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

arXiv:1809.01378 · TURKISH JOURNAL OF ELECTRICAL ENGINEERING & COMPUTER SCIENCES

The quantum version of the shifted power method and its application in quadratic binary optimization

Ammar Daskin

Published Jan 7, 2020• 2 citations
arXivHTMLPDF

Abstract

In this paper, we present a direct quantum adaptation of the classical shifted power method. The method is very similar to the iterative phase estimation algorithm; however, it does not require any initial estimate of an eigenvector, and as in the classical case its convergence and the required number of iterations are directly related to the eigengap. If the amount of the gap is in the order of $1/poly(n)$, then the algorithm can converge to the dominant eigenvalue in $O(poly(n))$ time. The method can be potentially used for solving any eigenvalue related problem and finding minimum/maximum of a data set in lieu of Grover's search algorithm. In addition, if the solution space of an optimization problem with $n$ parameters is encoded as the eigenspace of an $2^n$ dimensional unitary operator in $O(poly(n))$ time and the eigengap is not too small, then the solution for such a problem can be found in $O(poly(n))$. As an example, using the quantum gates, we show how to generate the solution space of the quadratic unconstrained binary optimization as the eigenvectors of a diagonal unitary matrix and find the solution for the problem.

DOI
10.3906/elk-1910-99

Related papers

On the quantum version of the shifted power method

Ammar Daskin

In this paper, we present a direct quantum adaptation of the classical shifted power method. The method is very similar to the iterative phase estimation algorithm; however, it does not require any initial estimate of an eigenvector and as in the classical case its convergence (the success probability) is directly related to the eigengap. If the amount of the gap is polynomial in the number of qubits $n$, then the algorithm can converge to the dominant eigenvalue in $O(poly(n))$ time. The method can be potentially used in any eigenvalue related problems and to find minimum/maximum of a quantum state in lieu of Grover's search algorithm. In addition, if the solution space of an optimization problem with $n$ parameters can be encoded as the eigenspace of an $2^n$ dimensional unitary operator in $O(poly(n))$ time, then the solution for such a problem can be found in $O(poly(n))$ if the eigengap is polynomial. As an example, using the quantum gates, we show how to generate the solution space of the quadratic unconstrained binary optimization as eigenvectors of a diagonal unitary matrix and find the solution for the problem.

•Sep 5, 2018•0 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 estimates for classical polynomial optimization

Oleg Evnin

The problem of finding lower and upper bounds on multivariate homogeneous polynomials is both difficult and important given its applications to questions ranging from dynamical stability in complex potential landscapes to data analysis. From the standpoint of tensor eigenvalue theory, the question is equivalent to finding the smallest and the largest eigenvalues of the coefficient tensor corresponding to the given polynomial. Standard approaches outlined in the literature amount to running nonlinear iterations in search for the optimal rays along which the growth of the polynomial is fastest or slowest. Unlike the case of matrices (or their corresponding multivariate quadratic forms) convergence of such algorithms for higher-rank tensors is capricious due to the complex topography of polynomial objective functions. In this essay, a very different strategy, inspired by quantum-mechanical variational methods, is introduced for finding bounds on polynomials. The original polynomial is replaced by an operator acting in a suitably chosen (large) space of states, such that in an appropriate "classical" limit this operator approaches the original polynomial expression made of commutative variables. As a result, approximating the smallest and largest eigenvalues of the coefficient tensor, and thus finding bounds on polynomials, amounts to diagonalizing the resulting quantum operator, represented as a large matrix, and then inspecting the smallest and largest eigenvalues of this matrix. This approach is then successfully applied to standard test examples from tensor eigenvalue literature and other problems of interest in mathematical physics including Strichartz-type inequalities.

math-phCross-listedarXiv:2607.25445•Jul 29, 2026•0 citations

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

Fixed-Point Grover Adaptive Search for Quadratic Binary Optimization Problems

Ákos Nagy, Jaime Park, Cindy Zhang +2 more

In this article, we study a Grover-type method for quadratic unconstrained binary optimization (QUBO) problems. For an$n$-dimensional QUBO problem with$m$nonzero terms, we construct a marker oracle for such problems with a tunable parameter,$\Lambda \in [ 1, m ] \cap \mathbb {Z}$. At$d \in \mathbb {Z}_+$precision, the oracle uses$O (n + \Lambda d)$qubits and has total depth of$O (\frac{m}{\Lambda } \log _{2} (n) + \log _{2} (d))$and a non-Clifford depth of$O (\frac{m}{\Lambda })$. Moreover, each qubit is required to be connected to at most$O (\log _{2} (\Lambda + d))$other qubits. In the case of a maximum graph cuts, as$d = 2 \left\lceil \log _{2} (n) \right\rceil$always suffices, the depth of the marker oracle can be made as shallow as$O (\log _{2} (n))$. For all values of$\Lambda$, the non-Clifford gate count of these oracles is strictly lower (at least by a factor of$\sim 2$) than previous constructions. Furthermore, we introduce a novel fixed-point Grover adaptive search for QUBO problems, using our oracle design and a hybrid fixed-point Grover search, motivated by the works of Boyer et al. (1988) and Li et al. (2019). This method has better performance guarantees than previous Grover adaptive search methods. Some of our results are novel and useful for any method based on the fixed-point Grover search. Finally, we give a heuristic argument that, with high probability and in$O (\frac{\log _{2} (n)}{\sqrt{\epsilon }})$time, this adaptive method finds a configuration that is among the best$\epsilon 2^{n}$ones.

arXiv:2311.05592•IEEE Transactions on Quantum Engineering•Jan 1, 2024•3 citations

Solving Quadratic Unconstrained Binary Optimization with divide-and-conquer and quantum algorithms

Gian Giacomo Guerreschi

Quadratic Unconstrained Binary Optimization (QUBO) is a broad class of optimization problems with many practical applications. To solve its hard instances in an exact way, known classical algorithms require exponential time and several approximate methods have been devised to reduce such cost. With the growing maturity of quantum computing, quantum algorithms have been proposed to speed up the solution by using either quantum annealers or universal quantum computers. Here we apply the divide-and-conquer approach to reduce the original problem to a collection of smaller problems whose solutions can be assembled to form a single Polynomial Binary Unconstrained Optimization instance with fewer variables. This technique can be applied to any QUBO instance and leads to either an all-classical or a hybrid quantum-classical approach. When quantum heuristics like the Quantum Approximate Optimization Algorithm (QAOA) are used, our proposal leads to a double advantage: a substantial reduction of quantum resources, specifically an average of ~42% fewer qubits to solve MaxCut on random 3-regular graphs, together with an improvement in the quality of the approximate solutions reached.

arXiv:2101.07813•Jan 19, 2021•12 citations
In this paper, we present a direct quantum adaptation of the classical shifted power method. The method is very similar to the iterative phase estimation algorithm; however, it does not require any initial estimate of an eigenvector, and as in the classical case its convergence and the required number of iterations are directly related to the eigengap. If the amount of the gap is in the order of 1/poly(n)1/poly(n)1/poly(n), then the algorithm can converge to the dominant eigenvalue in O(poly(n))O(poly(n))O(poly(n)) time. The method can be potentially used for solving any eigenvalue related problem and finding minimum/maximum of a data set in lieu of Grover's search algorithm. In addition, if the solution space of an optimization problem with nnn parameters is encoded as the eigenspace of an 2n2^n2n dimensional unitary operator in O(poly(n))O(poly(n))O(poly(n)) time and the eigengap is not too small, then the solution for such a problem can be found in O(poly(n))O(poly(n))O(poly(n)). As an example, using the quantum gates, we show how to generate the solution space of the quadratic unconstrained binary optimization as the eigenvectors of a diagonal unitary matrix and find the solution for the problem.
In this paper, we present a direct quantum adaptation of the classical shifted power method. The method is very similar to the iterative phase estimation algorithm; however, it does not require any initial estimate of an eigenvector and as in the classical case its convergence (the success probability) is directly related to the eigengap. If the amount of the gap is polynomial in the number of qubits nnn, then the algorithm can converge to the dominant eigenvalue in O(poly(n))O(poly(n))O(poly(n)) time. The method can be potentially used in any eigenvalue related problems and to find minimum/maximum of a quantum state in lieu of Grover's search algorithm. In addition, if the solution space of an optimization problem with nnn parameters can be encoded as the eigenspace of an 2n2^n2n dimensional unitary operator in O(poly(n))O(poly(n))O(poly(n)) time, then the solution for such a problem can be found in O(poly(n))O(poly(n))O(poly(n)) if the eigengap is polynomial. As an example, using the quantum gates, we show how to generate the solution space of the quadratic unconstrained binary optimization as eigenvectors of a diagonal unitary matrix and find the solution for the problem.
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.
The problem of finding lower and upper bounds on multivariate homogeneous polynomials is both difficult and important given its applications to questions ranging from dynamical stability in complex potential landscapes to data analysis. From the standpoint of tensor eigenvalue theory, the question is equivalent to finding the smallest and the largest eigenvalues of the coefficient tensor corresponding to the given polynomial. Standard approaches outlined in the literature amount to running nonlinear iterations in search for the optimal rays along which the growth of the polynomial is fastest or slowest. Unlike the case of matrices (or their corresponding multivariate quadratic forms) convergence of such algorithms for higher-rank tensors is capricious due to the complex topography of polynomial objective functions. In this essay, a very different strategy, inspired by quantum-mechanical variational methods, is introduced for finding bounds on polynomials. The original polynomial is replaced by an operator acting in a suitably chosen (large) space of states, such that in an appropriate "classical" limit this operator approaches the original polynomial expression made of commutative variables. As a result, approximating the smallest and largest eigenvalues of the coefficient tensor, and thus finding bounds on polynomials, amounts to diagonalizing the resulting quantum operator, represented as a large matrix, and then inspecting the smallest and largest eigenvalues of this matrix. This approach is then successfully applied to standard test examples from tensor eigenvalue literature and other problems of interest in mathematical physics including Strichartz-type inequalities.
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.
In this article, we study a Grover-type method for quadratic unconstrained binary optimization (QUBO) problems. For annnn-dimensional QUBO problem withmmmnonzero terms, we construct a marker oracle for such problems with a tunable parameter,Λ∈[1,m]∩Z\Lambda \in [ 1, m ] \cap \mathbb {Z}Λ∈[1,m]∩Z. Atd∈Z+d \in \mathbb {Z}_+d∈Z+​precision, the oracle usesO(n+Λd)O (n + \Lambda d)O(n+Λd)qubits and has total depth ofO(mΛlog⁡2(n)+log⁡2(d))O (\frac{m}{\Lambda } \log _{2} (n) + \log _{2} (d))O(Λm​log2​(n)+log2​(d))and a non-Clifford depth ofO(mΛ)O (\frac{m}{\Lambda })O(Λm​). Moreover, each qubit is required to be connected to at mostO(log⁡2(Λ+d))O (\log _{2} (\Lambda + d))O(log2​(Λ+d))other qubits. In the case of a maximum graph cuts, asd=2⌈log⁡2(n)⌉d = 2 \left\lceil \log _{2} (n) \right\rceild=2⌈log2​(n)⌉always suffices, the depth of the marker oracle can be made as shallow asO(log⁡2(n))O (\log _{2} (n))O(log2​(n)). For all values ofΛ\LambdaΛ, the non-Clifford gate count of these oracles is strictly lower (at least by a factor of∼2\sim 2∼2) than previous constructions. Furthermore, we introduce a novel fixed-point Grover adaptive search for QUBO problems, using our oracle design and a hybrid fixed-point Grover search, motivated by the works of Boyer et al. (1988) and Li et al. (2019). This method has better performance guarantees than previous Grover adaptive search methods. Some of our results are novel and useful for any method based on the fixed-point Grover search. Finally, we give a heuristic argument that, with high probability and inO(log⁡2(n)ϵ)O (\frac{\log _{2} (n)}{\sqrt{\epsilon }})O(ϵ​log2​(n)​)time, this adaptive method finds a configuration that is among the bestϵ2n\epsilon 2^{n}ϵ2nones.
Quadratic Unconstrained Binary Optimization (QUBO) is a broad class of optimization problems with many practical applications. To solve its hard instances in an exact way, known classical algorithms require exponential time and several approximate methods have been devised to reduce such cost. With the growing maturity of quantum computing, quantum algorithms have been proposed to speed up the solution by using either quantum annealers or universal quantum computers. Here we apply the divide-and-conquer approach to reduce the original problem to a collection of smaller problems whose solutions can be assembled to form a single Polynomial Binary Unconstrained Optimization instance with fewer variables. This technique can be applied to any QUBO instance and leads to either an all-classical or a hybrid quantum-classical approach. When quantum heuristics like the Quantum Approximate Optimization Algorithm (QAOA) are used, our proposal leads to a double advantage: a substantial reduction of quantum resources, specifically an average of ~42% fewer qubits to solve MaxCut on random 3-regular graphs, together with an improvement in the quality of the approximate solutions reached.