Optimization Applications as Quantum Performance Benchmarks
Open accessThe DOI matches its Crossref record; 31 of the 31 references it cites were found in a registry or an index.
Abstract
Combinatorial optimization is anticipated to be one of the primary use cases for quantum computation in the coming years. The Quantum Approximate Optimization Algorithm and Quantum Annealing can potentially demonstrate significant run-time performance benefits over current state-of-the-art solutions. Inspired by existing methods to characterize classical optimization algorithms, we analyze the solution quality obtained by solving Max-cut problems using gate-model quantum devices and a quantum annealing device. This is used to guide the development of an advanced benchmarking framework for quantum computers designed to evaluate the trade-off between run-time execution performance and the solution quality for iterative hybrid quantum-classical applications. The framework generates performance profiles through compelling visualizations that show performance progression as a function of time for various problem sizes and illustrates algorithm limitations uncovered by the benchmarking approach. As an illustration, we explore the factors that influence quantum computing system throughput, using results obtained through execution on various quantum simulators and quantum hardware systems.
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
Quantum supremacy using a programmable superconducting processor
Arute, F., Arya, K., Babbush, R., Bacon, D., Bardin, J. C., Barends, R., Biswas, R., Boixo, S., Brandao, F. G. S. L., Buell, D. A., et al. (2019) · Nature · doi:10.1038/s41586-019-1666-5 · Cited by 7,720
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 · cited 2×
“QAOA belongs to the class of Variational Quantum Algorithms (VQA) [35] and is usually implemented iteratively wherein a classical optimizer “trains” a parameterized quantum circuit.”
Ising formulations of many NP problems
Lucas, A. (2014) · Frontiers in Physics · doi:10.3389/fphy.2014.00005 · Cited by 2,512
Quantum computational advantage using photons
Zhong, H.-S., Wang, H., Deng, Y.-H., Chen, M.-C., Peng, L.-C., Luo, Y.-H., Qin, J., Wu, D., Ding, X., Hu, Y., et al. (2020) · Science · doi:10.1126/science.abe8770 · Cited by 2,405 · cited 1×
“For example, quantum and classical computing times were central to recent demonstrations of quantum advantage [75, 76].”
Quantum annealing in the transverse Ising model
Kadowaki, T., & Nishimori, H. (1998) · Physical Review E · doi:10.1103/physreve.58.5355 · Cited by 2,339 · cited 3×
“In the emerging world of quantum computing, new techniques for finding solutions to such combinatorial challenges, such as Quantum Annealing (QA) [4, 5] and the Quantum Ap0 0.”
Barren plateaus in quantum neural network training landscapes
McClean, J. R., Boixo, S., Smelyanskiy, V. N., Babbush, R., & Neven, H. (2018) · Nature Communications · doi:10.1038/s41467-018-07090-4 · Cited by 2,329
Some optimal inapproximability results
Håstad, J. (2001) · Journal of the ACM · doi:10.1145/502090.502098 · Cited by 1,902
Quantum annealing with manufactured spins
Johnson, M. W., Amin, M. H. S., Gildert, S., Lanting, T., Hamze, F., Dickson, N., Harris, R., Berkley, A. J., Johansson, J., Bunyk, P., et al. (2011) · Nature · doi:10.1038/nature10012 · Cited by 1,891 · cited 20×
“To this end, we built on the existing open-source QED-C Application-oriented Benchmark suite, enhancing it to support benchmarking of hybrid quantum-classical solutions to combinatorial optimization problems, often cited as a use case for quantum computing.”
InfluentialOptimization, 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
Cost function dependent barren plateaus in shallow parametrized quantum circuits
Cerezo, M., Sone, A., Volkoff, T., Cincio, L., & Coles, P. J. (2021) · Nature Communications · doi:10.1038/s41467-021-21728-w · Cited by 1,047
Randomized benchmarking of quantum gates
Knill, E., Leibfried, D., Reichle, R., Britton, J., Blakestad, R. B., Jost, J. D., Langer, C., Ozeri, R., Seidelin, S., & Wineland, D. J. (2008) · Physical Review A · doi:10.1103/physreva.77.012307 · Cited by 1,019 · cited 1×
“, randomized benchmarking [18, 19] and gate set tomography [20].”
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 · cited 3×
“…combinatorial optimization tasks, even to obtain an approximate solution, i.e., APX-Hard [13, 28], (2) as an unconstrained discrete optimization task, it has a natural encoding as a QUBO [29, 30] or an Ising model [5, 31], ideally fitting current quantum optimization algorithms (QAOA, QA).”
InfluentialNoise-induced barren plateaus in variational quantum algorithms
Wang, S., Fontana, E., Cerezo, M., Sharma, K., Sone, A., Cincio, L., & Coles, P. J. (2021) · Nature Communications · doi:10.1038/s41467-021-27045-6 · Cited by 773
Validating quantum computers using randomized model circuits
Cross, A. W., Bishop, L. S., Sheldon, S., Nation, P. D., & Gambetta, J. M. (2019) · Physical Review A · doi:10.1103/physreva.100.032328 · Cited by 704
Defining and detecting quantum speedup
Rønnow, T. F., Wang, Z., Job, J., Boixo, S., Isakov, S. V., Wecker, D., Martinis, J. M., Lidar, D. A., & Troyer, M. (2014) · Science · doi:10.1126/science.1252319 · Cited by 601
Training Variational Quantum Algorithms Is NP-Hard
Bittel, L., & Kliesch, M. (2021) · Physical Review Letters · doi:10.1103/physrevlett.127.120502 · Cited by 398 · cited 2×
“Finding the optimal angles for QAOA has been shown to be an NP-HARD problem [83].”
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
Demonstration of a Scaling Advantage for a Quantum Annealer over Simulated Annealing
Albash, T., & Lidar, D. A. (2018) · Physical Review X · doi:10.1103/physrevx.8.031016 · Cited by 238 · cited 1×
“The time-to-solution (TTS) metric determines the expected wall-clock time required to solve a problem to optimality [48, 82–85].”
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
SupermarQ: A Scalable Quantum Benchmark Suite
Tomesh, T., Gokhale, P., Omole, V., Ravi, G. S., Smith, K. N., Viszlai, J., Wu, X.-C., Hardavellas, N., Martonosi, M. R., & Chong, F. T. (2022) · arXiv · doi:10.48550/arxiv.2202.11045 · Cited by 143 · cited 2×
“Quantum computation based on quantum annealing techniques has been used to address combinatorial optimization problems for more than a decade [3, 9, 11, 62, 80–83].”
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 · cited 1×
“Throughout this section, we use the terms cut size and energy interchangeably, where energy refers to the eigenvalues of the Hamiltonian in Equation (12).”
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
A deceptive step towards quantum speedup detection
Mandrà, S., & Katzgraber, H. G. (2018) · Quantum Science and Technology · doi:10.1088/2058-9565/aac8b2 · Cited by 82 · cited 1×
“[70] Salvatore Mandrà and Helmut G Katzgraber.”
Benchmarking a quantum annealing processor with the time-to-target metric
King, J., Yarkoni, S., Nevisi, M. M., Hilton, J. P., & McGeoch, C. C. (2015) · arXiv · doi:10.48550/arxiv.1508.05087 · Cited by 77
Self-citationScalable Randomized Benchmarking of Quantum Computers Using Mirror Circuits
Proctor, T., Seritan, S., Rudinger, K., Nielsen, E., Blume-Kohout, R., & Young, K. (2022) · Physical Review Letters · doi:10.1103/physrevlett.129.150502 · Cited by 68
Readiness of Quantum Optimization Machines for Industrial Applications
Perdomo-Ortiz, A., Feldman, A., Ozaeta, A., Isakov, S. V., Zhu, Z., O’Gorman, B., Katzgraber, H. G., Diedrich, A., Neven, H., de Kleer, J., et al. (2019) · Physical Review Applied · doi:10.1103/physrevapplied.12.014004 · Cited by 62
On the emerging potential of quantum annealing hardware for combinatorial optimization
Tasseff, B., Albash, T., Morrell, Z., Vuffray, M., Lokhov, A. Y., Misra, S., & Coffrin, C. (2024) · Journal of Heuristics · doi:10.1007/s10732-024-09530-5 · Cited by 42 · cited 3×
“While these two methods characterize quantum circuit execution quality and scale, neither provides information about the time it takes a program to run, which is a critical factor in evaluating the total cost of any computing solution.”
Self-citationEntanglement-Induced Barren Plateaus
Ortiz Marrero, C., Kieferová, M., & Wiebe, N. (2021) · PRX Quantum · doi:10.1103/prxquantum.2.040316 · Cited by 39
Combinatorial Optimization on Gate Model Quantum Computers: A Survey
Zahedinejad, E., & Zaribafiyan, A. (2017) · arXiv · doi:10.48550/arxiv.1708.05294 · Cited by 29 · cited 3×
“This section provides an overview of the problem’s characteristics and then reviews the quantum solutions we propose to benchmark.”
BackgroundMethodBenchmarking 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
Fast Simulation of High-Depth QAOA Circuits
Lykov, D., Shaydulin, R., Sun, Y., Alexeev, Y., & Pistoia, M. (2023) · Proceedings of the SC '23 Workshops of the International Conference on High Performance Computing, Network, Storage, and Analysis · doi:10.1145/3624062.3624216 · Cited by 27
Cited by
Challenges and opportunities in quantum optimization
Abbas, A., Ambainis, A., Augustino, B., Bärtschi, A., Buhrman, H., Coffrin, C., Cortiana, G., Dunjko, V., Egger, D. J., Elmegreen, B. G., et al. (2024) · Nature Reviews Physics · doi:10.1038/s42254-024-00770-9 · Cited by 201
“Previous work has focused on application-centric quantum-hardware benchmarking frameworks that employ optimization problems as an exemplary use-case 163–166 .”
Self-citationNeutral atom quantum computing hardware: performance and end-user perspective
Wintersperger, K., Dommert, F., Ehmer, T., Hoursanov, A., Klepsch, J., Mauerer, W., Reuber, G., Strohm, T., Yin, M., & Luber, S. (2023) · EPJ Quantum Technology · doi:10.1140/epjqt/s40507-023-00190-1 · Cited by 117
Quantum Optimization Benchmarking Library - The Intractable Decathlon
Koch, T., Neira, D. E. B., Chen, Y., Cortiana, G., Egger, D. J., Heese, R., Hegade, N. N., Cadavid, A. G., Huang, R., Itoko, T., et al. (2025) · arXiv · doi:10.48550/arxiv.2504.03832 · Cited by 5
Counting collisions in random circuit sampling for benchmarking quantum computers
Mari, A. (2024) · APL Quantum · doi:10.1063/5.0219266 · Cited by 2
Metadata
- Authors
- Lubinski, T., Coffrin, C., McGeoch, C., Sathe, P., Apanavicius, J., Bernal Neira, D., & Quantum Economic Development Consortium(QED-C) Collaboration
- Venue
- ACM Transactions on Quantum Computing
- Published
- 2024-08-14
- Volume
- 5
- Issue
- 3
- Pages
- 1-44
- ISSN
- 2643-6809 (ISSN-L)
- 2643-6817
- OpenAlex
- W4400737701
- Cited by
- 59
- References
- 31
- FWCI
- 7.59
- Type
- journal article
- Language
- en
- Open access
- hybrid
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.