Current browse context:
quant-ph
Change to browse by:
References & Citations
Quantum Physics
Title: The Overlap Gap Property limits limit swapping in QAOA
(Submitted on 9 Apr 2024)
Abstract: The Quantum Approximate Optimization Algorithm (QAOA) is a quantum algorithm designed for combinatorial optimization problem. We show that under the assumption that the Overlap Gap Property (OGP) in the solution space for the Max-$q$-XORSAT is a monotonic increasing function, the swapping of limits in QAOA leads to suboptimal results limited by the OGP. Furthermore, since the performance of QAOA for the pure $q$-spin model matches asymptotically for Max-$q$-XORSAT on large-girth regular hypergraph, we show that the average-case value obtained by QAOA for the pure $q$-spin model for even $q\ge 4$ is bounded away from optimality even when the algorithm runs indefinitely. This suggests that a necessary condition for the validity of limit swapping in QAOA is the absence of OGP in a given combinatorial optimization problem. A corollary of this is that the spectral gap of a Hamiltonian exhibiting the OGP will close in the thermodynamic limit resulting in a limitation of the quantum adiabatic theorem and efficient optimization of QAOA parameters. Furthermore, the results suggests that even when sub-optimised, the performance of QAOA on spin glass is equal in performance to Montanari's classical algorithm in solving the mean field spin glass problem, the best known classical algorithm.
Link back to: arXiv, form interface, contact.