Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Cambridge University Press eBooks

Continuous optimization

Alexander M. Dalzell, Sam McArdle, Mario Berta, Przemyslaw Bienias, Chi-Fang Chen, András Gilyén, Connor T. Hann, Michael J. Kastoryano, Emil T. Khabiboulline, Aleksander Kubica, Grant Salton, Samson Wang, Fernando G. S. L. Brandão

Published Apr 24, 2025• 0 citations
Publisher

Abstract

This chapter covers applications of quantum computing in the area of continuous optimization, including both convex and nonconvex optimization. We discuss quantum algorithms for computing Nash equilibria for zero-sum games and for solving linear, second-order, and semidefinite programs. These algorithms are based on quantum implementations of the multiplicative weights update method or interior point methods. We also discuss general quantum algorithms for convex optimization which can provide a speedup in cases where the objective function is much easier to evaluate than the gradient of the objective function. Finally, we cover quantum algorithms for escaping saddle points and finding local minima in nonconvex optimization problems.

DOI
10.1017/9781009639651.007

Related papers

Quantum interior point methods

Alexander M. Dalzell, Sam McArdle, Mario Berta +10 more

This chapter covers quantum interior point methods, which are quantum algorithmic primitives for application to convex optimization problems, particularly linear, second-order, and semidefinite programs. Interior point methods are a successful classical iterative technique that solve a linear system of equations at each iteration. Quantum interior point methods replace this step with quantum a quantum linear system solver combined with quantum tomography, potentially offering a polynomial speedup.

Cambridge University Press eBooks•Apr 24, 2025•0 citations

Quantum Algorithms and Lower Bounds for Finite-Sum Optimization

Yexin Zhang, Zhang, Chenyi, Cong Fang +2 more

Finite-sum optimization has wide applications in machine learning, covering important problems such as support vector machines, regression, etc. In this paper, we initiate the study of solving finite-sum optimization problems by quantum computing. Specifically, let $f_1,\ldots,f_n\colon\mathbb{R}^d\to\mathbb{R}$ be $\ell$-smooth convex functions and $ψ\colon\mathbb{R}^d\to\mathbb{R}$ be a $μ$-strongly convex proximal function. The goal is to find an $ε$-optimal point for $F(\mathbf{x})=\frac{1}{n}\sum_{i=1}^n f_i(\mathbf{x})+ψ(\mathbf{x})$. We give a quantum algorithm with complexity $\tilde{O}\big(n+\sqrt{d}+\sqrt{\ell/μ}\big(n^{1/3}d^{1/3}+n^{-2/3}d^{5/6}\big)\big)$, improving the classical tight bound $\tildeΘ\big(n+\sqrt{n\ell/μ}\big)$. We also prove a quantum lower bound $\tildeΩ(n+n^{3/4}(\ell/μ)^{1/4})$ when $d$ is large enough. Both our quantum upper and lower bounds can extend to the cases where $ψ$ is not necessarily strongly convex, or each $f_i$ is Lipschitz but not necessarily smooth. In addition, when $F$ is nonconvex, our quantum algorithm can find an $ε$-critial point using $\tilde{O}(n+\ell(d^{1/3}n^{1/3}+\sqrt{d})/ε^2)$ queries.

arXiv:2406.03006•Jun 5, 2024•3 citations

Fast Convex Optimization with Quantum Gradient Methods

Brandon Augustino, Dylan Herman, Enrico Fontana +4 more

We study quantum algorithms based on quantum (sub)gradient estimation using noisy function evaluation oracles, and demonstrate the first dimension-independent query complexities (up to poly-logarithmic factors) for zeroth-order convex optimization in both smooth and nonsmooth settings. Interestingly, only using noisy function evaluation oracles, we match the first-order query complexities of classical gradient descent, thereby exhibiting exponential separation between quantum and classical zeroth-order optimization. We then generalize these algorithms to work in non-Euclidean settings by using quantum (sub)gradient estimation to instantiate mirror descent and its variants, including dual averaging and mirror prox. By leveraging a connection between semidefinite programming and eigenvalue optimization, we use our quantum mirror descent method to give a new quantum algorithm for solving semidefinite programs, linear programs, and zero-sum games. We identify a parameter regime in which our zero-sum games algorithm is faster than any existing classical or quantum approach.

arXiv:2503.17356•Mar 21, 2025•8 citations

Quantum algorithms for machine learning and optimization

Tongyang Li

The theories of optimization and machine learning answer foundational questions in computer science and lead to new algorithms for practical applications. While these topics have been extensively studied in the context of classical computing, their quantum counterparts are far from well-understood. In this thesis, we explore algorithms that bridge the gap between the fields of quantum computing and machine learning. First, we consider general optimization problems with only function evaluations. For two core problems, namely general convex optimization and volume estimation of convex bodies, we give quantum algorithms as well as quantum lower bounds that constitute the quantum speedups of both problems to be polynomial compared to their classical counterparts. We then consider machine learning and optimization problems with input data stored explicitly as matrices. We first look at semidefinite programs and provide quantum algorithms with polynomial speedup compared to the classical state-of-the-art. We then move to machine learning and give the optimal quantum algorithms for linear and kernel-based classifications. To complement with our quantum algorithms, we also introduce a framework for quantum-inspired classical algorithms, showing that for low-rank matrix arithmetics there can only be polynomial quantum speedup. Finally, we study statistical problems on quantum computers, with the focus on testing properties of probability distributions. We show that for testing various properties including L1-distance, L2-distance, Shannon and Renyi entropies, etc., there are polynomial quantum speedups compared to their classical counterparts. We also extend these results to testing properties of quantum states.

•Jan 1, 2020•2 citations

Applications of optimization to factorization ranks and quantum information theory

Sander Gribling

Optimization is a fundamental area in mathematics and computer science, with many real-world applications. In this thesis we study the efficiency with which we can solve certain optimization problems from two different perspectives. Firstly, we study it from the perspective of matrix factorization ranks, which comes with connections to quantum information theory. Secondly, we study it from the perspective of quantum computing. This thesis is accordingly divided into two parts, where we take these perspectives. In the first part of this thesis we study several matrix factorization ranks and their connections to quantum information theory. In Chapter 5, we first give a unified approach to lower bounding matrix factorization ranks, using polynomial optimization techniques. In Chapter 6, we exploit the connection between one particular factorization rank, the completely positive semidefinite rank, and quantum correlations to provide an explicit family of matrices with a large completely positive semidefinite factorization rank. In Chapter 8, we use the same connection to study quantum versions of classical graph parameters from the perspective of polynomial optimization (albeit in noncommutative variables). In Chapter 7 we propose and study a new measure for the amount of entanglement needed to realize quantum correlations. We can approximate this new measure using our approach to matrix factorization ranks, i.e., through polynomial optimization in noncommutative variables. In the second part of this thesis we turn our attention to the question: Can we solve optimization problems faster on a quantum computer? First, in Chapter 10, we look at the problem of evaluating a Boolean function. We give a new semidefinite programming characterization of the minimum number of quantum queries to the input that are needed to determine the corresponding function value. In Chapter 11 we revisit the semidefinite programming problem that plays a crucial role in the rest of the thesis; we provide a quantum algorithm for solving semidefinite programs. Finally, in Chapter 12, we study the general problem of solving convex optimization problems in the oracle model. We provide both upper and lower bounds on the efficiency of various reductions in the quantum setting. In particular, we show that quantum computers are more efficient than classical computers for the task of answering separation queries when access to the convex problem is given through membership queries.

Other publications TiSEM•Aug 2, 2019•2 citations

Applying Quantum Optimization Algorithms for Linear Programming

Mert Side, Volkan Erol

Quantum computers are machines that are designed to use quantum mechanics in order to improve upon classical computers by running quantum algorithms. One of the main applications of quantum computing is solving optimization problems. For addressing optimization problems we can use linear programming. Linear programming is a method to obtain the best possible outcome in a special case of mathematical programming. Application areas of this problem consist of resource allocation, production scheduling, parameter estimation, etc. In our study, we looked at the duality of resource allocation problems. First, we chose a real world optimization problem and looked at its solution with linear programming. Then, we restudied this problem with a quantum algorithm in order to understand whether if there is a speedup of the solution. The improvement in computation is analysed and some interesting results are reported.

•Apr 14, 2017•0 citations
This chapter covers applications of quantum computing in the area of continuous optimization, including both convex and nonconvex optimization. We discuss quantum algorithms for computing Nash equilibria for zero-sum games and for solving linear, second-order, and semidefinite programs. These algorithms are based on quantum implementations of the multiplicative weights update method or interior point methods. We also discuss general quantum algorithms for convex optimization which can provide a speedup in cases where the objective function is much easier to evaluate than the gradient of the objective function. Finally, we cover quantum algorithms for escaping saddle points and finding local minima in nonconvex optimization problems.
This chapter covers quantum interior point methods, which are quantum algorithmic primitives for application to convex optimization problems, particularly linear, second-order, and semidefinite programs. Interior point methods are a successful classical iterative technique that solve a linear system of equations at each iteration. Quantum interior point methods replace this step with quantum a quantum linear system solver combined with quantum tomography, potentially offering a polynomial speedup.
Finite-sum optimization has wide applications in machine learning, covering important problems such as support vector machines, regression, etc. In this paper, we initiate the study of solving finite-sum optimization problems by quantum computing. Specifically, let f1,…,fn ⁣:Rd→Rf_1,\ldots,f_n\colon\mathbb{R}^d\to\mathbb{R}f1​,…,fn​:Rd→R be ℓ\ellℓ-smooth convex functions and ψ ⁣:Rd→Rψ\colon\mathbb{R}^d\to\mathbb{R}ψ:Rd→R be a μμμ-strongly convex proximal function. The goal is to find an εεε-optimal point for F(x)=1n∑i=1nfi(x)+ψ(x)F(\mathbf{x})=\frac{1}{n}\sum_{i=1}^n f_i(\mathbf{x})+ψ(\mathbf{x})F(x)=n1​∑i=1n​fi​(x)+ψ(x). We give a quantum algorithm with complexity O~(n+d+ℓ/μ(n1/3d1/3+n−2/3d5/6))\tilde{O}\big(n+\sqrt{d}+\sqrt{\ell/μ}\big(n^{1/3}d^{1/3}+n^{-2/3}d^{5/6}\big)\big)O~(n+d​+ℓ/μ​(n1/3d1/3+n−2/3d5/6)), improving the classical tight bound Θ~(n+nℓ/μ)\tildeΘ\big(n+\sqrt{n\ell/μ}\big)Θ~(n+nℓ/μ​). We also prove a quantum lower bound Ω~(n+n3/4(ℓ/μ)1/4)\tildeΩ(n+n^{3/4}(\ell/μ)^{1/4})Ω~(n+n3/4(ℓ/μ)1/4) when ddd is large enough. Both our quantum upper and lower bounds can extend to the cases where ψψψ is not necessarily strongly convex, or each fif_ifi​ is Lipschitz but not necessarily smooth. In addition, when FFF is nonconvex, our quantum algorithm can find an εεε-critial point using O~(n+ℓ(d1/3n1/3+d)/ε2)\tilde{O}(n+\ell(d^{1/3}n^{1/3}+\sqrt{d})/ε^2)O~(n+ℓ(d1/3n1/3+d​)/ε2) queries.
We study quantum algorithms based on quantum (sub)gradient estimation using noisy function evaluation oracles, and demonstrate the first dimension-independent query complexities (up to poly-logarithmic factors) for zeroth-order convex optimization in both smooth and nonsmooth settings. Interestingly, only using noisy function evaluation oracles, we match the first-order query complexities of classical gradient descent, thereby exhibiting exponential separation between quantum and classical zeroth-order optimization. We then generalize these algorithms to work in non-Euclidean settings by using quantum (sub)gradient estimation to instantiate mirror descent and its variants, including dual averaging and mirror prox. By leveraging a connection between semidefinite programming and eigenvalue optimization, we use our quantum mirror descent method to give a new quantum algorithm for solving semidefinite programs, linear programs, and zero-sum games. We identify a parameter regime in which our zero-sum games algorithm is faster than any existing classical or quantum approach.
The theories of optimization and machine learning answer foundational questions in computer science and lead to new algorithms for practical applications. While these topics have been extensively studied in the context of classical computing, their quantum counterparts are far from well-understood. In this thesis, we explore algorithms that bridge the gap between the fields of quantum computing and machine learning. First, we consider general optimization problems with only function evaluations. For two core problems, namely general convex optimization and volume estimation of convex bodies, we give quantum algorithms as well as quantum lower bounds that constitute the quantum speedups of both problems to be polynomial compared to their classical counterparts. We then consider machine learning and optimization problems with input data stored explicitly as matrices. We first look at semidefinite programs and provide quantum algorithms with polynomial speedup compared to the classical state-of-the-art. We then move to machine learning and give the optimal quantum algorithms for linear and kernel-based classifications. To complement with our quantum algorithms, we also introduce a framework for quantum-inspired classical algorithms, showing that for low-rank matrix arithmetics there can only be polynomial quantum speedup. Finally, we study statistical problems on quantum computers, with the focus on testing properties of probability distributions. We show that for testing various properties including L1-distance, L2-distance, Shannon and Renyi entropies, etc., there are polynomial quantum speedups compared to their classical counterparts. We also extend these results to testing properties of quantum states.
Optimization is a fundamental area in mathematics and computer science, with many real-world applications. In this thesis we study the efficiency with which we can solve certain optimization problems from two different perspectives. Firstly, we study it from the perspective of matrix factorization ranks, which comes with connections to quantum information theory. Secondly, we study it from the perspective of quantum computing. This thesis is accordingly divided into two parts, where we take these perspectives. In the first part of this thesis we study several matrix factorization ranks and their connections to quantum information theory. In Chapter 5, we first give a unified approach to lower bounding matrix factorization ranks, using polynomial optimization techniques. In Chapter 6, we exploit the connection between one particular factorization rank, the completely positive semidefinite rank, and quantum correlations to provide an explicit family of matrices with a large completely positive semidefinite factorization rank. In Chapter 8, we use the same connection to study quantum versions of classical graph parameters from the perspective of polynomial optimization (albeit in noncommutative variables). In Chapter 7 we propose and study a new measure for the amount of entanglement needed to realize quantum correlations. We can approximate this new measure using our approach to matrix factorization ranks, i.e., through polynomial optimization in noncommutative variables. In the second part of this thesis we turn our attention to the question: Can we solve optimization problems faster on a quantum computer? First, in Chapter 10, we look at the problem of evaluating a Boolean function. We give a new semidefinite programming characterization of the minimum number of quantum queries to the input that are needed to determine the corresponding function value. In Chapter 11 we revisit the semidefinite programming problem that plays a crucial role in the rest of the thesis; we provide a quantum algorithm for solving semidefinite programs. Finally, in Chapter 12, we study the general problem of solving convex optimization problems in the oracle model. We provide both upper and lower bounds on the efficiency of various reductions in the quantum setting. In particular, we show that quantum computers are more efficient than classical computers for the task of answering separation queries when access to the convex problem is given through membership queries.
Quantum computers are machines that are designed to use quantum mechanics in order to improve upon classical computers by running quantum algorithms. One of the main applications of quantum computing is solving optimization problems. For addressing optimization problems we can use linear programming. Linear programming is a method to obtain the best possible outcome in a special case of mathematical programming. Application areas of this problem consist of resource allocation, production scheduling, parameter estimation, etc. In our study, we looked at the duality of resource allocation problems. First, we chose a real world optimization problem and looked at its solution with linear programming. Then, we restudied this problem with a quantum algorithm in order to understand whether if there is a speedup of the solution. The improvement in computation is analysed and some interesting results are reported.