TY - JOUR

T1 - Twisted hybrid algorithms for combinatorial optimization

AU - Caha, Libor

AU - Kliesch, Alexander

AU - Koenig, Robert

N1 - Publisher Copyright:
© 2022 The Author(s). Published by IOP Publishing Ltd.

PY - 2022/10

Y1 - 2022/10

N2 - 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.

AB - 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.

KW - MaxCut

KW - approximation algorithms

KW - combinatorial optimization

KW - hybrid algorithms

KW - quantum algorithms

KW - variational quantum algorithms

UR - http://www.scopus.com/inward/record.url?scp=85137897724&partnerID=8YFLogxK

U2 - 10.1088/2058-9565/ac7f4f

DO - 10.1088/2058-9565/ac7f4f

M3 - Article

AN - SCOPUS:85137897724

SN - 2058-9565

VL - 7

JO - Quantum Science and Technology

JF - Quantum Science and Technology

IS - 4

M1 - 045013

ER -