elib
DLR-Header
DLR-Logo -> http://www.dlr.de
DLR Portal Home | Imprint | Privacy Policy | Accessibility | Contact | Deutsch
Fontsize: [-] Text [+]
Tell a friend Print

Challenges and opportunities in quantum optimization

Abbas, Amira and Ambainis, Andris and Augustino, Brandon and Bärtschi, Andreas and Buhrman, Harry and Coffrin, Carleton and Cortiana, Giorgio and Dunjko, Vedran and Egger, Daniel J. and Elmegreen, Bruce G. and Franco, Nicola and Fratini, Filippo and Fuller, Bryce and Gacon, Julien and Gonciulea, Constantin and Gribling, Sander and Gupta, Swati and Hadfield, Stuart and Heese, Raoul and Kircher, Gerhard and Kleinert, Thomas and Koch, Thorsten and Korpas, Georgios and Lenk, Steve and Marecek, Jakub and Markov, Vanio and Mazzola, Guglielmo and Mensa, Stefano and Mohseni, Naeimeh and Nannicini, Giacomo and O’Meara, Corey and Tapia, Elena Peña and Pokutta, Sebastian and Proissl, Manuel and Rebentrost, Patrick and Sahin, Emre and Symons, Benjamin C. B. and Tornow, Sabine and Valls, Víctor and Woerner, Stefan and Wolf-Bauwens, Mira L. and Yard, Jon and Yarkoni, Sheir and Zechiel, Dirk and Zhuk, Sergiy and Zoufal, Christa (2024) Challenges and opportunities in quantum optimization. Nature Reviews Physics, 6 (12), pp. 718-735. Springer Nature. doi: 10.1038/s42254-024-00770-9. ISSN 2522-5820.

[img] PDF - Only accessible within DLR - Published version
1MB

Official URL: https://dx.doi.org/10.1038/s42254-024-00770-9

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.

Item URL in elib:https://elib.dlr.de/219452/
Document Type:Article
Title:Challenges and opportunities in quantum optimization
Authors:
AuthorsInstitution or Email of AuthorsAuthor's ORCID iDORCID Put Code
Abbas, AmiraUNSPECIFIEDhttps://orcid.org/0000-0003-3383-2287UNSPECIFIED
Ambainis, AndrisUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
Augustino, BrandonUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
Bärtschi, AndreasUNSPECIFIEDhttps://orcid.org/0000-0002-9049-0984UNSPECIFIED
Buhrman, HarryUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
Coffrin, CarletonUNSPECIFIEDhttps://orcid.org/0000-0003-3238-1699UNSPECIFIED
Cortiana, GiorgioUNSPECIFIEDhttps://orcid.org/0000-0001-8745-5021UNSPECIFIED
Dunjko, VedranUNSPECIFIEDhttps://orcid.org/0000-0002-2632-7955UNSPECIFIED
Egger, Daniel J.UNSPECIFIEDhttps://orcid.org/0000-0002-5523-9807UNSPECIFIED
Elmegreen, Bruce G.UNSPECIFIEDUNSPECIFIEDUNSPECIFIED
Franco, NicolaUNSPECIFIEDhttps://orcid.org/0000-0002-7320-5627UNSPECIFIED
Fratini, FilippoUNSPECIFIEDhttps://orcid.org/0000-0002-8060-4730UNSPECIFIED
Fuller, BryceUNSPECIFIEDhttps://orcid.org/0009-0009-3218-6501UNSPECIFIED
Gacon, JulienUNSPECIFIEDhttps://orcid.org/0000-0002-8617-1825UNSPECIFIED
Gonciulea, ConstantinUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
Gribling, SanderUNSPECIFIEDhttps://orcid.org/0000-0002-6817-2971UNSPECIFIED
Gupta, SwatiUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
Hadfield, StuartUNSPECIFIEDhttps://orcid.org/0000-0002-4607-3921UNSPECIFIED
Heese, RaoulUNSPECIFIEDhttps://orcid.org/0000-0001-7479-3339UNSPECIFIED
Kircher, GerhardUNSPECIFIEDhttps://orcid.org/0009-0008-6507-5149UNSPECIFIED
Kleinert, ThomasUNSPECIFIEDhttps://orcid.org/0000-0001-7082-7466UNSPECIFIED
Koch, ThorstenUNSPECIFIEDhttps://orcid.org/0000-0002-1967-0077UNSPECIFIED
Korpas, GeorgiosUNSPECIFIEDhttps://orcid.org/0000-0003-3850-4979UNSPECIFIED
Lenk, SteveUNSPECIFIEDhttps://orcid.org/0000-0002-3376-0589198517361
Marecek, JakubUNSPECIFIEDhttps://orcid.org/0000-0003-0839-0691UNSPECIFIED
Markov, VanioUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
Mazzola, GuglielmoUNSPECIFIEDhttps://orcid.org/0000-0002-8982-5169UNSPECIFIED
Mensa, StefanoUNSPECIFIEDhttps://orcid.org/0000-0002-0938-144XUNSPECIFIED
Mohseni, NaeimehUNSPECIFIEDhttps://orcid.org/0000-0003-3373-4572UNSPECIFIED
Nannicini, GiacomoUNSPECIFIEDhttps://orcid.org/0000-0002-4936-1259UNSPECIFIED
O’Meara, CoreyUNSPECIFIEDhttps://orcid.org/0000-0001-7056-7545UNSPECIFIED
Tapia, Elena PeñaUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
Pokutta, SebastianUNSPECIFIEDhttps://orcid.org/0000-0001-7365-3000UNSPECIFIED
Proissl, ManuelUNSPECIFIEDhttps://orcid.org/0009-0006-1083-1133UNSPECIFIED
Rebentrost, PatrickUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
Sahin, EmreUNSPECIFIEDhttps://orcid.org/0000-0002-5996-0407UNSPECIFIED
Symons, Benjamin C. B.UNSPECIFIEDhttps://orcid.org/0000-0001-5742-1082UNSPECIFIED
Tornow, SabineUNSPECIFIEDhttps://orcid.org/0000-0003-3301-169XUNSPECIFIED
Valls, VíctorUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
Woerner, StefanUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
Wolf-Bauwens, Mira L.UNSPECIFIEDUNSPECIFIEDUNSPECIFIED
Yard, JonUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
Yarkoni, SheirUNSPECIFIEDhttps://orcid.org/0000-0003-1839-3757UNSPECIFIED
Zechiel, DirkUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
Zhuk, SergiyUNSPECIFIEDhttps://orcid.org/0000-0002-0956-8909UNSPECIFIED
Zoufal, ChristaUNSPECIFIEDhttps://orcid.org/0000-0003-4126-3141UNSPECIFIED
Date:28 October 2024
Journal or Publication Title:Nature Reviews Physics
Refereed publication:Yes
Open Access:No
Gold Open Access:No
In SCOPUS:Yes
In ISI Web of Science:Yes
Volume:6
DOI:10.1038/s42254-024-00770-9
Page Range:pp. 718-735
Publisher:Springer Nature
ISSN:2522-5820
Status:Published
Keywords:Quantum optimization algorithms, quantum computing, benchmarking, quantum optimization
HGF - Research field:other
HGF - Program:other
HGF - Program Themes:other
DLR - Research area:Quantum Computing Initiative
DLR - Program:QC AW - Applications
DLR - Research theme (Project):QC - QCMobility
Location: Ulm
Institutes and Institutions:Institute of Quantum Technologies > Quantum Information and Communication
Deposited By: Nguyen, Thi Kim Tuyen
Deposited On:02 Dec 2025 10:57
Last Modified:02 Dec 2025 10:57

Repository Staff Only: item control page
Browse
Search
Help & Contact
Information
OpenAIRE Validator logo electronic library is running on EPrints 3.3.12
Website and database design: Copyright © German Aerospace Center (DLR). All rights reserved.