Bonn 2025 – wissenschaftliches Programm
Bereiche | Tage | Auswahl | Suche | Aktualisierungen | Downloads | Hilfe
QI: Fachverband Quanteninformation
QI 16: Quantum Computing Theory III
QI 16.6: Vortrag
Dienstag, 11. März 2025, 15:15–15:30, HS IV
Limitations of Quantum Approximate Optimization in Solving Generic Higher-Order Constraint-Satisfaction Problems — Thorge Müller1,3, •Ajainderpal Singh2, Frank K. Wilhelm2,3, and Tim Bode2 — 1German Aerospace Center (DLR), Institute for Software Technology, Department High-Performance Computing, 51147 Cologne, Germany — 2Institute for Quantum Computing Analytics (PGI-12),Forschungszentrum Jülich, 52425 Jülich, Germany — 3Theoretical Physics, Saarland University, 66123 Saarbrücken, Germany
The ability of the Quantum Approximate Optimization Algorithm (QAOA) to deliver a quantum advantage on combinatorial optimization problems is still unclear. Recently, a scaling advantage over a classical solver was postulated to exist for random 8-SAT at the satisfiability threshold. At the same time, the viability of quantum error mitigation for deep circuits on near-term devices has been put in doubt. Here, we analyze the QAOA’s performance on random Max-kXOR as a function of k and the clause-to-variable ratio. As a classical benchmark, we use the Mean-Field Approximate Optimization Algorithm (MF-AOA) and find that it performs better than or equal to the QAOA on average. Still, for large k and numbers of layers p, there may remain a window of opportunity for the QAOA. However, by extrapolating our numerical results, we find that reaching high levels of satisfaction would require extremely large p, which must be considered rather difficult both in the variational context and on near-term devices.
Keywords: QAOA; Mean-Field AOA; Max-kXOR; combinatorial optimization