Quantum Optimization: Potential, Challenges, and the Path Forward

Abstract

Recent advances in quantum computers are demonstrating the ability to solve problems at a scale beyond brute force classical simulation. As such, a widespread interest in quantum algorithms has developed in many areas, with optimization being one of the most pronounced domains. Across computer science and physics, there are a number of algorithmic approaches, often with little linkage. This is further complicated by the fragmented nature of the field of mathematical optimization, where major classes of optimization problems, such as combinatorial optimization, convex optimization, non-convex optimization, and stochastic extensions, have devoted communities. With these aspects in mind, this work draws on multiple approaches to study quantum optimization. Provably exact versus heuristic settings are first explained using computational complexity theory — highlighting where quantum advantage is possible in each context. Then, the core building blocks for quantum optimization algorithms are outlined to subsequently define prominent problem classes and identify key open questions that, if answered, will advance the field. The effects of scaling relevant problems on noisy quantum devices are also outlined in detail, alongside meaningful benchmarking problems. We underscore the importance of benchmarking by proposing clear metrics to conduct appropriate comparisons with classical optimization techniques. Lastly, we highlight two domains – finance and sustainability – as rich sources of optimization problems that could be used to benchmark, and eventually validate, the potential real-world impact of quantum optimization.

Authors 46

1. Amira Abbas

   QuSoft · University of Amsterdam

   Affiliation as printed

   QuSoft, Amsterdam (Netherlands)

   Univ. of Amsterdam (Netherlands)

   QuSoft, Amsterdam (Netherlands); Univ. of Amsterdam (Netherlands)

2. USDOE National Nuclear Security Administration (NNSA)

   University of Latvia

   Affiliation as printed

   Univ. of Latvia, Riga (Latvia)

3. Andris Ambainis

   Massachusetts Institute of Technology · University of Latvia

   Affiliation as printed

   Univ. of Latvia, Riga (Latvia)

   Massachusetts Inst. of Technology (MIT), Cambridge, MA (United States)

4. Brandon Augustino

   Los Alamos National Laboratory · Massachusetts Institute of Technology

   Affiliation as printed

   Massachusetts Inst. of Technology (MIT), Cambridge, MA (United States)

   Los Alamos National Laboratory (LANL), Los Alamos, NM (United States)

5. Andreas Bärtschi

   Los Alamos National Laboratory · QuSoft · University of Amsterdam

   Affiliation as printed

   Los Alamos National Laboratory (LANL), Los Alamos, NM (United States)

   QuSoft, Amsterdam (Netherlands); Univ. of Amsterdam (Netherlands)

   Univ. of Amsterdam (Netherlands)

6. Harry Buhrman

   Los Alamos National Laboratory · QuSoft · University of Amsterdam

   Affiliation as printed

   QuSoft, Amsterdam (Netherlands)

   Univ. of Amsterdam (Netherlands)

   Los Alamos National Laboratory (LANL), Los Alamos, NM (United States)

7. Carleton Coffrin

   Los Alamos National Laboratory · E.ON (Germany)

   Affiliation as printed

   Los Alamos National Laboratory (LANL), Los Alamos, NM (United States)

   E.ON Digital Technology GmbH, Essen (Germany)

8. G. Cortiana Aachen Leiden Univ. (Netherlands)

   Leiden University · E.ON (Germany)

   Affiliation as printed

   E.ON Digital Technology GmbH, Essen (Germany)

   Leiden Univ. (Netherlands)

9. Vedran Dunjko Aachen Leiden Univ. (Netherlands)

   Leiden University · IBM Research - Zurich

   Affiliation as printed

   Leiden Univ. (Netherlands)

   IBM Quantum, IBM Research Europe - Zurich

10. Bruce Elmegreen

    IBM (United States) · Fraunhofer Institute for Cognitive Systems

    Affiliation as printed

    IBM, Yorktown Heights, NY (United States)

    Fraunhofer IKS (Germany)

11. Nicola Franco

    Fraunhofer Institute for Cognitive Systems

    Affiliation as printed

    Fraunhofer IKS (Germany)

    Erste Group Bank, Vienna (Austria)

12. F. Fratini

    IBM (United States) · IBM Research - Thomas J. Watson Research Center

    Affiliation as printed

    Erste Group Bank, Vienna (Austria)

    IBM Quantum, IBM T.J. Watson Research Center

13. Bryce Fuller

    IBM (United States) · IBM Research - Thomas J. Watson Research Center · École Polytechnique Fédérale de Lausanne

    Affiliation as printed

    IBM Quantum, IBM T.J. Watson Research Center

    IBM, Yorktown Heights, NY (United States)

    IBM, Yorktown Heights, NY (United States); Ecole Polytechnique Federale Lausanne (EPFL) (Switzerland)

14. Julien Gacon

    IBM (United States) · Wells Fargo (United States) · École Polytechnique Fédérale de Lausanne

    Affiliation as printed

    Ecole Polytechnique Federale Lausanne (EPFL) (Switzerland)

    IBM, Yorktown Heights, NY (United States)

    Wells Fargo, San Francisco, CA (United States)

15. Constantin Gonciulea

    Wells Fargo (United States) · Tilburg University

    Affiliation as printed

    Wells Fargo, San Francisco, CA (United States)

    Tilburg University (Netherlands)

16. Sander Gribling

    Tilburg University · Massachusetts Institute of Technology

    Affiliation as printed

    Tilburg University (Netherlands)

    Massachusetts Inst. of Technology (MIT), Cambridge, MA (United States)

17. Swati Gupta

    Ames Research Center · Research Institute for Advanced Computer Science · Massachusetts Institute of Technology

    Affiliation as printed

    Massachusetts Inst. of Technology (MIT), Cambridge, MA (United States)

    Quantum Artificial Intelligence Lab, NASA Ames Research Center and USRA Research Institute for Advanced Computer Science

18. Stuart Hadfield

    Ames Research Center · Research Institute for Advanced Computer Science · Fraunhofer Institute for Industrial Mathematics

    Affiliation as printed

    Quantum Artificial Intelligence Lab, NASA Ames Research Center and USRA Research Institute for Advanced Computer Science

    Fraunhofer ITWM (Germany)

19. Raoul Heese

    Fraunhofer Institute for Industrial Mathematics

    Affiliation as printed

    Fraunhofer ITWM (Germany)

    Erste Group Bank, Vienna (Austria)

20. Gerhard Kircher
    Affiliation as printed

    Erste Group Bank, Vienna (Austria)

    Quantagonia (Germany)

21. Thomas Kleinert

    Zuse Institute Berlin · Technische Universität Berlin

    Affiliation as printed

    Quantagonia (Germany)

    Technical Univ. of Berlin (Germany)

    Zuse Institute Berlin (Germany); Technical Univ. of Berlin (Germany)

22. Thorsten Koch

    Zuse Institute Berlin · HSBC Holdings · Czech Technical University in Prague · Technische Universität Berlin

    Affiliation as printed

    Technical Univ. of Berlin (Germany)

    Zuse Institute Berlin (Germany)

    HSBC, London (United Kingdom)

    HSBC, London (United Kingdom); Czech Technical Univ., Prague (Czech Republic)

23. Georgios Korpas

    HSBC Holdings · Fraunhofer Institute of Optronics, System Technologies and Image Exploitation · Czech Technical University in Prague

    Affiliation as printed

    Czech Technical Univ., Prague (Czech Republic)

    HSBC, London (United Kingdom)

    Fraunhofer IOSB-AST (Germany)

24. Steve Lenk

    Fraunhofer Institute of Optronics, System Technologies and Image Exploitation · Czech Technical University in Prague

    Affiliation as printed

    Fraunhofer IOSB-AST (Germany)

    Czech Technical Univ., Prague (Czech Republic)

25. Jakub Mareček

    Wells Fargo (United States) · Czech Technical University in Prague

    Affiliation as printed

    Czech Technical Univ., Prague (Czech Republic)

    Wells Fargo, San Francisco, CA (United States)

26. Vanio Markov

    Wells Fargo (United States) · University of Zurich

    Affiliation as printed

    Wells Fargo, San Francisco, CA (United States)

    Univ. of Zurich (Switzerland)

27. Guglielmo Mazzola

    Science and Technology Facilities Council · University of Zurich

    Affiliation as printed

    Univ. of Zurich (Switzerland)

    The Hartree Centre, STFC, Daresbury (United Kingdom)

28. Stefano Mensa

    E.ON (Germany) · Science and Technology Facilities Council

    Affiliation as printed

    The Hartree Centre, STFC, Daresbury (United Kingdom)

    E.ON Digital Technology GmbH, Essen (Germany)

29. Naeimeh Mohseni

    University of Southern California · E.ON (Germany)

    Affiliation as printed

    E.ON Digital Technology GmbH, Essen (Germany)

    Univ. of Southern California, Los Angeles, CA (United States)

30. Giacomo Nannicini

    University of Southern California · E.ON (Germany)

    Affiliation as printed

    Univ. of Southern California, Los Angeles, CA (United States)

    E.ON Digital Technology GmbH, Essen (Germany)

31. Corey O’Meara

    E.ON (Germany) · IBM Research - Zurich

    Affiliation as printed

    E.ON Digital Technology GmbH, Essen (Germany)

    IBM Quantum, IBM Research Europe - Zurich

32. Elena Peña Tapia

    Zuse Institute Berlin · IBM Research - Zurich · Technische Universität Berlin

    Affiliation as printed

    IBM Quantum, IBM Research Europe - Zurich

    Technical Univ. of Berlin (Germany)

    Zuse Institute Berlin (Germany); Technical Univ. of Berlin (Germany)

33. Sebastian Pokutta

    Zuse Institute Berlin · IBM Research - Zurich · Technische Universität Berlin

    Affiliation as printed

    Technical Univ. of Berlin (Germany)

    Zuse Institute Berlin (Germany)

    BM Quantum, IBM Research Europe - Zurich

34. Manuel Proissl

    Centre for Quantum Technologies · National University of Singapore · IBM Research - Zurich

    Affiliation as printed

    BM Quantum, IBM Research Europe - Zurich

    Center for Quantum Technologies, National University of Singapore

35. Patrick Rebentrost

    Centre for Quantum Technologies · Science and Technology Facilities Council · National University of Singapore

    Affiliation as printed

    Center for Quantum Technologies, National University of Singapore

    The Hartree Centre, STFC, Daresbury (United Kingdom)

36. Emre Sahin

    Science and Technology Facilities Council

    Affiliation as printed

    The Hartree Centre, STFC, Daresbury (United Kingdom)

37. Benjamin Symons

    Science and Technology Facilities Council · Universität der Bundeswehr München

    Affiliation as printed

    The Hartree Centre, STFC, Daresbury (United Kingdom)

    University of the Bundeswehr Munich

38. Sabine Tornow

    Universität der Bundeswehr München · IBM (Ireland)

    Affiliation as printed

    University of the Bundeswehr Munich

    IBM Research Europe, Dublin (Ireland)

39. Víctor Valls

    IBM (Ireland) · IBM Research - Zurich

    Affiliation as printed

    IBM Research Europe, Dublin (Ireland)

    IBM Quantum, IBM Research Europe - Zurich

40. Stefan Woerner

    IBM Research - Zurich

    Affiliation as printed

    IBM Quantum, IBM Research Europe - Zurich

    IBM Research Europe, Zurich (Switzerland)

41. Mira Wolf-Bauwens

    University of Waterloo · IBM Research - Zurich

    Affiliation as printed

    IBM Research Europe, Zurich (Switzerland)

    Univ. of Waterloo, ON (Canada)

42. Jon Yard

    Volkswagen Group (Germany) · University of Waterloo

    Affiliation as printed

    Univ. of Waterloo, ON (Canada)

    Volkswagen Group, Berlin (Germany)

43. Sheir Yarkoni

    Volkswagen Group (Germany)

    Affiliation as printed

    Volkswagen Group, Berlin (Germany)

    Quantagonia (Germany)

44. Dirk Zechiel

    IBM (Ireland)

    Affiliation as printed

    Quantagonia (Germany)

    IBM Research Europe, Dublin (Ireland)

45. Sergiy Zhuk

    IBM (Ireland) · IBM Research - Zurich

    Affiliation as printed

    IBM Research Europe, Dublin (Ireland)

    IBM Research Europe, Zurich (Switzerland)

46. Christa Zoufal

    IBM Research - Zurich

    Affiliation as printed

    IBM Research Europe, Zurich (Switzerland)