CoChat
Sign Up
Cited by 128Quantum Computing Algorithms and ArchitectureQuantum many-body systemsMetaheuristic Optimization Algorithms Research

Benchmarking the quantum approximate optimization algorithm

Open access
Willsch, Madita, Willsch, Dennis, Jin, Fengping, De Raedt, Hans, Michielsen, Kristel·2020·Quantum Information Processing
DOI 10.1007/s11128-020-02692-8
Open this paper in CoChat — free accountOpen PDF

Abstract

The performance of the quantum approximate optimization algorithm is evaluated by using three different measures: the probability of finding the ground state, the energy expectation value, and a ratio closely related to the approximation ratio. The set of problem instances studied consists of weighted MaxCut problems and 2-satisfiability problems. The Ising model representations of the latter possess unique ground states and highly degenerate first excited states. The quantum approximate optimization algorithm is executed on quantum computer simulators and on the IBM Q Experience. Additionally, data obtained from the D-Wave 2000Q quantum annealer are used for comparison, and it is found that the D-Wave machine outperforms the quantum approximate optimization algorithm executed on a simulator. The overall performance of the quantum approximate optimization algorithm is found to strongly depend on the problem instance.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1007/s11128-020-02692-8

Cites

25 of 25 references verified0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Other investigations highlight the strong dependence of QAOA on the problem instance, the number of parameters, and their initialization.

    “Other investigations highlight the strong dependence of QAOA on the problem instance, the number of parameters, and their initialization [81, 142].”

    From Quantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping Study (2024) · cites this paper as [142]

  • Comparative evaluation studies have demonstrated the superiority of QA in terms of performance.

    “Last, comparative evaluation studies between VQAs and QA have demonstrated (i) the reachability issues of QAOA compared to VQE [10], (ii) the ability of QAOA to harness diabatic processes in contrast to QA [154], (iii) the superiority of QA in terms of performance [142], and (iv) the character of QAOA as a digitized version of QA [141].”

    From Quantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping Study (2024) · cites this paper as [142]

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

Flagged first, then by citations

Research works printed but not linked: 10

  1. Farhi, E., Goldstone, J., Gutmann, S.: A quantum approximate optimization algorithm (2014). arXiv:1411.4028 · arXiv
  2. Streif, M., Leib, M.: Comparison of QAOA with quantum and simulated annealing (2019). arXiv:1901.01903 · arXiv
  3. Otterbach, J. S., Manenti, R., Alidoust, N., Bestwick, A., Block, M., Bloom, B., Caldwell, S., Didier, N., Fried, E. S., Hong, S., Karalekas, P., Osborn, C.B., Papageorge, A., Peterson, E.C., Prawiroatmodjo, G., Rubin, G., Ryan, C.A., Scarabelli, D., Scheer, M., Sete, E.A., Sivarajah, P., Smith, R.S., Staley, A., Tezak, N., Zeng, W.J., Hudson, A., Johnson, B.R., Reagor, M., da Silva, M.P., Rigetti, C.: Unsupervised machine learning on a hybrid quantum computer (2017). arXiv:1712.05771 · arXiv
  4. Farhi, E., Harrow, A.W.: Quantum supremacy through the quantum approximate optimization algorithm (2016). arXiv:1602.07674 · arXiv
  5. Farhi, E., Goldstone, J., Gutmann, S., Sipser, M.: Quantum computation by adiabatic evolution (2000). arXiv:quant-ph/0001106 · arXiv
  6. O'Malley, P.J.J., Babbush, R., Kivlichan, I.D., Romero, J., McClean, J.R., Barends, R., Kelly, J., Roushan, P., Tranter, A., Ding, N., Campbell, B., Chen, Y., Chen, Z., Chiaro, B., Dunsworth, A., Fowler, A.G., Jeffrey, E., Lucero, E., Megrant, A., Mutus, J.Y., Neeley, M., Neill, C., Quintana, C., Sank, D., Vainsencher, A., Wenner, J., White, T.C., Coveney, P.V., Love, P.J., Neven, H., Aspuru-Guzik, A., Martinis, J.M.: Scalable quantum simulation of molecular energies. Phys. Rev. X 6, 031007 (2016)
  7. Yang, Z., Rahmani, A., Shabani, A., Neven, H., Chamon, C.: Optimizing variational quantum algo- rithms using Pontryagin's minimum principle. Phys. Rev. X 7, 021027 (2017)
  8. Press, W.H., Teukolsky, S.A., Vetterling, W.T., Flannery, B.P.: Numerical Recipes, 3rd Edition: The Art of Scientific Computing. Cambridge University Press, New York (2007)
  9. Crooks, G.E.: Performance of the quantum approximate optimization algorithm on the maximum cut problem (2018). arXiv:1811.08419v1 · arXiv
  10. Zhou, L., Wang, S.-T., Choi, S., Pichler, H., Lukin, M.D.: Quantum approximate optimiza- tion algorithm: performance, mechanism, and implementation on near-term devices (2018). arXiv:1812.01041v1 · arXiv

Cited by

Sorted by citations

Authors
Willsch, M., Willsch, D., Jin, F., De Raedt, H., & Michielsen, K.
Affiliations
Forschungszentrum Jülich (DE)
Corresponding author
Willsch, Madita
ORCID
Willsch, Madita
Venue
Quantum Information Processing
Publisher
Springer Science and Business Media LLC
Published
2020-06-02
Volume
19
Issue
7
ISSN
  • 1570-0755 (ISSN-L)
  • 1573-1332
DOI
10.1007/s11128-020-02692-8
OpenAlex
W2955075300
Cited by
128
References
25
Citations by year
2026: 9 · 2025: 17 · 2024: 24 · 2023: 24 · 2022: 29 · 2021: 23 · 2020: 2
FWCI
7.66
Type
journal article
Language
en
Open access
Licence
Locations
  • Quantum Information Processing (publishedVersion, cc-by)
  • arXiv (Cornell University) (publishedVersion)
  • University of Groningen research database (University of Groningen / Centre for Information Technology) (submittedVersion, cc-by)
  • arXiv (Cornell University)
Funders
  • Helmholtz-Gemeinschaft (ZT-0013)
  • European Commission (820363)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum many-body systems
  • Physical Sciences › Computer Science › Artificial Intelligence › Metaheuristic Optimization Algorithms Research
Keywords
quantum approximate optimization algorithm, benchmarking, Ising model, energy expectation value, approximation ratio, quantum annealing, D-Wave 2000Q

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review