Toward quantum advantage for continuous optimization
Abstract
Quantum computers are widely believed to be faster than classical computers at performing certaintasks. This belief originates fromthe fact that for some problems, quantum algorithms arefaster than any known classical algorithm: celebrated examples are Hamiltonian simulation [21],integer factorization [62], and black-box search [30, 5]. For other problems it is still an open questionif thereexist quantum algorithms that can beat classical algorithms, in theory or in practice.Mathematical optimization problems with continuous decision variables fall in this category: despitesignificant research efforts, the evidence for a clear quantum advantage is lacking. Thereare recent works that yield notable theoretical speedups with respect to classical algorithms, e.g.,[8, 71, 70, 39, 4, 50], but they all have some severe limitation that makes them unlikely to be practical.Typical limitations are: the algorithms have poor dependence on some numerical parametersof the problem instance (e.g., the desired precision of the solution), or the algorithmshave strongassumptions regarding the input data.Even with the above-mentioned limitations, some building blocks for quantum algorithms arenatural candidates to accelerate mathematical optimization approaches. Among these buildingblocks, we mention fast gradient algorithms [37, 23], algorithms for linear systems [35, 13, 12],and efficient manipulation of Gibbs states [8, 70, 73], which can be used to represent positivedefinite matrices. To build on these strengths, in this proposal we describe two areas of classicalmathematical optimization that show promising signs for a successful quantization, and a three yearplan to systematically explore these possibilities.The areas that we consider are semidefinite optimization (with special attention to algorithmsfor the subclass of linear optimization problems) and stochastic optimization. Classically, thesebranches of mathematical optimization are well studied as a consequence of their practical relevance:countless real-world applications can be modeled and solved with one of these approaches,see subsequent sections of this document for some examples. In the quantum world, semidefiniteoptimization has been studied [8, 71, 39, 4], but existing quantum algorithms are not practical, forthe reasons outlined above. These problem classes share the following characteristics: (i) Theyinvolve mathematical optimization problems with continuous (as opposed to discrete) decisionvariables. (ii) Their study has led to classical algorithms that are effective in practice, leading touse in industry, government agencies, and academia. (iii) These effective classical algorithms displaysome traits that suggest potential for a quantum speedup, using different quantum techniques.This proposal describes in detail some research questions that we plan to study, and motivatestheir importance. The measure of success for this project is the advancement of our understandingof quantum optimizationalgorithms, and the development of new quantum optimization methodologies.The ultimate goal of this research direction is to prove quantum advantage in continuousoptimization, and to do so based on algorithms that are known to be efficient in the classical world,so that a quantum implementation is susceptible of the same positive trait. Studying multipleclasses of problems allows us to mitigate the risk of this project, increasing the likelyhood that wewill be able to positively answer at least some of the research questions described here.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- May 15, 2023
- Source ID
- N000142312585
Entities
People
- Giacomo Nannicini
Organizations
- Office of Naval Research
- United States Navy
- University of Southern California