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

Evaluating Quantum Approximate Optimization Algorithm: A Case Study

Open access
Shaydulin, Ruslan, Alexeev, Yuri·2019·2019 Tenth International Green and Sustainable Computing Conference (IGSC)
DOI 10.1109/igsc48788.2019.8957201
Open this paper in CoChat — free accountOpen PDF

Abstract

Quantum Approximate Optimization Algorithm (QAOA) is one of the most promising quantum algorithms for the Noisy Intermediate-Scale Quantum (NISQ) era. Quantifying the performance of QAOA in the near-term regime is of utmost importance. We perform a large-scale numerical study of the approximation ratios attainable by QAOA is the low-to medium-depth regime. To find good QAOA parameters we perform 990 million 10-qubit QAOA circuit evaluations. We find that the approximation ratio increases only marginally as the depth is increased, and the gains are offset by the increasing complexity of optimizing variational parameters. We observe a high variation in approximation ratios attained by QAOA, including high variations within the same class of problem instances. We observe that the difference in approximation ratios between problem instances increases as the similarity between instances decreases. We find that optimal QAOA parameters concentrate for instances in out benchmark, confirming the previous findings for a different class of problems.

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.1109/igsc48788.2019.8957201

Cites

7 of 7 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?

  • Investigations on the impact of different classical optimizers for parameter optimization in general advocate for gradient-free global optimizers when dealing with real quantum hardware.

    “Investigations on the impact of different classical optimizers for parameter optimization in general advocate for gradient-free global optimizers when dealing with real quantum hardware [37, 47, 100, 121].”

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

    The Methods (p. 2) describe using derivative-free BOBYQA to optimize QAOA parameters, but call it a local optimizer; the study is numerical, not an evaluation on real quantum hardware. The Discussion (p. 5) notes limitations of local optimization while also describing gradient-based approaches as promising. It does not generally advocate gradient-free global optimizers for hardware. (LLM, conf=0.86)

    Experimental — accuracy not yet measured

  • A large-scale evaluation on QAOA validated the theoretical properties and yielded further empirical performance bounds.

    “Continuing with empirical studies on gate-based quantum CO approaches, a large-scale evaluation on QAOA [92, 121] validated the theoretical properties [4, 21, 43] and yielded further empirical performance bounds.”

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

  • The reachability issue of QAOA has been theoretically proven and empirically validated.

    “It has been theoretically proven [4, 43, 44] and empirically validated [121].”

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

  • Optimal parameters for QAOA are similar for similar problem instances.

    “Optimal parameters for QAOA are similar for similar problem instances.”

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

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: 11

  1. [1][1] E. Farhi, J. Goldstone, and S. Gutmann, 'A quantum approximate optimization algorithm,' arXiv:1411.4028 , 2014. - · arXiv
  2. [2][2] --, 'A quantum approximate optimization algorithm applied to a bounded occurrence constraint problem,' arXiv:1412.6062 , 2014. - · arXiv
  3. [4][4] --, 'Community detection across emerging quantum architectures,' Proceedings of the 3rd International Workshop on Post Moore's Era Supercomputing , 2018. -
  4. [5][5] P. K. Barkoutsos, G. Nannicini, A. Robert, I. Tavernelli, and S. Woerner, 'Improving variational quantum optimization using cvar,' arXiv preprint arXiv:1907.04769 , 2019. - · arXiv
  5. [7][7] L. Zhou, S.-T. Wang, S. Choi, H. Pichler, and M. D. Lukin, 'Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near-term devices,' arXiv:1812.01041 , 2018. - · arXiv
  6. [10][10] G. B. Mbeng, R. Fazio, and G. Santoro, 'Quantum annealing: a journey through digitalitalization, control, and hybrid quantum variational schemes,' arXiv preprint arXiv:1906.08948 , 2019. - · arXiv
  7. [14][14] M. J. Powell, 'The BOBYQA algorithm for bound constrained optimization without derivatives,' Cambridge NA Report NA2009/06, University of Cambridge, Cambridge , pp. 26-46, 2009. -
  8. [17][17] P. Erd˝ os and A. R´ enyi, 'On the evolution of random graphs,' Publ. Math. Inst. Hung. Acad. Sci , vol. 5, no. 1, pp. 17-60, 1960. -
  9. [19][19] A. A. Hagberg, D. A. Schult, and P. J. Swart, 'Exploring network structure, dynamics, and function using NetworkX,' in Proceedings of the 7th Python in Science Conference (SciPy 2008) , G. Varoquaux, T. Vaught, and J. Millman, Eds., Pasadena, CA USA, 2008, pp. 11-15. -
  10. [21][21] F. G. Brandao, M. Broughton, E. Farhi, S. Gutmann, and H. Neven, 'For fixed control parameters the quantum approximate optimization algorithm's objective function value concentrates for typical instances,' arXiv:1812.04170 , 2018. - · arXiv
  11. [23][23] S. Khairy, R. Shaydulin, L. Cincio, Y. Alexeev, and P. Balaprakash, 'Reinforcement-learning-based variational quantum circuits optimization for combinatorial problems,' Accepted for Poster Presentation at the Machine Learning and the Physical Sciences workshop at Conference on Neural Information Processing Systems (NeurIPS 2019), 2019. -

Cited by

Sorted by citations

Authors
Shaydulin, R., & Alexeev, Y.
Affiliations
  • Clemson University (US)
  • Argonne National Laboratory (US)
ORCID
Venue
2019 Tenth International Green and Sustainable Computing Conference (IGSC)
Publisher
IEEE
Published
2019-10
Pages
1-6
DOI
10.1109/igsc48788.2019.8957201
OpenAlex
W2979402214
Cited by
55
References
7
Citations by year
2026: 1 · 2025: 5 · 2024: 9 · 2023: 12 · 2022: 12 · 2021: 9 · 2020: 5 · 2019: 2
FWCI
2.68
Type
conference paper
Language
en
Open access
Licence
Locations
  • International Green and Sustainable Computing Conference (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
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, approximation ratio, variational parameter optimization, circuit depth, NISQ devices, combinatorial optimization

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