Limitations of quantum approximate optimization in solving generic higher-order constraint-satisfaction problems
Physical Review Research · 19.05.2025 · 7 (2)
DOI: 10.1103/physrevresearch.7.023165 ↗Kurz gefasst
Fachartikel in der Zeitschrift Physical Review Research, online erschienen am 19.05.2025. Verfasst von Thorge Müller und 3 weiteren Autor:innen. Die Arbeit wurde bisher 8-mal zitiert (Crossref) und nennt 22 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Deutsches Zentrum für Luft- und Raumfahrt, Forschungszentrum Jülich, Bundesministerium für Bildung und Forschung.
Abstract (Originalsprache)
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- k XOR as a function of k 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 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.
Förderung
- Deutsches Zentrum für Luft- und Raumfahrt
- Forschungszentrum Jülich
- Bundesministerium für Bildung und Forschung
- Bundesministerium für Wirtschaft und Klimaschutz
Zitieren
APA
Müller, T., Singh, A., Wilhelm, F. K., & Bode, T. (2025). Limitations of quantum approximate optimization in solving generic higher-order constraint-satisfaction problems. Physical Review Research, 7(2). https://doi.org/10.1103/physrevresearch.7.023165
Vancouver
Müller T, Singh A, Wilhelm FK, Bode T. Limitations of quantum approximate optimization in solving generic higher-order constraint-satisfaction problems. Physical Review Research. 2025;7(2). doi:10.1103/physrevresearch.7.023165
BibTeX
@article{Mller2025,
author = {Müller, Thorge and Singh, Ajainderpal and Wilhelm, Frank K. and Bode, Tim},
title = {Limitations of quantum approximate optimization in solving generic higher-order constraint-satisfaction problems},
journal = {Physical Review Research},
year = {2025},
volume = {7},
number = {2},
doi = {10.1103/physrevresearch.7.023165}
}
EUVIMED