Challenges and opportunities in quantum optimization
Open accessThe 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
Cites
Statistics
Figures





![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.](https://figures.cochat.ai/paper-figures/53c52792efdb48fd9fca9e2afba13e8a/challenges-and-opportunities-in-quantum-optimization-figure-6.png)



Verification
Claims the paper makes
0 Valid · 3 Not valid · 0 Not checked · 9 Own results and interpretations
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“and identify key open questions that should be addressed to advance the field.”
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“and we highlight where quantum advantage is possible in each context.”
The paper states this without a source or data behind it here, so there is nothing to check it against. The quote shows it is in the paper.
In the paper
“We underscore the importance of benchmarking”
What the paper did — it cites no source for this, so there is none to check. The quote shows it is in the paper.
In the paper
“Then, we outline the core building blocks for quantum optimization algorithms,”
What the paper did — it cites no source for this, so there is none to check. The quote shows it is in the paper.
In the paper
“define prominent problem classes”
7 more claims
Create a free account to see all 12 claims and every source verdict.
Citations
Cites
Stochastic relaxation, gibbs distributions, and the bayesian restoration of images.
Geman, S., & Geman, D. (1984) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.1984.4767596 · Cited by 17,949 · cited 1×
“Gibbs sampling generates sample sequences from complex probability distributions, for example, by using a Markov-chain Monte Carlo algorithm 242 .”
A fast quantum mechanical algorithm for database search
Grover, L. K. (1996) · Proceedings of the twenty-eighth annual ACM symposium on Theory of computing - STOC '96 · doi:10.1145/237814.237866 · Cited by 8,830 · cited 2×
“Grover’s search 1 , quantum annealing, adiabatic quantum optimization 2,3 and the quantum approximate optimization algorithm (QAOA) 4 provided a promising start, but it has become clear that more is needed to realize a practical quantum advantage in optimization.”
Algorithms for quantum computation: discrete logarithms and factoring
Shor, P. W. (2002) · Proceedings 35th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1994.365700 · Cited by 8,713 · cited 1×
“Shor’s algorithm 239 leverages QPE to achieve an exponential speedup over the best-known classical algorithms for factoring and related problems 222,223 .”
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×
“VQAs are a family of search algorithms, originally proposed for quantum chemistry applications 255 , which utilize parameterized quantum states and cost functions to iteratively optimize parameters and find good solutions 4,256–258 .”
Goemans, M. X., & Williamson, D. P. (1995) · Journal of the ACM · doi:10.1145/227683.227684 · Cited by 3,587 · cited 2×
“For instance, semidefinite programming relaxations — as used in the famous Goemans-Williamson algorithm for the maximum-cut problem 64,253 or in more general variants for the quadratic unconstrained binary optimization problem 254 — may profit from quantum semidefinite-programming solvers.”
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
Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bellman Equations
Bardi, M., & Capuzzo-Dolcetta, I. (1997) · Birkhäuser Boston eBooks · doi:10.1007/978-0-8176-4755-1 · Cited by 2,758
Ising formulations of many NP problems
Lucas, A. (2014) · Frontiers in Physics · doi:10.3389/fphy.2014.00005 · Cited by 2,512 · cited 6×
“In the case that certain groups of decision variables are not correlated, QUBOs can be decomposed trivially into smaller sub-QUBOs to be solved independently.”
InfluentialGlobal Optimization with Polynomials and the Problem of Moments
Lasserre, J. B. (2001) · SIAM Journal on Optimization · doi:10.1137/s1052623400366802 · Cited by 2,474 · cited 1×
“Similarly, using moment or sum-of-squares techniques 134,135 , MIP can be reformulated to infinite-dimensional linear programming, with an SDP relaxation in a dimension much higher than n + d and sometimes 136 exponential in n + d .”
Probing many-body dynamics on a 51-atom quantum simulator
Bernien, H., Schwartz, S., Keesling, A., Levine, H., Omran, A., Pichler, H., Choi, S., Zibrov, A. S., Endres, M., Greiner, M., et al. (2017) · Nature · doi:10.1038/nature24622 · Cited by 2,460
Research works printed but not linked: 26
- 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).
- Cook, W. J. In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation (Princeton Univ. Press, 2012).
- Crama, Y., Elloumi, S., Lambert, A. & Rodriguez-Heck, E. Quadratization and convexification in polynomial binary optimization. Preprint at https://hal.science/hal-03795395 (2022).
- 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).
- 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).
- 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).
- Grötschel, M., Lovász, L. & Schrijver, A. Geometric Algorithms and Combinatorial Optimization Vol. 2 (Springer, 2012).
- 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).
- 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).
- van Apeldoorn, J. A Quantum View on Convex Optimization. PhD thesis, Univ. Amsterdam (2020).
- 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).
- Zhang, C. & Li, T. Quantum lower bounds for finding stationary points of nonconvex functions. In International Conference on Machine Learning 41268–41299 (PMLR, 2023).
- Gambella, C., Simonetto, A., Mevissen, M. & Marecek, J. Mixed-binary constrained optimization on quantum computers. US patent 16/395,560 (2020).
- Bertsekas, D. P. Constrained Optimization and Lagrange Multiplier Methods (Academic Press, 2014).
- 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).
- 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).
- Cornelissen, A. J. Quantum gradient estimation and its application to quantum reinforcement learning. Master thesis, TU Delft (2018).
- 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).
- 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).
- Jain, R. The Art of Computer Systems Performance Analysis: Techniques for Experimental Design, Measurement, Simulation, and Modeling (Wiley, 1991).
- Müller, M., Whitney, B., Henschel, R. & Kumaran, K. in Encyclopedia of Parallel Computing (ed. Padua, D.) 1886–1893 (Springer, 2011).
- Applegate, D. L., Bixby, R. E., Chvatál, V. & Cook, W. J. The Traveling Salesman Problem: A Computational Study (Princeton Univ. Press, 2006).
- Tsukamoto, S., Takatsu, M., Matsubara, S. & Tamura, H. An accelerator architecture for combinatorial optimization problems. Fujitsu Sci. Tech. J. 53, 8–13 (2017).
- Nocedal, J. & Wright, S. J. Numerical Optimization 2nd edn (Springer, 2006).
- Bonnans, J., Gilbert, J., Lemarechal, C. & Sagastizábal, C. Numerical Optimization: Theoretical and Practical Aspects (Springer, 2006).
- Nielsen, M. A. & Chuang, I. L. Quantum Computation and Quantum Information (Cambridge Univ. Press, 2000).
Cited by
Rishiwal, V., Agarwal, U., Yadav, M., Tanwar, S., Garg, D., & Guizani, M. (2025) · IEEE Internet of Things Journal · doi:10.1109/jiot.2025.3535414 · Cited by 79
“For example, QML can enhance the routing efficiency in intelligent transportation systems or optimize energy usage in smart grids, leading to more sustainable and efficient IoT operations [92], [93].”
Towards large-scale quantum optimization solvers with few qubits
Sciorilli, M., Borges, L., Patti, T. L., García-Martín, D., Camilo, G., Anandkumar, A., & Aolita, L. (2025) · Nature Communications · doi:10.1038/s41467-024-55346-z · Cited by 47
Quinton, F. A., Myhr, P. A. S., Barani, M., Crespo del Granado, P., & Zhang, H. (2025) · Scientific Reports · doi:10.1038/s41598-025-96220-2 · Cited by 46
Demonstration of Weighted-Graph Optimization on a Rydberg-Atom Array Using Local Light Shifts
de Oliveira, A. G., Diamond-Hitchcock, E., Walker, D. M., Wells-Pestell, M. T., Pelegrí, G., Picken, C., Malcolm, G. P. A., Daley, A. J., Bass, J., & Pritchard, J. D. (2025) · PRX Quantum · doi:10.1103/prxquantum.6.010301 · Cited by 51
Quantum approximate multi-objective optimization
Kotil, A., Pelofske, E., Riedmüller, S., Egger, D. J., Eidenbenz, S., Koch, T., & Woerner, S. (2025) · Nature Computational Science · doi:10.1038/s43588-025-00873-y · Cited by 63
Self-citation
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)
- ORCID
- Abbas, Amira
- Ambainis, Andris
- Augustino, Brandon
- Bärtschi, Andreas
- Coffrin, Carleton
- Cortiana, Giorgio
- Dunjko, Vedran
- Egger, Daniel J.
- Elmegreen, Bruce G.
- Franco, Nicola
- Fratini, Filippo
- Fuller, Bryce
- Gacon, Julien
- Gonciulea, Constantin
- Gribling, Sander
- Gupta, Swati
- Hadfield, Stuart
- Heese, Raoul
- Kircher, Gerhard
- Kleinert, Thomas
- Koch, Thorsten
- Korpas, Georgios
- Lenk, Steve
- Marecek, Jakub
- Markov, Vanio
- Mazzola, Guglielmo
- Mensa, Stefano
- Mohseni, Naeimeh
- Nannicini, Giacomo
- O’Meara, Corey
- Pokutta, Sebastian
- Proissl, Manuel
- Rebentrost, Patrick
- Sahin, Emre
- Symons, Benjamin C. B.
- Tornow, Sabine
- Valls, Víctor
- Woerner, Stefan
- Wolf-Bauwens, Mira L.
- Yard, Jon
- Yarkoni, Sheir
- Zhuk, Sergiy
- Zoufal, Christa
- Venue
- Nature Reviews Physics
- Published
- 2024-10-28
- Volume
- 6
- Issue
- 12
- Pages
- 718-735
- ISSN
- 2522-5820 (ISSN-L)
- OpenAlex
- W4403834027
- Semantic Scholar
- e8d07023d5a8dde24bd388b230aee85805d4ec04
- Cited by
- 201
- References
- 228
- Citations by year
- 2026: 83 · 2025: 115 · 2024: 3
- FWCI
- 6.87
- Type
- journal article
- Language
- en
- Open access
- Licence
- other-oa
- www.springernature.com/gp/researchers/text-and-data-mining (tdm)
- www.springernature.com/gp/researchers/text-and-data-mining (vor)
- 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.