For Fixed Control Parameters the Quantum Approximate Optimization Algorithm's Objective Function Value Concentrates for Typical Instances
Open accessAbstract
The Quantum Approximate Optimization Algorithm, QAOA, uses a shallow depth quantum circuit to produce a parameter dependent state. For a given combinatorial optimization problem instance, the quantum expectation of the associated cost function is the parameter dependent objective function of the QAOA. We demonstrate that if the parameters are fixed and the instance comes from a reasonable distribution then the objective function value is concentrated in the sense that typical instances have (nearly) the same value of the objective function. This applies not just for optimal parameters as the whole landscape is instance independent. We can prove this is true for low depth quantum circuits for instances of MaxCut on large 3-regular graphs. Our results generalize beyond this example. We support the arguments with numerical examples that show remarkable concentration. For higher depth circuits the numerics also show concentration and we argue for this using the Law of Large Numbers. We also observe by simulation that if we find parameters which result in good performance at say 10 bits these same parameters result in good performance at say 24 bits. These findings suggest ways to run the QAOA that reduce or eliminate the use of the outer loop optimization and may allow us to find good solutions with fewer calls to the quantum computer.
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.
Integrity signals
Registry
Cites
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.
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?
By fixing QAOA parameters and selecting typical problem instances from a reasonable distribution, the objective function value concentrates, i.e. is almost independent of the problem instance.
“Remarkably, it was shown that by fixing the QAOA parameters and selecting the typical problem instances from a reasonable distribution, the objective function value concentrates, i.e. the objective function value is almost independent of the problem instance (Brandao et al. , 2018).”
From Noisy intermediate-scale quantum algorithms (2022) · cites this paper as Brandao et al. , 2018
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 [21]
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
No references could be resolved yet.
Research works printed but not linked: 7
- [2]Edward Farhi, Jeffrey Goldstone, Sam Gutmann. A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem, 2015. arXiv:1412.6062 [quant-ph]. · arXiv
- [3]Eran Halperin, Dror Livnat, Uri Zwick. MAX CUT in cubic graphs, 2004. Journal of Algorithms, Volume 53 Issue 2, Pages 169-185.
- [4]Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright. Beating the random assignment on constraint satisfaction problems of bounded degree, 2015. Electronic Colloquium on Computational Complexity, Report No. 82 (2015). arXiv:1505.03424 [cs.CC]. · arXiv
- [9]Training A Quantum Optimizer, 2016. Phys. Rev. A, Volume 94 Issue 2, Pages 022309.
- [11]Performance of the Quantum Approximate Optimization Algorithm on the Maximum Cut Problem, 2018. arXiv:1811.08419 [quant-ph]. · arXiv
- [8]Leo Zhou, Sheng-Tao Wang, Soonwon Choi, Hannes Pichler, Mikhail D. Lukin. Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices, 2018. arXiv:1812.01041 [quant-ph]. · arXiv
- [9]Sergey Bravyi, Dan Browne, Padraic Calpin, Earl Campbell, David Gosset, Mark Howard. Simulation of quantum circuits by low-rank stabilizer decompositions, 2018. arXiv:1808.00128 [quant-ph]. · arXiv
Cited by
Sorted by citations
Noisy intermediate-scale quantum algorithms
Bharti, K., Cervera-Lierta, A., Kyaw, T. H., Haug, T., Alperin-Lea, S., Anand, A., Degroote, M., Heimonen, H., Kottmann, J. S., Menke, T., et al. (2022) · Reviews of Modern Physics · doi:10.1103/revmodphys.94.015004 · Cited by 1,726 · see citing works
Warm-starting quantum optimization
Egger, D. J., Mareček, J., & Woerner, S. (2021) · Quantum · doi:10.22331/q-2021-06-17-479 · Cited by 269 · see citing works
Training the quantum approximate optimization algorithm without access to a quantum processing unit
Streif, M., & Leib, M. (2020) · Quantum Science and Technology · doi:10.1088/2058-9565/ab8c2b · Cited by 125 · see citing works
Parameter concentrations in quantum approximate optimization
Akshay, V., Rabinovich, D., Campos, E., & Biamonte, J. (2021) · Physical Review A · doi:10.1103/physreva.104.l010401 · Cited by 103 · see citing works
Quantum optimization with a novel Gibbs objective function and ansatz architecture search
Li, L., Fan, M., Coram, M., Riley, P., & Leichenauer, S. (2020) · Physical Review Research · doi:10.1103/physrevresearch.2.023074 · Cited by 98 · see citing works
Layer VQE: A Variational Approach for Combinatorial Optimization on Noisy Quantum Computers
Liu, X., Angone, A., Shaydulin, R., Safro, I., Alexeev, Y., & Cincio, L. (2022) · IEEE Transactions on Quantum Engineering · doi:10.1109/tqe.2021.3140190 · Cited by 78 · see citing works
Transferability of optimal QAOA parameters between random graphs
Galda, A., Liu, X., Lykov, D., Alexeev, Y., & Safro, I. (2021) · 2021 IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce52317.2021.00034 · Cited by 72 · see citing works
Multiblock ADMM Heuristics for Mixed-Binary Optimization on Classical and Quantum Computers
Gambella, C., & Simonetto, A. (2020) · IEEE Transactions on Quantum Engineering · doi:10.1109/tqe.2020.3033139 · Cited by 60 · see citing works
Dalyac, C., Henriet, L., Jeandel, E., Lechner, W., Perdrix, S., Porcheron, M., & Veshchezerova, M. (2021) · EPJ Quantum Technology · doi:10.1140/epjqt/s40507-021-00100-3 · Cited by 46 · see citing works
Parameter Setting in Quantum Approximate Optimization of Weighted Problems
Sureshbabu, S. H., Herman, D., Shaydulin, R., Basso, J., Chakrabarti, S., Sun, Y., & Pistoia, M. (2024) · Quantum · doi:10.22331/q-2024-01-18-1231 · Cited by 41 · see citing works
Streif, M., Yarkoni, S., Skolik, A., Neukart, F., & Leib, M. (2021) · Physical Review A · doi:10.1103/physreva.104.012403 · Cited by 41 · see citing works
Exploiting Symmetry Reduces the Cost of Training QAOA
Shaydulin, R., & Wild, S. M. (2021) · IEEE Transactions on Quantum Engineering · doi:10.1109/tqe.2021.3066275 · Cited by 39 · see citing works
Montañez-Barrera, J. A., & Michielsen, K. (2025) · npj Quantum Information · doi:10.1038/s41534-025-01082-1 · Cited by 34 · see citing works
Alam, M., Ash-Saki, A., & Ghosh, S. (2019) · arXiv · doi:10.48550/arxiv.1907.09631 · Cited by 33 · see citing works
QAOAKit: A Toolkit for Reproducible Study, Application, and Verification of the QAOA
Shaydulin, R., Marwaha, K., Wurtz, J., & Lotshaw, P. C. (2021) · 2021 IEEE/ACM Second International Workshop on Quantum Computing Software (QCS) · doi:10.1109/qcs54837.2021.00011 · Cited by 31 · see citing works
Quantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping Study
Gemeinhardt, F., Garmendia, A., Wimmer, M., Weder, B., & Leymann, F. (2024) · ACM Computing Surveys · doi:10.1145/3620668 · Cited by 22 · see citing works
“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.”
BackgroundMethodHigh-Round QAOA for MAX $k$-SAT on Trapped Ion NISQ Devices
Pelofske, E., Bärtschi, A., Golden, J., & Eidenbenz, S. (2023) · 2023 IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce57702.2023.00064 · Cited by 15 · see citing works
- Authors
- Brandao, F. G. S. L., Broughton, M., Farhi, E., Gutmann, S., & Neven, H.
- Affiliations
- Google (United States) (US)
- Venue
- arXiv
- Publisher
- arXiv
- Published
- 2018
- ISSN
- 2331-8422 (ISSN-L)
- arXiv
- 1812.04170
- OpenAlex
- W2904281284
- Cited by
- 88
- References
- 0
- Citations by year
- 2025: 8 · 2024: 10 · 2023: 13 · 2022: 15 · 2021: 19 · 2020: 16 · 2019: 7
- Type
- posted content
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- arXiv (Cornell University) (submittedVersion)
- CaltechAUTHORS (California Institute of Technology) (submittedVersion)
- arXiv (Cornell University)
- Funders
- National Science Foundation (1729369)
- Army Research Office (W911NF-17-1-0433, W911NF-17, W911NF)
- 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 › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Keywords
- quantum approximate optimization algorithm, MaxCut, cubic graphs, combinatorial optimization, law of large numbers, parameter 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
