Challenges and opportunities in quantum optimization
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F24%3A00379058" target="_blank" >RIV/68407700:21230/24:00379058 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.1038/s42254-024-00770-9" target="_blank" >https://doi.org/10.1038/s42254-024-00770-9</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1038/s42254-024-00770-9" target="_blank" >10.1038/s42254-024-00770-9</a>
Alternative languages
Result language
angličtina
Original language name
Challenges and opportunities in quantum optimization
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/GA23-07947S" target="_blank" >GA23-07947S: Learning Models of Quantum Systems as a Non-Commutative Polynomial Optimization Problem</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2024
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Nature Reviews Physics
ISSN
2522-5820
e-ISSN
2522-5820
Volume of the periodical
6
Issue of the periodical within the volume
12
Country of publishing house
GB - UNITED KINGDOM
Number of pages
18
Pages from-to
718-735
UT code for WoS article
001344204600001
EID of the result in the Scopus database
2-s2.0-85207968009