Large-scale quantum approximate optimization on nonplanar graphs with machine learning noise mitigation
Open accessThe DOI matches its Crossref record; 29 of the 29 references it cites were found in a registry or an index.
Abstract
Quantum computers are increasing in size and quality but are still very noisy. Error mitigation extends the size of the quantum circuits that noisy devices can meaningfully execute. However, state-of-the-art error mitigation methods are hard to implement and the limited qubit connectivity in superconducting qubit devices restricts most applications to the hardware's native topology. Here we show a quantum approximate optimization algorithm (QAOA) on nonplanar random regular graphs with up to 40 nodes enabled by a machine learning-based error mitigation. We use a swap network with careful decision-variable-to-qubit mapping and a feed-forward neural network to optimize a depth-two QAOA on up to 40 qubits. We observe a meaningful parameter optimization for the largest graph which requires running quantum circuits with 958 two-qubit gates. Our paper emphasizes the need to mitigate samples, and not only expectation values, in quantum approximate optimization. These results are a step towards executing quantum approximate optimization at a scale that is not classically simulable. Reaching such system sizes is key to properly understanding the true potential of heuristic algorithms like QAOA. Published by the American Physical Society 2024
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
Biamonte, J., Wittek, P., Pancotti, N., Rebentrost, P., Wiebe, N., & Lloyd, S. (2017) · Nature · doi:10.1038/nature23474 · Cited by 4,779
A variational eigenvalue solver on a photonic quantum processor
Peruzzo, A., McClean, J., Shadbolt, P., Yung, M.-H., Zhou, X.-Q., Love, P. J., Aspuru-Guzik, A., & O’Brien, J. L. (2014) · Nature Communications · doi:10.1038/ncomms5213 · Cited by 4,552 · cited 1×
“For variational algorithms, like the variational eigen-solver applied in a chemistry setting [71, 72], error mitigating expectation values are often sufficient, e.g., to compute the energy spectrum of molecules [73, 74].”
MethodGoemans, M. X., & Williamson, D. P. (1995) · Journal of the ACM · doi:10.1145/227683.227684 · Cited by 3,587 · cited 1×
“Furthermore, proper QAOA benchmarks must compare to state-of-theart solvers [32], such as Gurobi and CPLEX, and randomized rounding algorithms [60].”
MethodIsing formulations of many NP problems
Lucas, A. (2014) · Frontiers in Physics · doi:10.3389/fphy.2014.00005 · Cited by 2,512
Solving the quantum many-body problem with artificial neural networks
Carleo, G., & Troyer, M. (2017) · Science · doi:10.1126/science.aag2302 · Cited by 2,215 · cited 1×
“Supervised learning benefits a wide range of scientific fields, including quantum physics [24].”
BackgroundDynamical Decoupling of Open Quantum Systems
Viola, L., Knill, E., & Lloyd, S. (1999) · Physical Review Letters · doi:10.1103/physrevlett.82.2417 · Cited by 1,808 · cited 1×
“1(e) which also shows that these circuits leave little space for error suppression methods such as dynamical decoupling [47].”
BackgroundQuantum computational chemistry
McArdle, S., Endo, S., Aspuru-Guzik, A., Benjamin, S. C., & Yuan, X. (2020) · Reviews of Modern Physics · doi:10.1103/revmodphys.92.015003 · Cited by 1,621 · cited 1×
“INTRODUCTION Quantum information processing holds the promise of drastically speeding up a number of interesting computational tasks ranging from chemistry [1], finance [2], machine learning [3, 4], and high-energy physics [5, 6].”
BackgroundError Mitigation for Short-Depth Quantum Circuits
Temme, K., Bravyi, S., & Gambetta, J. M. (2017) · Physical Review Letters · doi:10.1103/physrevlett.119.180509 · Cited by 1,379
Evidence for the utility of quantum computing before fault tolerance
Kim, Y., Eddins, A., Anand, S., Wei, K. X., van den Berg, E., Rosenblatt, S., Nayfeh, H., Wu, Y., Zaletel, M., Temme, K., et al. (2023) · Nature · doi:10.1038/s41586-023-06096-3 · Cited by 1,050
Quantum optimization using variational algorithms on near-term quantum devices
Moll, N., Barkoutsos, P., Bishop, L. S., Chow, J. M., Cross, A., Egger, D. J., Filipp, S., Fuhrer, A., Gambetta, J. M., Ganzhorn, M., et al. (2018) · Quantum Science and Technology · doi:10.1088/2058-9565/aab822 · Cited by 744
Self-citationEfficient Variational Quantum Simulator Incorporating Active Error Minimization
Li, Y., & Benjamin, S. C. (2017) · Physical Review X · doi:10.1103/physrevx.7.021050 · Cited by 686
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 · cited 5×
“We achieve this by combining swap networks [20, 31], and the SAT-based initial mapping of Matsuo et al. [38] which was so far only numerically studied.”
BackgroundMethodInfluentialPractical Quantum Error Mitigation for Near-Future Applications
Endo, S., Benjamin, S. C., & Li, Y. (2018) · Physical Review X · doi:10.1103/physrevx.8.031027 · Cited by 562 · cited 1×
“In particular, error mitigation tools [7, 8], e.”
Probabilistic error cancellation with sparse Pauli–Lindblad models on noisy quantum processors
van den Berg, E., Minev, Z. K., Kandala, A., & Temme, K. (2023) · Nature Physics · doi:10.1038/s41567-023-02042-2 · Cited by 305
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 · cited 1×
“[48].”
Self-citationDigital zero noise extrapolation for quantum error mitigation
Giurgica-Tiron, T., Hindy, Y., LaRose, R., Mari, A., & Zeng, W. J. (2020) · 2020 IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce49297.2020.00045 · Cited by 241 · cited 1×
“As alternative, digital ZNE folds gates such as CNOTs which produce large stretch factors c = 2m+1 where m is the number of times a gate is folded [11].”
BackgroundDigital zero noise extrapolation for quantum error mitigation
Giurgica-Tiron, T., Hindy, Y., LaRose, R., Mari, A., & Zeng, W. J. (2020) · arXiv · doi:10.48550/arxiv.2005.10921 · Cited by 241
Learning-Based Quantum Error Mitigation
Strikis, A., Qin, D., Chen, Y., Benjamin, S. C., & Li, Y. (2021) · PRX Quantum · doi:10.1103/prxquantum.2.040330 · Cited by 237 · cited 3×
“[26, 27], we present an error mitigation strategy based on a neural network that uses measurements of noisy observables and compares them to their ideal values.”
BackgroundMethodLearning-based quantum error mitigation
Strikis, A., Qin, D., Chen, Y., Benjamin, S. C., & Li, Y. (2020) · arXiv · doi:10.48550/arxiv.2005.07601 · Cited by 237
Topological and Subsystem Codes on Low-Degree Graphs with Flag Qubits
Chamberland, C., Zhu, G., Yoder, T. J., Hertzberg, J. B., & Cross, A. W. (2020) · Physical Review X · doi:10.1103/physrevx.10.011022 · Cited by 223 · cited 1×
“Furthermore, many problems of practical interest are non-planar [33], but common superconducting qubit architectures have a grid [34] or heavy-hexagonal [35] coupling map.”
BackgroundTraining 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
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
Brandao, F. G. S. L., Broughton, M., Farhi, E., Gutmann, S., & Neven, H. (2018) · arXiv · doi:10.48550/arxiv.1812.04170 · Cited by 88
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
Halperin, E., Livnat, D., & Zwick, U. (2004) · Journal of Algorithms · doi:10.1016/j.jalgor.2004.06.001 · Cited by 53 · cited 1×
“For example, for RR3 graphs there is an approximation algorithm that achieves an approximation ratio of 0.9326 [70].”
MethodInfluentialStreif, M., Yarkoni, S., Skolik, A., Neukart, F., & Leib, M. (2021) · Physical Review A · doi:10.1103/physreva.104.012403 · Cited by 41
Benchmarking Quantum Processor Performance at Scale
McKay, D. C., Hincks, I., Pritchett, E. J., Carroll, M., Govia, L. C. G., & Merkel, S. T. (2023) · arXiv · doi:10.48550/arxiv.2311.05933 · Cited by 29
Error mitigation with Clifford quantum-circuit data
Czarnik, P., Arrasmith, A., Coles, P. J., & Cincio, L. (2021) · Quantum · doi:10.22331/q-2021-11-26-592 · Cited by 27 · cited 4×
“[26, 27], we present an error mitigation strategy based on a neural network that uses measurements of noisy observables and compares them to their ideal values.”
BackgroundMethodInfluentialGate-free state preparation for fast variational quantum eigensolver simulations: ctrl-VQE
Meitei, O. R., Gard, B. T., Barron, G. S., Pappas, D. P., Economou, S. E., Barnes, E., & Mayhall, N. J. (2020) · arXiv · doi:10.48550/arxiv.2008.04302 · Cited by 6
Cited by
Provable bounds for noise-free expectation values computed from noisy samples
Barron, S. V., Egger, D. J., Pelofske, E., Bärtschi, A., Eidenbenz, S., Lehmkuehler, M., & Woerner, S. (2024) · Nature Computational Science · doi:10.1038/s43588-024-00709-1 · Cited by 25
Self-citationmRNA Secondary Structure Prediction Using Utility-Scale Quantum Computers
Alevras, D., Metkar, M., Yamamoto, T., Kumar, V., Friedhoff, T., Park, J.-E., Takeori, M., LaDue, M., Davis, W., & Galda, A. (2024) · 2024 IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce60285.2024.00064 · Cited by 14
Kumar, V., Alevras, D., Metkar, M., Welling, E., Cade, C., Niesen, I., Friedhoff, T., Park, J.-E., Shivpuje, S., LaDue, M., et al. (2025) · arXiv · doi:10.48550/arxiv.2505.05782 · Cited by 3
“However, a majority of utility-scale studies on gate-based quantum computers [13], [14], [15], [16], [17], [18], [19], [20], [21], focus on problems that align closely with the architecture of available quantum hardware.”
Metadata
- Authors
- Sack, S. H., & Egger, D. J.
- Venue
- Physical Review Research
- Publisher
- American Physical Society (APS)
- Published
- 2024-03-01
- Volume
- 6
- Issue
- 1
- ISSN
- 2643-1564 (ISSN-L)
- OpenAlex
- W4392359185
- Cited by
- 40
- References
- 29
- FWCI
- 5.51
- Type
- journal article
- Language
- en
- Open access
- gold
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.