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. \nThe thesis focuses primarily on the iterative gradient search algorithm (algorithm \nfor finding the minimum or maximum of a function) and the Newton-Raphson \nalgorithm. The thesis introduces a new quantum gradient algorithm suggested by \nProfessor Thomas Konrad and colleagues and a quantum analogue of the Newton-Raphson \nMethod, a method for finding approximations to the roots or zeroes of a real-valued function. \nThe quantum gradient algorithm and the quantum Newton-Raphson are shown to \ngive a polynomial speed up over their classical analogues.

Related papers

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 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•168 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•16 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 Algorithms for Multiobjective Combinatorial Optimization

Gerardo G. Fogel

This thesis studies multiobjective optimization problems in the context of quantum computing. Quantum computing is a computational paradigm based on the laws of quantum physics as superposition, interference and entanglement. New quantum algorithms have emerged that proved to be more efficient than classical algorithms. Particularly, Grover’s search algorithm can find a specific element out of a set of N elements with complexity O(√N). Applications of Grover’s algorithm to optimization problems are currently being studied by other researchers, and in this thesis, a new adaptive search method based on Grover’s algorithm applied to several biobjective optimization problems is introduced. This new algorithm is compared against one of the most cited multiobjective optimization algorithms known as NSGA-II. Experimental evidence suggests that the quantum optimization method proposed in this work is at least as effective as NSGA-II in average, considering an equal number of executions. The proposed quantum algorithm, however, only requires approximately the square root of the number of evaluations executed by NSGA-II. Also, two different types of oracles with regard to the proposed algorithm were considered and the experimental results have shown that one of this oracles has requiered less iterations for similar performance.

•Jan 1, 2017•0 citations

Quantum gradient algorithm for general polynomials

Pan Gao, Keren Li, Shijie Wei +2 more

Gradient-based algorithms provide the fundamental tools for the optimizations and are the essential components of many modern technologies. Theoretically, the extreme points of a cost function can be found by iterative descent(ascent) of the variable along the direction of the gradient. However, the time complexity to calculate a gradient is at a level of $O(poly(d))$ for the $d$-dimension problems. For processing the high-dimension case, especially modern machine-learning engineering with the number of optimized parameters being in billions, quantum techniques are introduced. Via the dressed amplitude encoding and nonunitary module, a gradient-based quantum optimization algorithm for general polynomials is proposed, aiming at solving the fast-convergence problems with both time and memory complexity in $O(poly(logd))$. Furthermore, numerical simulations are carried out to inspect the performance of the newly born protocol by considering the noises or perturbations during the initialization, operations, and truncations. For the potential values in high-dimension optimizations, this gradient-based quantum optimization algorithm is supposed to facilitate the polynomial optimizations, being a subroutine for future practical quantum computers.

arXiv:2004.11086•Physical Review A•Apr 1, 2021•17 citations
This thesis explores the quantum analogues of algorithms used in mathematical optimization. \nThe thesis focuses primarily on the iterative gradient search algorithm (algorithm \nfor finding the minimum or maximum of a function) and the Newton-Raphson \nalgorithm. The thesis introduces a new quantum gradient algorithm suggested by \nProfessor Thomas Konrad and colleagues and a quantum analogue of the Newton-Raphson \nMethod, a method for finding approximations to the roots or zeroes of a real-valued function. \nThe quantum gradient algorithm and the quantum Newton-Raphson are shown to \ngive a polynomial speed up over their classical analogues.
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 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.
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.
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.
This thesis studies multiobjective optimization problems in the context of quantum computing. Quantum computing is a computational paradigm based on the laws of quantum physics as superposition, interference and entanglement. New quantum algorithms have emerged that proved to be more efficient than classical algorithms. Particularly, Grover’s search algorithm can find a specific element out of a set of N elements with complexity O(√N). Applications of Grover’s algorithm to optimization problems are currently being studied by other researchers, and in this thesis, a new adaptive search method based on Grover’s algorithm applied to several biobjective optimization problems is introduced. This new algorithm is compared against one of the most cited multiobjective optimization algorithms known as NSGA-II. Experimental evidence suggests that the quantum optimization method proposed in this work is at least as effective as NSGA-II in average, considering an equal number of executions. The proposed quantum algorithm, however, only requires approximately the square root of the number of evaluations executed by NSGA-II. Also, two different types of oracles with regard to the proposed algorithm were considered and the experimental results have shown that one of this oracles has requiered less iterations for similar performance.
Gradient-based algorithms provide the fundamental tools for the optimizations and are the essential components of many modern technologies. Theoretically, the extreme points of a cost function can be found by iterative descent(ascent) of the variable along the direction of the gradient. However, the time complexity to calculate a gradient is at a level of O(poly(d))O(poly(d))O(poly(d)) for the ddd-dimension problems. For processing the high-dimension case, especially modern machine-learning engineering with the number of optimized parameters being in billions, quantum techniques are introduced. Via the dressed amplitude encoding and nonunitary module, a gradient-based quantum optimization algorithm for general polynomials is proposed, aiming at solving the fast-convergence problems with both time and memory complexity in O(poly(logd))O(poly(logd))O(poly(logd)). Furthermore, numerical simulations are carried out to inspect the performance of the newly born protocol by considering the noises or perturbations during the initialization, operations, and truncations. For the potential values in high-dimension optimizations, this gradient-based quantum optimization algorithm is supposed to facilitate the polynomial optimizations, being a subroutine for future practical quantum computers.