Bereiche | Tage | Auswahl | Suche | Aktualisierungen | Downloads | Hilfe
QI: Fachverband Quanteninformation
QI 15: Quantum Computing Theory
QI 15.7: Vortrag
Mittwoch, 20. März 2024, 11:30–11:45, HFT-FT 101
Overlap Gap Property limits limit swaping in QAOA — •Mark Goh — Institute of Material Physics in Space, German Aerospace Center, Cologne, Germany — Institute for Theoretical Physics, University of Cologne, Cologne, Germany
The Quantum Approximate Optimization Algorithm (QAOA) is a quantum algorithm designed for finding approximate solutions to combinatorial optimization problem. Recent works on evaluating the performance of QAOA for q-spin glass models have been found to to beat semi-definite programming at layer p=11 for the Sherrington–Kirkpatrick model (2-spin glass). In addition, the algorithm to evaluate the expectation value has time complexity O(p2 4p), independent of the input size in the large n limit.
We show that under the likely conjecture that Max-q-XORSAT on large-girth regular hypergraph exhibit the Overlap Gap Property (OGP), the swapping of limits in QAOA leads to suboptimal results. Numerical simulations of Max-q-XORSAT on large-girth regular hypergraph supports the conjecture as OGP is observed when the degree of a vertex is greater than q.
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≥ 4 is bounded away from optimality even when the algorithm runs indefinitely if the conjecture is true. This suggests that a necessary condition for the validity of limit swapping in QAOA is the absence of OGP.
Keywords: Quantum Algorithm; Quantum Computing; QAOA; Overlap Gap Property; NISQ