Adaptive quantum approximate optimization algorithm for solving combinatorial problems on a quantum computer
Open accessThe DOI matches its Crossref record; 22 of the 22 references it cites were found in a registry or an index.
Abstract
The quantum approximate optimization algorithm (QAOA) is a hybrid variational quantum-classical algorithm that solves combinatorial optimization problems. While there is evidence suggesting that the fixed form of the standard QAOA Ansatz is not optimal, there is no systematic approach for finding better Ans\"atze. We address this problem by developing an iterative version of QAOA that is problem tailored, and which can also be adapted to specific hardware constraints. We simulate the algorithm on a class of Max-Cut graph problems and show that it converges much faster than the standard QAOA, while simultaneously reducing the required number of CNOT gates and optimization parameters. We provide evidence that this speedup is connected to the concept of shortcuts to adiabaticity.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Ising formulations of many NP problems
Lucas, A. (2014) · Frontiers in Physics · doi:10.3389/fphy.2014.00005 · Cited by 2,512
An adaptive variational algorithm for exact molecular simulations on a quantum computer
Grimsley, H. R., Economou, S. E., Barnes, E., & Mayhall, N. J. (2019) · Nature Communications · doi:10.1038/s41467-019-10988-2 · Cited by 1,033
Self-citationZhou, L., Wang, S.-T., Choi, S., Pichler, H., & Lukin, M. D. (2020) · Physical Review X · doi:10.1103/physrevx.10.021067 · Cited by 913
From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
Hadfield, S., Wang, Z., O’Gorman, B., Rieffel, E. G., Venturelli, D., & Biswas, R. (2019) · Algorithms · doi:10.3390/a12020034 · Cited by 772
Quantum approximate optimization of non-planar graph problems on a planar superconducting processor
Harrigan, M. P., Sung, K. J., Neeley, M., Satzinger, K. J., Arute, F., Arya, K., Atalaya, J., Bardin, J. C., Barends, R., Boixo, S., et al. (2021) · Nature Physics · doi:10.1038/s41567-020-01105-y · Cited by 564
Tang, H. L., Shkolnikov, V. O., Barron, G. S., Grimsley, H. R., Mayhall, N. J., Barnes, E., & Economou, S. E. (2021) · PRX Quantum · doi:10.1103/prxquantum.2.020310 · Cited by 408
Self-citationTang, H. L., Shkolnikov, V. O., Barron, G. S., Grimsley, H. R., Mayhall, N. J., Barnes, E., & Economou, S. E. (2019) · arXiv · doi:10.48550/arxiv.1911.10205 · Cited by 408
Self-citationQuantum approximate optimization algorithm for MaxCut: A fermionic view
Wang, Z., Hadfield, S., Jiang, Z., & Rieffel, E. G. (2018) · Physical Review A · doi:10.1103/physreva.97.022304 · Cited by 353
QAOA for Max-Cut requires hundreds of qubits for quantum speed-up
Guerreschi, G. G., & Matsuura, A. Y. (2019) · Scientific Reports · doi:10.1038/s41598-019-43176-9 · Cited by 337
Obstacles to State Preparation and Variational Optimization from Symmetry Protection
Bravyi, S., Kliesch, A., Koenig, R., & Tang, E. (2019) · arXiv · doi:10.48550/arxiv.1910.08980 · Cited by 279
Obstacles to Variational Quantum Optimization from Symmetry Protection
Bravyi, S., Kliesch, A., Koenig, R., & Tang, E. (2020) · Physical Review Letters · doi:10.1103/physrevlett.125.260505 · Cited by 278
Improving Variational Quantum Optimization using CVaR
Barkoutsos, P. K., Nannicini, G., Robert, A., Tavernelli, I., & Woerner, S. (2020) · Quantum · doi:10.22331/q-2020-04-20-256 · Cited by 263
Efficient and noise resilient measurements for quantum chemistry on near-term quantum computers
Huggins, W. J., McClean, J. R., Rubin, N. C., Jiang, Z., Wiebe, N., Whaley, K. B., & Babbush, R. (2021) · npj Quantum Information · doi:10.1038/s41534-020-00341-7 · Cited by 256
Optimizing Variational Quantum Algorithms Using Pontryagin’s Minimum Principle
Yang, Z.-C., Rahmani, A., Shabani, A., Neven, H., & Chamon, C. (2017) · Physical Review X · doi:10.1103/physrevx.7.021027 · Cited by 210
XY mixers: Analytical and numerical results for the quantum alternating operator ansatz
Wang, Z., Rubin, N. C., Dominy, J. M., & Rieffel, E. G. (2020) · Physical Review A · doi:10.1103/physreva.101.012320 · Cited by 190
Avoiding local minima in variational quantum eigensolvers with the natural gradient optimizer
Wierichs, D., Gogolin, C., & Kastoryano, M. (2020) · Physical Review Research · doi:10.1103/physrevresearch.2.043246 · Cited by 172
Generating shortcuts to adiabaticity in quantum and classical dynamics
Jarzynski, C. (2013) · Physical Review A · doi:10.1103/physreva.88.040101 · Cited by 159
Reachability Deficits in Quantum Approximate Optimization
Akshay, V., Philathong, H., Morales, M. E. S., & Biamonte, J. D. (2020) · Physical Review Letters · doi:10.1103/physrevlett.124.090504 · Cited by 151
Superadiabatic Controlled Evolutions and Universal Quantum Computation
Santos, A. C., & Sarandy, M. S. (2015) · Scientific Reports · doi:10.1038/srep15775 · Cited by 125
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
On the Universality of the Quantum Approximate Optimization Algorithm
Morales, M. E. S., Biamonte, J., & Zimborás, Z. (2019) · arXiv · doi:10.48550/arxiv.1909.03123 · Cited by 95
Quantum Algorithms for Fixed Qubit Architectures
Farhi, E., Goldstone, J., Gutmann, S., & Neven, H. (2017) · arXiv · doi:10.48550/arxiv.1703.06199 · Cited by 93
Research works printed but not linked: 15
- 10.1007/s10878-014-9734-0 · DOI · Paper page
- 10.1073/pnas.2006373117 · DOI · Paper page
- 10.1103/PhysRevA.95.062317 · DOI
- 10.1007/s11128-020-02748-9 · DOI · Paper page
- 10.1021/jp030708a · DOI · Paper page
- 10.1088/1751-8113/42/36/365303 · DOI · Paper page
- 10.1103/RevModPhys.91.045001 · DOI · Paper page
- 10.1103/PhysRevApplied.15.024038 · DOI · Paper page
- R. Shaydulin, 2019, 2019 IEEE High Performance Extreme Computing Conference (HPEC)
- 10.1103/PhysRevE.88.062122 · DOI · Paper page
- 10.1038/s41567-020-0989-3 · DOI
- 10.1016/j.physrep.2017.07.001 · DOI · Paper page
- 10.1073/pnas.1619826114 · DOI · Paper page
- 10.1103/PhysRevLett.123.090602 · DOI · Paper page
- 10.1103/PhysRevA.94.042132 · DOI · Paper page
Cited by
Variational quantum algorithms
Cerezo, M., Arrasmith, A., Babbush, R., Benjamin, S. C., Endo, S., Fujii, K., McClean, J. R., Mitarai, K., Yuan, X., Cincio, L., et al. (2021) · Nature Reviews Physics · doi:10.1038/s42254-021-00348-9 · Cited by 3,385
Generalization in quantum machine learning from few training data
Caro, M. C., Huang, H.-Y., Cerezo, M., Sharma, K., Sornborger, A., Cincio, L., & Coles, P. J. (2022) · Nature Communications · doi:10.1038/s41467-022-32550-3 · Cited by 476
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
Barren plateaus in variational quantum computing
Larocca, M., Thanasilp, S., Wang, S., Sharma, K., Biamonte, J., Coles, P. J., Cincio, L., McClean, J. R., Holmes, Z., & Cerezo, M. (2025) · Nature Reviews Physics · doi:10.1038/s42254-025-00813-9 · Cited by 257
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
Metadata
- Authors
- Zhu, L., Tang, H. L., Barron, G. S., Calderon-Vargas, F. A., Mayhall, N. J., Barnes, E., & Economou, S. E.
- Venue
- Physical Review Research
- Publisher
- American Physical Society (APS)
- Published
- 2022-07-11
- Volume
- 4
- Issue
- 3
- ISSN
- 2643-1564 (ISSN-L)
- OpenAlex
- W3026387229
- Cited by
- 209
- References
- 22
- FWCI
- 13.73
- Type
- journal article
- Language
- en
- Open access
- gold
- Funders
- U.S. Department of Energy (DE-SC0019318, DE-SC0019199)
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
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.