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

Quantum analogues of classical optimization algorithms.

Kelvin Tafadzwa Mpofu

Published Jan 1, 2017• 0 citations
OpenAlex

Abstract

This thesis explores the quantum analogues of algorithms used in mathematical optimization.The thesis focuses primarily on the iterative gradient search algorithm (algorithm for finding the minimum or maximum of a function) and the Newton-Raphson algorithm.The thesis introduces a new quantum gradient algorithm suggested by Professor Thomas Konrad and colleagues and a quantum analogue of the Newton-Raphson Method, a method for finding approximations to the roots or zeroes of a real-valued function.The quantum gradient algorithm and the quantum Newton-Raphson are shown to give a polynomial speed up over their classical analogues.

Related papers

Quantum gradient descent and Newton’s method for constrained polynomial optimization

Patrick Rebentrost, Maria Schuld, Leonard Wossnig +2 more

Abstract Optimization problems in disciplines such as machine learning are commonly solved with iterative methods. Gradient descent algorithms find local minima by moving along the direction of steepest descent while Newton’s method takes into account curvature information and thereby often improves convergence. Here, we develop quantum versions of these iterative optimization algorithms and apply them to polynomial optimization with a unit norm constraint. In each step, multiple copies of the current candidate are used to improve the candidate using quantum phase estimation, an adapted quantum state exponentiation scheme, as well as quantum matrix multiplications and inversions. The required operations perform polylogarithmically in the dimension of the solution vector and exponentially in the number of iterations. Therefore, the quantum algorithm can be useful for high-dimensional problems where a small number of iterations is sufficient.

arXiv:1612.01789•New Journal of Physics•Jun 20, 2019•15 citations

Quantum gradient descent and Newton’s method for constrained polynomial optimization

Rebentrost, Frank Patrick, Seth Lloyd

Optimization problems in disciplines such as machine learning are commonly solved with iterative methods. Gradient descent algorithms find local minima by moving along the direction of steepest descent while Newton's method takes into account curvature information and thereby often improves convergence. Here, we develop quantum versions of these iterative optimization algorithms and apply them to polynomial optimization with a unit norm constraint. In each step, multiple copies of the current candidate are used to improve the candidate using quantum phase estimation, an adapted quantum state exponentiation scheme, as well as quantum matrix multiplications and inversions. The required operations perform polylogarithmically in the dimension of the solution vector and exponentially in the number of iterations. Therefore, the quantum algorithm can be useful for high-dimensional problems where a small number of iterations is sufficient.

•Jul 1, 2019•127 citations

Quantum algorithms and learning theory

Srinivasan Arunachalam

This thesis studies strengths and weaknesses of quantum computers. In the first part we present three contributions to quantum algorithms. 1) consider a search space of N elements. One of these elements is "marked" and our goal is to find this. We describe a quantum algorithm to solve this problem using essentially sqrt{N} queries and other operations, improving over the gate count of Grover's algorithm. 2) We give a succinct characterization of quantum algorithms in terms of polynomials, and develop a new technique for showing upper and lower bounds on quantum query complexity based on this. 3) One generic technique used to compute the minimum of a given function is "gradient descent". We present a quantum gradient-calculation algorithm and a gradient-optimization algorithm that is quadratically faster than classical algorithms. In the second part of this thesis we look at quantum learning theory. 1) We survey quantum learning theory, describing the main results known for three models of learning, using classical as well as quantum data: exact learning from membership queries, the probably approximately correct (PAC) learning model, and the agnostic learning model. 2) We then consider if a quantum learner can PAC-learn a given concept class from fewer quantum examples. We give a negative answer by showing that quantum examples are not more powerful than classical random examples, both for PAC learning and for agnostic learning.

•Apr 25, 2018•1 citation

Quantum speedups of some general-purpose numerical optimisation algorithms

Ashley Montanaro, Noah Linden, Cezar-Mihail Alexandru +3 more

Abstract We give quantum speedups of several general-purpose numerical optimisation methods for minimising a function <?CDATA $f:{\mathbb{R}}^{n}\to \mathbb{R}$?> f : R n → R . First, we show that many techniques for global optimisation under a Lipschitz constraint can be accelerated near-quadratically. Second, we show that backtracking line search, an ingredient in quasi-Newton optimisation algorithms, can be accelerated up to quadratically. Third, we show that a component of the Nelder–Mead algorithm can be accelerated by up to a multiplicative factor of <?CDATA $O\left(\sqrt{n}\right)$?> O ( n ) . Fourth, we show that a quantum gradient computation algorithm of Gilyén et al can be used to approximately compute gradients in the framework of stochastic gradient descent. In each case, our results are based on applying existing quantum algorithms to accelerate specific components of the classical algorithms, rather than developing new quantum techniques.

•Sep 3, 2020•14 citations

Towards Efficient Function Optimisation with Quantum–Classical Hybrid Search

Mansur Ziatdinov, Fedor Levkovich-Maslyuk, Emmanuel M. Pothos

Finding the global minimum of a function with many local extrema is well known to be a challenging computational task. We propose a hybrid quantum-classical algorithm for this optimisation problem, based on a combination of Grover quantum search and the classical Newton-Raphson method. The approach is tailored to situations with a large number of false minima. The main idea is to use quantum search to efficiently locate the vicinity of the true optimum, after which a classical algorithm can solve the problem in only a few iterations. We specifically address the nontrivial question of choosing the discretisation of the function domain, which is critical for quantum approaches to optimisation of continuous functions. While we do not expect that this method will always be superior, we identify a paradigmatic case of a function for which we demonstrate that, remarkably, our hybrid method quadratically outperforms a purely classical approach (measuring performance by the number of function/oracle calls). We evaluate key performance metrics of the algorithm in numerical experiments. We furthermore discuss its possible extensions as well as the potential relevance of hybrid approaches in the context of quantum cognition.

Entropy•Sep 26, 2026•0 citations

Quantum speedups of some general-purpose numerical optimisation algorithms

Cezar-Mihail Alexandru, Ella Bridgett-Tomkinson, Noah Linden +3 more

Abstract We give quantum speedups of several general-purpose numerical optimisation methods for minimising a function f : R n → R . First, we show that many techniques for global optimisation under a Lipschitz constraint can be accelerated near-quadratically. Second, we show that backtracking line search, an ingredient in quasi-Newton optimisation algorithms, can be accelerated up to quadratically. Third, we show that a component of the Nelder–Mead algorithm can be accelerated by up to a multiplicative factor of O ( n ) . Fourth, we show that a quantum gradient computation algorithm of Gilyén et al can be used to approximately compute gradients in the framework of stochastic gradient descent. In each case, our results are based on applying existing quantum algorithms to accelerate specific components of the classical algorithms, rather than developing new quantum techniques.

arXiv:2004.06521•Quantum Science and Technology•Aug 17, 2020•1 citation
This thesis explores the quantum analogues of algorithms used in mathematical optimization.The thesis focuses primarily on the iterative gradient search algorithm (algorithm for finding the minimum or maximum of a function) and the Newton-Raphson algorithm.The thesis introduces a new quantum gradient algorithm suggested by Professor Thomas Konrad and colleagues and a quantum analogue of the Newton-Raphson Method, a method for finding approximations to the roots or zeroes of a real-valued function.The quantum gradient algorithm and the quantum Newton-Raphson are shown to give a polynomial speed up over their classical analogues.
Abstract Optimization problems in disciplines such as machine learning are commonly solved with iterative methods. Gradient descent algorithms find local minima by moving along the direction of steepest descent while Newton’s method takes into account curvature information and thereby often improves convergence. Here, we develop quantum versions of these iterative optimization algorithms and apply them to polynomial optimization with a unit norm constraint. In each step, multiple copies of the current candidate are used to improve the candidate using quantum phase estimation, an adapted quantum state exponentiation scheme, as well as quantum matrix multiplications and inversions. The required operations perform polylogarithmically in the dimension of the solution vector and exponentially in the number of iterations. Therefore, the quantum algorithm can be useful for high-dimensional problems where a small number of iterations is sufficient.
Optimization problems in disciplines such as machine learning are commonly solved with iterative methods. Gradient descent algorithms find local minima by moving along the direction of steepest descent while Newton's method takes into account curvature information and thereby often improves convergence. Here, we develop quantum versions of these iterative optimization algorithms and apply them to polynomial optimization with a unit norm constraint. In each step, multiple copies of the current candidate are used to improve the candidate using quantum phase estimation, an adapted quantum state exponentiation scheme, as well as quantum matrix multiplications and inversions. The required operations perform polylogarithmically in the dimension of the solution vector and exponentially in the number of iterations. Therefore, the quantum algorithm can be useful for high-dimensional problems where a small number of iterations is sufficient.
This thesis studies strengths and weaknesses of quantum computers. In the first part we present three contributions to quantum algorithms. 1) consider a search space of N elements. One of these elements is "marked" and our goal is to find this. We describe a quantum algorithm to solve this problem using essentially sqrt{N} queries and other operations, improving over the gate count of Grover's algorithm. 2) We give a succinct characterization of quantum algorithms in terms of polynomials, and develop a new technique for showing upper and lower bounds on quantum query complexity based on this. 3) One generic technique used to compute the minimum of a given function is "gradient descent". We present a quantum gradient-calculation algorithm and a gradient-optimization algorithm that is quadratically faster than classical algorithms. In the second part of this thesis we look at quantum learning theory. 1) We survey quantum learning theory, describing the main results known for three models of learning, using classical as well as quantum data: exact learning from membership queries, the probably approximately correct (PAC) learning model, and the agnostic learning model. 2) We then consider if a quantum learner can PAC-learn a given concept class from fewer quantum examples. We give a negative answer by showing that quantum examples are not more powerful than classical random examples, both for PAC learning and for agnostic learning.
Abstract We give quantum speedups of several general-purpose numerical optimisation methods for minimising a function <?CDATA f:Rn→Rf:{\mathbb{R}}^{n}\to \mathbb{R}f:Rn→R?> f : R n → R . First, we show that many techniques for global optimisation under a Lipschitz constraint can be accelerated near-quadratically. Second, we show that backtracking line search, an ingredient in quasi-Newton optimisation algorithms, can be accelerated up to quadratically. Third, we show that a component of the Nelder–Mead algorithm can be accelerated by up to a multiplicative factor of <?CDATA O(n)O\left(\sqrt{n}\right)O(n​)?> O ( n ) . Fourth, we show that a quantum gradient computation algorithm of Gilyén et al can be used to approximately compute gradients in the framework of stochastic gradient descent. In each case, our results are based on applying existing quantum algorithms to accelerate specific components of the classical algorithms, rather than developing new quantum techniques.
Finding the global minimum of a function with many local extrema is well known to be a challenging computational task. We propose a hybrid quantum-classical algorithm for this optimisation problem, based on a combination of Grover quantum search and the classical Newton-Raphson method. The approach is tailored to situations with a large number of false minima. The main idea is to use quantum search to efficiently locate the vicinity of the true optimum, after which a classical algorithm can solve the problem in only a few iterations. We specifically address the nontrivial question of choosing the discretisation of the function domain, which is critical for quantum approaches to optimisation of continuous functions. While we do not expect that this method will always be superior, we identify a paradigmatic case of a function for which we demonstrate that, remarkably, our hybrid method quadratically outperforms a purely classical approach (measuring performance by the number of function/oracle calls). We evaluate key performance metrics of the algorithm in numerical experiments. We furthermore discuss its possible extensions as well as the potential relevance of hybrid approaches in the context of quantum cognition.
Abstract We give quantum speedups of several general-purpose numerical optimisation methods for minimising a function f : R n → R . First, we show that many techniques for global optimisation under a Lipschitz constraint can be accelerated near-quadratically. Second, we show that backtracking line search, an ingredient in quasi-Newton optimisation algorithms, can be accelerated up to quadratically. Third, we show that a component of the Nelder–Mead algorithm can be accelerated by up to a multiplicative factor of O ( n ) . Fourth, we show that a quantum gradient computation algorithm of Gilyén et al can be used to approximately compute gradients in the framework of stochastic gradient descent. In each case, our results are based on applying existing quantum algorithms to accelerate specific components of the classical algorithms, rather than developing new quantum techniques.