Analysis of Quantum Approximate Optimization Algorithm under Realistic Noise in Superconducting Qubits
Open accessAbstract
The quantum approximate optimization algorithm (QAOA) is a promising quantum-classical hybrid technique to solve combinatorial optimization problems in near-term gate-based noisy quantum devices. In QAOA, the objective is a function of the quantum state, which itself is a function of the gate parameters of a multi-level parameterized quantum circuit (PQC). A classical optimizer varies the continuous gate parameters to generate distributions (quantum state) with significant support to the optimal solution. Even at the lowest circuit depth, QAOA offers non-trivial provable performance guarantee which is expected to increase with the circuit depth. However, the existing analysis fails to consider non-idealities in the qubit quality i.e., short lifetime and imperfect gate operations in realistic quantum hardware. In this article, we investigate the impact of various noise sources on the performance of QAOA both in simulation and on a real quantum computer from IBM. Our analyses indicate that the optimal number of stages (p-value) for any QAOA instance is limited by the noise characteristics (gate error, coherence time, etc.) of the target hardware as opposed to the current perception that higher-depth QAOA will provide monotonically better performance for a given problem compared to the low-depth implementations.
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?
The effects of noise constitute an optimal depth for QAOA.
“The effects of noise constitute an optimal depth for QAOA [5, 60].”
From Quantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping Study (2024) · cites this paper as [5]
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
Storn, R., & Price, K. (1997) · Journal of Global Optimization · doi:10.1023/a:1008202821328 · Cited by 29,569 · see citing works
Reducibility among Combinatorial Problems
Karp, R. M. (1972) · Complexity of Computer Computations · doi:10.1007/978-1-4684-2001-2_9 · Cited by 11,511 · see citing works
Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets
Kandala, A., Mezzacapo, A., Temme, K., Takita, M., Brink, M., Chow, J. M., & Gambetta, J. M. (2017) · Nature · doi:10.1038/nature23879 · Cited by 2,982 · see citing works
A Quantum Approximate Optimization Algorithm
Farhi, E., Goldstone, J., & Gutmann, S. (2014) · arXiv · doi:10.48550/arxiv.1411.4028 · Cited by 1,789 · see citing works
Optimization, approximation, and complexity classes
Papadimitriou, C. H., & Yannakakis, M. (1991) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(91)90023-x · Cited by 1,653 · see citing works
Zhou, L., Wang, S.-T., Choi, S., Pichler, H., & Lukin, M. D. (2020) · Physical Review X · doi:10.1103/physrevx.10.021067 · Cited by 913 · see citing works
Quantum autoencoders for efficient compression of quantum data
Romero, J., Olson, J. P., & Aspuru-Guzik, A. (2017) · Quantum Science and Technology · doi:10.1088/2058-9565/aa8072 · Cited by 559 · see citing works
Quantum generative adversarial networks
Dallaire-Demers, P.-L., & Killoran, N. (2018) · Physical Review A · doi:10.1103/physreva.98.012324 · Cited by 506 · see citing works
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 · see citing works
Performance of the Quantum Approximate Optimization Algorithm on the Maximum Cut Problem
Crooks, G. E. (2018) · arXiv · doi:10.48550/arxiv.1811.08419 · Cited by 158 · see citing works
Practical optimization for hybrid quantum-classical algorithms
Guerreschi, G. G., & Smelyanskiy, M. (2017) · arXiv · doi:10.48550/arxiv.1701.01450 · Cited by 99 · see citing works
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 · see citing works
Brandao, F. G. S. L., Broughton, M., Farhi, E., Gutmann, S., & Neven, H. (2018) · arXiv · doi:10.48550/arxiv.1812.04170 · Cited by 88 · see citing works
Saki, A. A., Alam, M., & Ghosh, S. (2019) · ACM/IEEE Design Automation Conference (DAC) · doi:10.1145/3316781.3317888 · Cited by 74 · see citing works
Self-citationQuantum Approximate Optimization with Hard and Soft Constraints
Hadfield, S., Wang, Z., Rieffel, E. G., O'Gorman, B., Venturelli, D., & Biswas, R. (2017) · Proceedings of the Second International Workshop on Post Moores Era Supercomputing · doi:10.1145/3149526.3149530 · Cited by 51 · see citing works
Flagged first, then by citations
1 of the 16 references couldn’t be matched to a known paper.
Research works printed but not linked: 2
- [6][6] D. Wecker, M. B. Hastings, and M. Troyer, 'Training a quantum optimizer,' Physical Review A , vol. 94, no. 2, p. 022309, 2016. -
- [11][11] A. Ash-Saki, M. Alam, and S. Ghosh, 'Qure: Qubit re-allocation in noisy intermediate-scale quantum computers,' in Proceedings of the 56th Annual Design Automation Conference 2019 . ACM, 2019, p. 141. -
Cited by
Sorted by citations
A review on Quantum Approximate Optimization Algorithm and its variants
Blekos, K., Brand, D., Ceschini, A., Chou, C.-H., Li, R.-H., Pandya, K., & Summer, A. (2024) · Physics Reports · doi:10.1016/j.physrep.2024.03.002 · Cited by 444 · see citing works
Robust data encodings for quantum classifiers
LaRose, R., & Coyle, B. (2020) · Physical Review A · doi:10.1103/physreva.102.032420 · Cited by 332 · 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
Solving Vehicle Routing Problem Using Quantum Approximate Optimization Algorithm
Azad, U., Behera, B. K., Ahmed, E. A., Panigrahi, P. K., & Farouk, A. (2023) · IEEE Transactions on Intelligent Transportation Systems · doi:10.1109/tits.2022.3172241 · Cited by 149 · see citing works
Multi-angle quantum approximate optimization algorithm
Herrman, R., Lotshaw, P. C., Ostrowski, J., Humble, T. S., & Siopsis, G. (2022) · Scientific Reports · doi:10.1038/s41598-022-10555-8 · Cited by 117 · see citing works
Circuit Compilation Methodologies for Quantum Approximate Optimization Algorithm
Alam, M., Saki, A. A., & Ghosh, S. (2020) · IEEE/ACM International Symposium on Microarchitecture (MICRO) · doi:10.1109/micro50266.2020.00029 · Cited by 76 · see citing works
Self-citationImproving the Performance of Deep Quantum Optimization Algorithms with Continuous Gate Sets
Lacroix, N., Hellings, C., Andersen, C. K., Paolo, A. D., Remm, A., Lazar, S., Krinner, S., Norris, G. J., Gabureac, M. S., Heinsoo, J., et al. (2020) · Repository for Publications and Research Data (ETH Zurich) · doi:10.3929/ethz-b-000464528 · Cited by 59 · see citing works
A study of the performance of classical minimizers in the Quantum Approximate Optimization Algorithm
Fernández-Pendás, M., Combarro, E. F., Vallecorsa, S., Ranilla, J., & Rúa, I. F. (2022) · Journal of Computational and Applied Mathematics · doi:10.1016/j.cam.2021.113388 · Cited by 52 · see citing works
To quantum or not to quantum: towards algorithm selection in near-term quantum optimization
Moussa, C., Calandra, H., & Dunjko, V. (2020) · Quantum Science and Technology · doi:10.1088/2058-9565/abb8e5 · Cited by 50 · see citing works
Noise-resilient variational hybrid quantum-classical optimization
Gentini, L., Cuccoli, A., Pirandola, S., Verrucchi, P., & Banchi, L. (2020) · Physical Review A · doi:10.1103/physreva.102.052414 · Cited by 46 · see citing works
Maciejewski, F. B., Baccari, F., Zimborás, Z., & Oszmaniec, M. (2021) · Quantum · doi:10.22331/q-2021-06-01-464 · Cited by 46 · see citing works
An Efficient Circuit Compilation Flow for Quantum Approximate Optimization Algorithm
Alam, M., Saki, A. A., & Ghosh, S. (2020) · ACM/IEEE Design Automation Conference (DAC) · doi:10.1109/dac18072.2020.9218558 · Cited by 39 · see citing works
Self-citationA practitioner’s guide to quantum algorithms for optimisation problems
Symons, B. C. B., Galvin, D., Sahin, E., Alexandrov, V., & Mensa, S. (2023) · Journal of Physics A Mathematical and Theoretical · doi:10.1088/1751-8121/ad00f0 · Cited by 37 · see citing works
An expressive ansatz for low-depth quantum approximate optimisation
Vijendran, V., Das, A., Koh, D. E., Assad, S. M., & Lam, P. K. (2024) · Quantum Science and Technology · doi:10.1088/2058-9565/ad200a · Cited by 37 · see citing works
Investigating the effect of circuit cutting in QAOA for the MaxCut problem on NISQ devices
Bechtold, M., Barzen, J., Leymann, F., Mandl, A., Obst, J., Truger, F., & Weder, B. (2023) · Quantum Science and Technology · doi:10.1088/2058-9565/acf59c · Cited by 35 · see citing works
Maciejewski, F. B., Baccari, F., Zimborás, Z., & Oszmaniec, M. (2021) · Repository of the Academy's Library (Library of the Hungarian Academy of Sciences) · Cited by 33 · see citing works
The impact of cost function globality and locality in hybrid quantum neural networks on NISQ devices
Kashif, M., & Al-Kuwari, S. M. (2023) · Machine Learning Science and Technology · doi:10.1088/2632-2153/acb12f · Cited by 25 · 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
“Thus, as an example, the optimal depth as a tradeoff between ansatz accuracy and error rates has been found to be p=1 and p=3, respectively [5, 60].”
BackgroundQPack: Quantum Approximate Optimization Algorithms as universal benchmark for quantum computersPreprint
Mesman, K. J., Al-Ars, Z., & Möller, M. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2103.17193 · Cited by 23 · see citing works
Huot, C., Kea, K., Kim, T.-K., & Han, Y. (2024) · IEEE Access · doi:10.1109/access.2024.3506981 · Cited by 14 · see citing works
What do QAOA energies reveal about graphs?Preprint
Szegedy, M. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1912.12277 · Cited by 13 · see citing works
Obfuscating Quantum Hybrid-Classical Algorithms for Security and Privacy
Upadhyay, S., & Ghosh, S. (2024) · International Symposium on Quality Electronic Design (ISQED) · doi:10.1109/isqed60706.2024.10528769 · Cited by 9 · see citing works
Self-citationLi, J., Alam, M., Saki, A. A., & Ghosh, S. (2020) · International Symposium on Quality Electronic Design (ISQED) · doi:10.1109/isqed48828.2020.9136973 · Cited by 9 · see citing works
Self-citationQuantum approximate optimization for hard problems in linear algebra
Borle, A., Elfving, V. E., & Lomonaco, S. J. (2021) · SciPost Physics Core · doi:10.21468/scipostphyscore.4.4.031 · Cited by 32 · see citing works
Resiliency analysis and improvement of variational quantum factoring in superconducting qubit
Qiu, L., Alam, M., Saki, A. A., & Ghosh, S. (2020) · International Symposium on Low Power Electronics and Design (ISLPED) · doi:10.1145/3370748.3406586 · Cited by 7 · see citing works
Self-citationError Analysis of the Variational Quantum Eigensolver Algorithm
Brandhofer, S., Devitt, S. J., & Polian, I. (2021) · IEEE/ACM International Symposium on Nanoscale Architectures (NANOARCH) · doi:10.1109/nanoarch53687.2021.9642249 · Cited by 3 · see citing works
Muñoz‐Coreas, E. (2020) · UKnowledge (University of Kentucky) · doi:10.13023/etd.2020.365 · Cited by 1 · see citing works
Hodson, M. J., Ruck, B., Ong, H., Dulman, S., & Garvin, D. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2008.09505
Report on scipost_202106_00008v2
Borle, A., Elfving, V. E., & Lomonaco, S. J. (2021) · SciPost Physics Core · doi:10.21468/scipost.report.3619
Report on scipost_202106_00008v1
Borle, A., Elfving, V. E., & Lomonaco, S. J. (2021) · SciPost Physics Core · doi:10.21468/scipost.report.3307
Report on scipost_202106_00008v1
Borle, A., Elfving, V. E., & Lomonaco, S. J. (2021) · SciPost Physics Core · doi:10.21468/scipost.report.3409
Feasibility Study of Post Quantum Cryptography in TLS 1.3
Lee, S., & Son, T.-S. (2023) · Journal of Digital Contents Society · doi:10.9728/dcs.2023.24.1.167
Quantum simulations and classical hybrid machine learning
Pawan, Y. V. R. N., & Kolla, B. P. (2025) · Elsevier eBooks · doi:10.1016/b978-0-443-29096-1.00006-4
- Authors
- Alam, M., Ash-Saki, A., & Ghosh, S.
- Affiliations
- Pennsylvania State University (US)
- Venue
- arXiv
- Publisher
- arXiv
- Published
- 2019
- ISSN
- 2331-8422 (ISSN-L)
- arXiv
- 1907.09631
- OpenAlex
- W2963142702
- Cited by
- 33
- References
- 16
- Citations by year
- 2025: 1 · 2024: 4 · 2023: 5 · 2022: 2 · 2021: 10 · 2020: 10 · 2019: 1
- Type
- posted content
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Information and Cryptography
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum many-body systems
- Keywords
- quantum approximate optimization algorithm, superconducting qubits, gate errors, coherence time, variational quantum circuits, circuit depth, combinatorial optimization, hybrid quantum-classical algorithms, IBM quantum hardware
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
