Fast Simulation of High-Depth QAOA Circuits
Open accessAbstract
Until high-fidelity quantum computers with a large number of qubits become widely available, classical simulation remains a vital tool for algorithm design, tuning, and validation. We present a simulator for the Quantum Approximate Optimization Algorithm (QAOA). Our simulator is designed with the goal of reducing the computational cost of QAOA parameter optimization and supports both CPU and GPU execution. Our central observation is that the computational cost of both simulating the QAOA state and computing the QAOA objective to be optimized can be reduced by precomputing the diagonal Hamiltonian encoding the problem. We reduce the time for a typical QAOA parameter optimization by eleven times for n = 26 qubits compared to a state-of-the-art GPU quantum circuit simulator based on cuQuantum. Our simulator is available on GitHub: https://github.com/jpmorganchase/QOKit
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?
Tensor network techniques do not provide a benefit in this case since the circuit we simulate is deep and fully connected.
“We note in particular that tensor network techniques do not provide a benefit in this case since the circuit we simulate is deep and fully connected [see (22) for detailed comparison].”
From Evidence of scaling advantage for the quantum approximate optimization algorithm on a classically intractable problem (2024) · cites this paper as [22]
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
<i>Quantum Computation and Quantum Information</i>
Nielsen, M. A., Chuang, I., & Grover, L. K. (2002) · American Journal of Physics · doi:10.1119/1.1463744 · Cited by 21,895 · see citing works
Quantum Mechanics Helps in Searching for a Needle in a Haystack
Grover, L. K. (1997) · Physical Review Letters · doi:10.1103/physrevlett.79.325 · Cited by 4,306 · cited 1× · see citing works
“the ability of quantum computers to efficiently perform Walsh-Hadamard transform [8], [9], which is the central building block for the famed Grover’s algorithm [10], was the inspiration for the definition of the QAOA mixer [3].”
MethodA 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
Qiskit/qiskit-metapackage: Qiskit 0.43.0
Gambetta, J., Treinish, M., Kassebaum, P., Rodríguez, D. M., De La Puente González, S., Hu, S., Javadi-Abhari, A., Azaustre, C., Pistoia, M., Scholten, T. L., et al. (2019) · Zenodo (CERN European Organization for Nuclear Research) · doi:10.5281/zenodo.2573505 · Cited by 388 · see citing works
Self-citationBrassard, G., Høyer, P., & Tapp, A. (1998) · Lecture notes in computer science · doi:10.1007/bfb0055105 · Cited by 322 · see citing works
Hyper-optimized tensor network contraction
Gray, J., & Kourtis, S. (2021) · Quantum · doi:10.22331/q-2021-03-15-410 · Cited by 216 · see citing works
qHiPSTER: The Quantum High Performance Software Testing EnvironmentPreprint
Smelyanskiy, M., Sawaya, N. P. D., & Aspuru‐Guzik, A. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1601.07195 · Cited by 173 · see citing works
Advanced Simulation of Quantum Computations
Zulehner, A., & Wille, R. (2018) · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · doi:10.1109/tcad.2018.2834427 · Cited by 159 · see citing works
Quantum annealing initialization of the quantum approximate optimization algorithm
Sack, S. H., & Serbyn, M. (2021) · Quantum · doi:10.22331/q-2021-07-01-491 · Cited by 145 · see citing works
Full-state quantum circuit simulation by using data compression
Wu, X.-C., Di, S., Dasgupta, E. M., Cappello, F., Finkel, H., Alexeev, Y., & Chong, F. T. (2019) · International Conference for High Performance Computing, Networking, Storage and Analysis (SC) · doi:10.1145/3295500.3356155 · Cited by 132 · see citing works
Self-citationPerformance Analysis of MPI Collective Operations
Pjesivac-Grbovic, J., Angskun, T., Bosilca, G., et al. (2005) · Proceedings - IEEE International Parallel and Distributed Processing Symposium · doi:10.1109/ipdps.2005.335 · Cited by 124 · see citing works
Advanced Equivalence Checking for Quantum Circuits
Burgholzer, L., & Wille, R. (2020) · Springer eBooks · doi:10.1007/978-3-032-06770-8_14 · Cited by 112 · see citing works
Hogg, T. (2000) · Physical Review A · doi:10.1103/physreva.61.052311 · Cited by 70 · see citing works
heFFTe: Highly Efficient FFT for Exascale
Ayala, A., Tomov, S. Z., Haidar, A., et al. (2020) · Lecture notes in computer science · doi:10.1007/978-3-030-50371-0_19 · Cited by 60 · see citing works
Classical symmetries and the Quantum Approximate Optimization Algorithm
Shaydulin, R., Hadfield, S., Hogg, T., & Safro, I. (2021) · Quantum Information Processing · doi:10.1007/s11128-021-03298-4 · Cited by 60 · see citing works
Self-citationPan, F. P., Zhou, P., Li, S., & Zhang, P. (2020) · Physical Review Letters · doi:10.1103/physrevlett.125.060503 · Cited by 58 · see citing works
Tensor Network Quantum Simulator With Step-Dependent Parallelization
Lykov, D., Schutski, R., Galda, A., Vinokur, V. M., & Alexeev, Y. (2022) · IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce53715.2022.00081 · Cited by 52 · see citing works
Self-citationExploiting 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
Self-citationLykov, D., Wurtz, J., Poole, C., Saffman, M. E., Noel, T., & Alexeev, Y. (2023) · npj Quantum Information · doi:10.1038/s41534-023-00718-4 · Cited by 37 · see citing works
Self-citationQAOAKit: 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 · cited 2× · see citing works
“On the other hand, there exist simulation libraries that focus on the quantum side and delegate the concern of low-level performance to other libraries [18], [19].”
BackgroundMethodSelf-citationHogg, T., MOCHON, C., Polak, W., & Rieffel, E. G. (1999) · International Journal of Modern Physics C · doi:10.1142/s0129183199001108 · Cited by 27 · see citing works
Adaptive algorithm for quantum circuit simulation
Schutski, R., Lykov, D., & Oseledets, I. V. (2020) · Physical Review A · doi:10.1103/physreva.101.042335 · Cited by 27 · see citing works
Self-citationQuantum simulation with just-in-time compilation
Efthymiou, S., Lazzarin, M., Pasquale, A., & Carrazza, S. (2022) · Quantum · doi:10.22331/q-2022-09-22-814 · Cited by 27 · see citing works
AccFFT: A library for distributed-memory FFT on CPU and GPU architecturesPreprint
Gholami, A., Hill, J. C., Malhotra, D., et al. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1506.07933 · Cited by 25 · see citing works
Simulations of Quantum Circuits with Approximate Noise using qsim and CirqPreprint
Isakov, S. V., Kafri, D., Martin, O., Heidweiller, C. V., Mruczkiewicz, W., Harrigan, M. P., Rubin, N. C., Thomson, R., Broughton, M., Kissell, K., et al. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2111.02396 · Cited by 19 · see citing works
Importance of Diagonal Gates in Tensor Network Simulations
Lykov, D., & Alexeev, Y. (2021) · IEEE Computer Society Annual Symposium on VLSI · doi:10.1109/isvlsi51109.2021.00088 · Cited by 17 · see citing works
Self-citationSolving boolean satisfiability problems with the quantum approximate optimization algorithmPreprint
Boulebnane, S., & Montanaro, A. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2208.06909 · Cited by 12 · see citing works
Constructing Optimal Contraction Trees for Tensor Network Quantum Circuit Simulation
Ibrahim, C., Lykov, D., He, Z., et al. (2022) · IEEE High Performance Extreme Computing Conference · doi:10.1109/hpec55821.2022.9926353 · Cited by 10 · see citing works
Self-citationA Visual Guide to MPI All-to-all
Netterville, N., Fan, K., Kumar, S., et al. (2022) · IEEE International Conference on High Performance Computing, Data and Analytics Workshop (HiPCW) · doi:10.1109/hipcw57629.2022.00008 · Cited by 9 · see citing works
Accelerating Multi - Process Communication for Parallel 3-D FFT
Ayala, A., Tomov, S. Z., Stoyanov, M., et al. (2021) · doi:10.1109/exampi54564.2021.00011 · Cited by 4 · see citing works
cuQuantum SDK: A High-Performance Library for Accelerating Quantum SciencePreprint
Bayraktar, H. H., Charara, A., Clark, D., et al. (2023) · arXiv (Cornell University) · doi:10.48550/arxiv.2308.01999 · Cited by 3 · see citing works
OpenQAOA -- An SDK for QAOAPreprint
Sharma, V., Saharan, N. S. B., Chiew, S.-H., Chiacchio, E. I. R., Disilvestro, L., Demarie, T. F., & Munro, E. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2210.08695 · Cited by 2 · see citing works
A Parameter Setting Heuristic for the Quantum Alternating Operator AnsatzPreprint
Sud, J., Hadfield, S., Rieffel, E. G., et al. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2211.09270 · Cited by 1 · see citing works
Flagged first, then by citations
Research works printed but not linked: 6
- A. Fabrikant and T. Hogg, "Graph coloring with quantum heuristics," in Proceedings of the Eighteenth National Confer- ence on Artificial Intelligence and Fourteenth Conference on Innovative Applications of Artificial Intelligence, R. Dechter, M. J. Kearns, and R. S. Sutton, Eds. AAAI Press / The MIT Press, 2002, pp. 22-27.
- Z. A. E. M. Dahi, E. Alba, R. Gil-Merino, F. Chicano, and G. Luque, "A survey on quantum computer simulators," 2023. [Online]. Available: https://api.semanticscholar.org/CorpusID: 259257304
- T. Khakhulin, R. Schutski, and I. Oseledets, "Learning elimination ordering for tree decomposition problem," in Learning Meets Combinatorial Algorithms at NeurIPS2020, 2020. [Online]. Available: https://openreview.net/forum?id= aZ7wAnYs9v1
- E. Meirom, H. Maron, S. Mannor, and G. Chechik, "Optimizing tensor network contraction using reinforcement learning," in International Conference on Machine Learning. PMLR, 2022, pp. 15 278-15 292.
- J. Gray and S. Kourtis, "Hyper-optimized tensor network contraction," p. 410, Mar. 2021. [Online]. Available: https: //doi.org/10.22331/q-2021-03-15-410 · DOI
- M. Broughton, G. Verdon, T. McCourt, A. J. Martinez, J. H. Yoo, S. V. Isakov, P. Massey, R. Halavati, M. Y. Niu, A. Zlokapa, E. Peters, O. Lockwood, A. Skolik, S. Jerbi, V. Dunjko, M. Leib, M. Streif, D. Von Dollen, H. Chen, S. Cao, R. Wiersema, H.-Y. Huang, J. R. McClean, R. Babbush, S. Boixo, D. Bacon, A. K. Ho, H. Neven, and M. Mohseni, "Tensorflow quantum: A software framework for quantum machine learning," arXiv:2003.02989, 2020. [Online]. Available: 2003.02989 · arXiv
Cited by
Sorted by citations
Shaydulin, R., Li, C., Chakrabarti, S., DeCross, M., Herman, D., Kumar, N., Larson, J., Lykov, D., Minssen, P., Sun, Y., et al. (2024) · Science Advances · doi:10.1126/sciadv.adm6761 · Cited by 120 · see citing works
“Our results are enabled by a custom algorithm-specific GPU simulator (22), which we execute using up to 1,024 GPUs per simulation on the Polaris supercomputer accessed through the Argonne Leadership Computing Facility.”
MethodInfluentialSelf-citation
- Authors
- Lykov, D., Shaydulin, R., Sun, Y., Alexeev, Y., & Pistoia, M.
- Affiliations
- Argonne National Laboratory (US)
- JPMorgan Chase & Co (United States) (US)
- Venue
- Proceedings of the SC '23 Workshops of the International Conference on High Performance Computing, Network, Storage, and Analysis
- Publisher
- ACM
- Published
- 2023-11-12
- Pages
- 1443-1451
- ISSN
- 2167-4337 (ISSN-L)
- OpenAlex
- W4388581244
- Cited by
- 27
- References
- 34
- Citations by year
- 2026: 4 · 2025: 11 · 2024: 10 · 2023: 2
- FWCI
- 4.78
- Type
- conference paper
- Language
- en
- Open access
- bronze
- doi.org
- Locations
- International Conference for High Performance Computing, Networking, Storage and Analysis (SC) (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Funders
- Department of Energy Office of Science (DE-AC02-06CH11357)
- 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 › Hardware and Architecture › Parallel Computing and Optimization Techniques
- Keywords
- quantum approximate optimization algorithm, quantum circuit simulation, GPU acceleration
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
