CoChat

Challenges and opportunities in quantum optimization

Open access

The DOI matches its Crossref record; 255 of the 255 references it cites were found in a registry or an index.

Abstract

Quantum computers have demonstrable ability to solve problems at a scale beyond brute-force classical simulation. Interest in quantum algorithms has developed in many areas, particularly in relation to mathematical optimization — a broad field with links to computer science and physics. In this Review, we aim to give an overview of quantum optimization. Provably exact, provably approximate and heuristic settings are first explained using computational complexity theory, and we highlight where quantum advantage is possible in each context. Then, we outline the core building blocks for quantum optimization algorithms, define prominent problem classes and identify key open questions that should be addressed to advance the field. We underscore the importance of benchmarking by proposing clear metrics alongside suitable optimization problems, for appropriate comparisons with classical optimization techniques, and discuss next steps to accelerate progress towards quantum advantage in optimization. This Review discusses quantum optimization, focusing on the potential of exact, approximate and heuristic methods, core algorithmic building blocks, problem classes and benchmarking metrics. The challenges for quantum optimization are considered, and next steps are suggested for progress towards achieving quantum advantage. Quantum computing is advancing rapidly, and quantum optimization is a promising area of application. Quantum optimization algorithms — whether provably exact, provably approximate or heuristic — offer opportunities to demonstrate quantum advantage. Systematic benchmarking is crucial to guide research, track progress and further advance understanding of quantum optimization. Theoretical research and empirical research using real hardware can complement each other, in the move towards demonstrating quantum advantage. Quantum computing is advancing rapidly, and quantum optimization is a promising area of application. Quantum optimization algorithms — whether provably exact, provably approximate or heuristic — offer opportunities to demonstrate quantum advantage. Systematic benchmarking is crucial to guide research, track progress and further advance understanding of quantum optimization. Theoretical research and empirical research using real hardware can complement each other, in the move towards demonstrating quantum advantage.

Overview

CoChat Summary

TL;DR

This review provides an overview of quantum optimization, framing where quantum advantage may be possible across exact, approximate, and heuristic settings. It also argues that better benchmarking and clearer metrics are needed to compare quantum and classical optimization fairly.

Key findings

  • The paper states that quantum computers have “demonstrable ability” to solve problems beyond brute-force classical simulation.
  • It distinguishes three settings for quantum optimization: provably exact, provably approximate, and heuristic, and says computational-complexity theory is used to explain where quantum advantage may be possible in each.
  • The review identifies core building blocks of quantum optimization algorithms, defines prominent problem classes, and highlights key open questions to advance the field.
  • The authors emphasize benchmarking as a central need and propose clear metrics and suitable optimization problems for comparison with classical optimization techniques.

Methods

  • Review article, not an original empirical study.
  • The paper synthesizes quantum optimization through computational-complexity theory, algorithmic building blocks, problem classes, and benchmarking considerations.
  • It does not report a study sample or new data; instead, it provides a conceptual overview and agenda for the field.

Limitations

  • The paper itself does not report experimental results or a primary dataset, because it is a review.
  • It implies a field-wide limitation: benchmarking is not yet sufficiently clear or standardized for appropriate comparisons with classical optimization techniques.

Model-written summary. Check it against the paper before relying on it.

Integrity signals

Registry

Crossref · 10.1038/s42254-024-00770-9

Cites

255 of 255 references verified0 citation errors · 0 not checkable

Statistics

Nothing to recompute.

Figures

Figure 1 The inclusions of various complexity classes concerned with decision problems, as discussed in Sec. II. While these inclusions are not known to be strict, this diagram captures the gist of prominent, canonical classes in complexity theory.
Figure 1 The inclusions of various complexity classes concerned with decision problems, as discussed in Sec. II. While these inclusions are not known to be strict, this diagram captures the gist of prominent, canonical classes in complexity theory.From the PDF
Figure 2 Complexity classes for optimization problems. Notice that, similar to # P , the functional problem classes are outside of the decision problems, and hence, not displayed in this hierarchy.
Figure 2 Complexity classes for optimization problems. Notice that, similar to # P , the functional problem classes are outside of the decision problems, and hence, not displayed in this hierarchy.From the PDF
Figure 3 Variational methods iterate between the evaluation of empirical estimates of the expectations of a set of observables { O k } associated with a parameterized quantum circuit, and classical computation of updated parameters for the parameterized quantum circuit.
Figure 3 Variational methods iterate between the evaluation of empirical estimates of the expectations of a set of observables { O k } associated with a parameterized quantum circuit, and classical computation of updated parameters for the parameterized quantum circuit.From the PDF
Figure 4 Structure of QAOA ansatz: every layer consists of a mixing and a problem unitary with corresponding parameters γ j and β j for layer j = 1 , . . . , p .
Figure 4 Structure of QAOA ansatz: every layer consists of a mixing and a problem unitary with corresponding parameters γ j and β j for layer j = 1 , . . . , p .From the PDF
Figure 5 High-level summary of the quantum stack. (a) A quantum algorithm, including an encoding of decision variables in qubits and any hardware-guided problem simplifications, results in a high-level quantum circuit. (b) The instructions in this circuit are then transpiled to hardware native instructions. (c) Error mitigation methods, such as PEC, are often encoded as circuit instructions. (d) At the pulse-level, circuit instructions are represented by the physical pulses that are played on the qubits. (e) Finally, the circuit is compiled into machine-executable waveforms, (f) that are run on the quantum processor.
Figure 5 High-level summary of the quantum stack. (a) A quantum algorithm, including an encoding of decision variables in qubits and any hardware-guided problem simplifications, results in a high-level quantum circuit. (b) The instructions in this circuit are then transpiled to hardware native instructions. (c) Error mitigation methods, such as PEC, are often encoded as circuit instructions. (d) At the pulse-level, circuit instructions are represented by the physical pulses that are played on the qubits. (e) Finally, the circuit is compiled into machine-executable waveforms, (f) that are run on the quantum processor.From the PDF
Figure 6 The figure illustrates the time it takes the Gurobi solver [482] to find the optimal solution for MIPLIB 2017 [467] instances of the form min x c T x subject to Ax ≤ b , x being partly integer. The size of the circles depicts the number of non-zero coefficients in the constraint matrix A and the instances are ordered (on the x-axis) according to the square root of the number of variables times the number of constraints.
Figure 6 The figure illustrates the time it takes the Gurobi solver [482] to find the optimal solution for MIPLIB 2017 [467] instances of the form min x c T x subject to Ax ≤ b , x being partly integer. The size of the circles depicts the number of non-zero coefficients in the constraint matrix A and the instances are ordered (on the x-axis) according to the square root of the number of variables times the number of constraints.From the PDF
Figure 7 Sketch of the optimization platform ecosystem. We focus on digital classical computing as well as digital and analog quantum computing.
Figure 7 Sketch of the optimization platform ecosystem. We focus on digital classical computing as well as digital and analog quantum computing.From the PDF
Figure 8 An illustration of the optimal asset allocation at time t 0 (model definition), considering perfect predictors of asset valuation at the end of investment horizon t 1 given prior statistics ω 1 , ω 2 , . . . (level 1), then taking uncertainties of these predictors into account but still with a limited view until t 1 (level 2), before anticipating a multi-period allocation strategy and respective uncertainties beyond t 1 (level 3).
Figure 8 An illustration of the optimal asset allocation at time t 0 (model definition), considering perfect predictors of asset valuation at the end of investment horizon t 1 given prior statistics ω 1 , ω 2 , . . . (level 1), then taking uncertainties of these predictors into account but still with a limited view until t 1 (level 2), before anticipating a multi-period allocation strategy and respective uncertainties beyond t 1 (level 3).From the PDF
Figure 9 Illustrating a possible instance for the problem of scheduling the charging of EVs in a parking site (use case 1).
Figure 9 Illustrating a possible instance for the problem of scheduling the charging of EVs in a parking site (use case 1).From the PDF

Verification

Claims the paper makes

0 Valid · 3 Not valid · 0 Not checked · 9 Own results and interpretations

7 more claims

Create a free account to see all 12 claims and every source verdict.

See all claims — free account

Citations

Cites

Show all 255 references

Research works printed but not linked: 26

  1. Applegate, D. L., Bixby, R. E., Chvátal, V. & Cook, W. J. On the solution of traveling salesman problems. Doc. Math. 3, 645–656 (1998).
  2. Cook, W. J. In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation (Princeton Univ. Press, 2012).
  3. Crama, Y., Elloumi, S., Lambert, A. & Rodriguez-Heck, E. Quadratization and convexification in polynomial binary optimization. Preprint at https://hal.science/hal-03795395 (2022).
  4. Chou, C.-N., Love, P. J., Sandhu, J. S. & Shi, J. Limitations of local quantum algorithms on random MAX-k-XOR and beyond. In Proc. 49th International Colloquium on Automata, Languages, and Programming (eds Bojańczyk, M. et al.) 41:1–41:20 (Leibniz International Proceedings in Informatics, 2022).
  5. Garg, A., Kothari, R., Netrapalli, P. & Sherif, S. No quantum speedup over gradient descent for non-smooth convex optimization. In Proc. 12th Innovations in Theoretical Computer Science Conference (Leibniz International Proceedings in Informatics, 2021).
  6. Garg, A., Kothari, R., Netrapalli, P. & Sherif, S. Near-optimal lower bounds for convex optimization for all orders of smoothness. In Proc. Advances in Neural Information Processing Systems 34 (eds Ranzato, M. et al.) 29874–29884 (NeurIPS, 2021).
  7. Grötschel, M., Lovász, L. & Schrijver, A. Geometric Algorithms and Combinatorial Optimization Vol. 2 (Springer, 2012).
  8. Brandão, F. G. S. L. et al. Quantum SDP solvers: large speed-ups, optimality, and applications to quantum learning. In Proc. 46th International Colloquium on Automata, Languages, and Programming (eds Baier, C. et al.) 27 (Leibniz International Proceedings in Informatics, 2019).
  9. van Apeldoorn, J. & Gilyén, A. Improvements in quantum SDP-solving with applications. In Proc. 46th International Colloquium on Automata, Languages, and Programming (Leibniz International Proceedings in Informatics, 2019).
  10. van Apeldoorn, J. A Quantum View on Convex Optimization. PhD thesis, Univ. Amsterdam (2020).
  11. Chakraborty, S., Gilyén, A. & Jeffery, S. The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation. In Proc. 46th International Colloquium on Automata, Languages, and Programming 33:1–33:14 (Leibniz International Proceedings in Informatics, 2019).
  12. Zhang, C. & Li, T. Quantum lower bounds for finding stationary points of nonconvex functions. In International Conference on Machine Learning 41268–41299 (PMLR, 2023).
  13. Gambella, C., Simonetto, A., Mevissen, M. & Marecek, J. Mixed-binary constrained optimization on quantum computers. US patent 16/395,560 (2020).
  14. Bertsekas, D. P. Constrained Optimization and Lagrange Multiplier Methods (Academic Press, 2014).
  15. Gaspers, S. & Li, J. Z. Quantum algorithms for graph coloring and other partitioning, covering, and packing problems. In Proc. 51st International Colloquium on Automata, Languages, and Programming 69:1–69:20 (Leibniz International Proceedings in Informatics, 2024).
  16. Kļevickis, V., Prūsis, K. & Vihrovs, J. Quantum speedups for treewidth. In Proc. 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (eds Gall, F. L. & Morimae, T.) 11:1–11:18 (Leibniz International Proceedings in Informatics, 2022).
  17. Cornelissen, A. J. Quantum gradient estimation and its application to quantum reinforcement learning. Master thesis, TU Delft (2018).
  18. Jerbi, S., Cornelissen, A., Ozols, M. & Dunjko, V. Quantum policy gradient algorithms. In Proc. 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (eds Fawzi, O. & Walter, M.) 13:1–13:24 (Leibniz International Proceedings in Informatics, 2023).
  19. Jerbi, S., Gyurik, C., Marshall, S., Briegel, H. & Dunjko, V. Parametrized quantum policies for reinforcement learning. In Proc. Advances in Neural Information Processing Systems (eds Ranzato, M. et al.) 28362–28375 (NeurIPS, 2021).
  20. Jain, R. The Art of Computer Systems Performance Analysis: Techniques for Experimental Design, Measurement, Simulation, and Modeling (Wiley, 1991).
  21. Müller, M., Whitney, B., Henschel, R. & Kumaran, K. in Encyclopedia of Parallel Computing (ed. Padua, D.) 1886–1893 (Springer, 2011).
  22. Applegate, D. L., Bixby, R. E., Chvatál, V. & Cook, W. J. The Traveling Salesman Problem: A Computational Study (Princeton Univ. Press, 2006).
  23. Tsukamoto, S., Takatsu, M., Matsubara, S. & Tamura, H. An accelerator architecture for combinatorial optimization problems. Fujitsu Sci. Tech. J. 53, 8–13 (2017).
  24. Nocedal, J. & Wright, S. J. Numerical Optimization 2nd edn (Springer, 2006).
  25. Bonnans, J., Gilbert, J., Lemarechal, C. & Sagastizábal, C. Numerical Optimization: Theoretical and Practical Aspects (Springer, 2006).
  26. Nielsen, M. A. & Chuang, I. L. Quantum Computation and Quantum Information (Cambridge Univ. Press, 2000).

Cited by

See all 201

Metadata

Authors
Abbas, A., Ambainis, A., Augustino, B., Bärtschi, A., Buhrman, H., Coffrin, C., Cortiana, G., Dunjko, V., Egger, D. J., Elmegreen, B. G., Franco, N., Fratini, F., Fuller, B., Gacon, J., Gonciulea, C., Gribling, S., Gupta, S., Hadfield, S., Heese, R., Kircher, G., Kleinert, T., Koch, T., Korpas, G., Lenk, S., Marecek, J., Markov, V., Mazzola, G., Mensa, S., Mohseni, N., Nannicini, G., O’Meara, C., Tapia, E. P., Pokutta, S., Proissl, M., Rebentrost, P., Sahin, E., Symons, B. C. B., Tornow, S., Valls, V., Woerner, S., Wolf-Bauwens, M. L., Yard, J., Yarkoni, S., Zechiel, D., Zhuk, S., & Zoufal, C.
Affiliations
  • QuSoft (NL)
  • University of Latvia (LV)
  • Massachusetts Institute of Technology (US)
  • Los Alamos National Laboratory (US)
  • Centrum Wiskunde & Informatica (NL)
  • E.ON (Germany) (DE)
  • Leiden University (NL)
  • IBM Research - Zurich (CH)
  • IBM (United States) (US)
  • Fraunhofer Institute for Cognitive Systems (DE)
  • Wells Fargo (United States) (US)
  • Tilburg University (NL)
  • Ames Research Center (US)
  • Fraunhofer Institute for Industrial Mathematics (DE)
  • Zuse Institute Berlin (DE)
  • Athena Research and Innovation Center In Information Communication & Knowledge Technologies (GR)
  • Deutsches Zentrum für Luft- und Raumfahrt e. V. (DLR) (DE)
  • University of Zurich (CH)
  • Science and Technology Facilities Council (GB)
  • University of Southern California (US)
  • Centre for Quantum Technologies (SG)
  • Universität der Bundeswehr München (DE)
  • IBM (Ireland) (IE)
  • University of Waterloo (CA)
  • Data:Lab Munich (Germany) (DE)
Venue
Nature Reviews Physics
Published
2024-10-28
Volume
6
Issue
12
Pages
718-735
ISSN
2522-5820 (ISSN-L)
OpenAlex
W4403834027
Cited by
201
References
228
Citations by year
2026: 83 · 2025: 115 · 2024: 3
FWCI
6.87
Type
journal article
Language
en
Licence
Locations
  • Nature Reviews Physics (publishedVersion)
  • Research portal (Tilburg University) (publishedVersion, other-oa)
  • UvA-DARE (University of Amsterdam) (publishedVersion, cc-by)
  • elib (German Aerospace Center) (acceptedVersion)
  • arXiv (Cornell University) (submittedVersion, cc-by)
  • Centrum Wiskunde & Informatica (CWI), the national research institute for mathematics and computer science in the Netherlands (submittedVersion)
  • RePEc: Research Papers in Economics (submittedVersion)
  • HAL (submittedVersion)
  • Leiden Repository (Leiden University) (submittedVersion)
  • SDL (submittedVersion)
  • Fraunhofer-Publica (Fraunhofer-Gesellschaft) (submittedVersion, cc-by)
  • Fraunhofer-Publica (Fraunhofer-Gesellschaft) (submittedVersion)
  • Science and Technology Facilities Council (submittedVersion)
  • arXiv (Cornell University) (cc-by)
Funders
  • National Science Foundation (2229099)
  • Amazon Web Services
  • Innovation, Science and Economic Development Canada
  • Government of Canada
  • National Research Foundation
  • National Research Foundation Singapore
  • Institut Périmètre de physique théorique
  • Natural Sciences and Engineering Research Council of Canada (rgpin-2018-04742, ALLRP-569582-21, 04742, RGPIN 2018)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Physical Sciences › Computer Science › Artificial Intelligence › Metaheuristic Optimization Algorithms Research
  • Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Information and Cryptography
Keywords
quantum optimization, quantum advantage, quantum algorithms, heuristic optimization, benchmarking metrics, problem classes, combinatorial optimization

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.

A language model drew the claims from the paper on 2026-09-25 (prompt extract-v1).

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

How to cite

Cite CoChat for the checks on this page, and the paper for its own findings.

This page
CoChat. (2026). Citation check: Challenges and opportunities in quantum optimization. https://app.cochat.ai/papers/10.1038/s42254-024-00770-9
The paper
Abbas, A., Ambainis, A., Augustino, B., Bärtschi, A., Buhrman, H., Coffrin, C., Cortiana, G., Dunjko, V., Egger, D. J., Elmegreen, B. G., Franco, N., Fratini, F., Fuller, B., Gacon, J., Gonciulea, C., Gribling, S., Gupta, S., Hadfield, S., Heese, R., . . . Zoufal, C. (2024). Challenges and opportunities in quantum optimization. Nature Reviews Physics. https://doi.org/10.1038/s42254-024-00770-9

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.