.png){kind=icon}
Return
Twisted hybrid algorithms for combinatorial optimization
.png){kind=icon}
OA
AI
DOI：10.1088/2058-9565/ac7f4f.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Proposed hybrid algorithms encode a combinatorial cost function into a problem Hamiltonian and optimize its energy by varying over a set of states with low circuit complexity. Classical processing is typically only used for the choice of variational parameters following gradient descent. As a consequence, these approaches are limited by the descriptive power of the associated states. We argue that for certain combinatorial optimization problems, such algorithms can be hybridized further, thus harnessing the power of efficient non-local classical processing. Specifically, we consider combining a quantum variational ansatz with a greedy classical post-processing procedure for the MaxCut-problem on three-regular graphs. We show that the average cut-size produced by this method can be quantified in terms of the energy of a modified problem Hamiltonian. This motivates the consideration of an improved algorithm which variationally optimizes the energy of the modified Hamiltonian. We call this a twisted hybrid algorithm since the additional classical processing step is combined with a different choice of variational parameters. We exemplify the viability of this method using the quantum approximate optimization algorithm (QAOA), giving analytic lower bounds on the expected approximation ratios achieved by twisted QAOA. We observe that for levels p - 1, ..., 5, these lower bounds are comparable to the known lower bounds on QAOA at level p + 1 for high-girth graphs. This suggests that using twisted QAOA can reduce the circuit depth by 4 and the number of variational parameters by 2.
Keywords:
quantum algorithms
variational quantum algorithms
combinatorial optimization
approximation algorithms
hybrid algorithms
MaxCut
Journal
IF:
5
Papers:
1.4K
Citations:
5.1K
Organization
Cited Papers
.png){kind=icon}
ShareSave
ShareSaveShareSaveShareSaveShareSave
View more