Journal Article

FZJ-2025-04050

http://join2-wiki.gsi.de/foswiki/pub/Main/Artwork/join2_logo100x88.png Limitations of quantum approximate optimization in solving generic higher-order constraint-satisfaction problems

Müller, T. (Corresponding author) ; Singh, A. ; Wilhelm, F. K.FZJ* ; Bode, T.FZJ*

2025
APS College Park, MD

This record in other databases:

Please use a persistent id in citations: doi:10.1103/PhysRevResearch.7.023165  doi:10.34734/FZJ-2025-04050

Abstract: 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 into doubt. Here we analyze the QAOA's performance on random Max-𝑘⁢XORas a function of 𝑘and the clause-to-variable ratio. As a classical benchmark, we use the mean-field approximate optimization algorithm and find that it performs better than or equal to the QAOA on average. Still, for large 𝑘and numbers of layers 𝑝, 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 𝑝, which must be considered rather difficult both in the variational context and on near-term devices.

---

Contributing Institute(s):

1. Quantum Computing Analytics (PGI-12)

Research Program(s):

1. 5214 - Quantum State Preparation and Control (POF4-521) (POF4-521)
2. BMBF 13N16149 - QSolid - Quantencomputer im Festkörper (BMBF-13N16149) (BMBF-13N16149)

Appears in the scientific report 2025

---

Database coverage:
; ; ; ; Article Processing Charges ; Clarivate Analytics Master Journal List ; DOAJ Seal ; Emerging Sources Citation Index ; Fees ; SCOPUS ; Web of Science Core Collection

---