EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Limitations of quantum approximate optimization in solving generic higher-order constraint-satisfaction problems

Thorge Müller, Ajainderpal Singh, Frank K. Wilhelm, Tim Bode

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →