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

On the quantum version of the shifted power method

Ammar Daskin

Published Sep 5, 2018• 0 citations
OpenAlex

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 (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.

Related papers

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

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 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.

arXiv:1809.01378•TURKISH JOURNAL OF ELECTRICAL ENGINEERING & COMPUTER SCIENCES•Jan 7, 2020•5 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•Journal of Physics A Mathematical and Theoretical•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•168 citations

A quantum analogue of convex optimization

Eunou Lee

Convex optimization is the powerhouse behind the theory and practice of optimization. We introduce a quantum analogue of unconstrained convex optimization: computing the minimum eigenvalue of a Schrödinger operator $h = -Δ+ V $ with convex potential $V:\mathbb R^n \rightarrow \mathbb R_{\ge 0}$ such that $V(x)\rightarrow\infty $ as $\|x\|\rightarrow\infty$. For this problem, we present an efficient quantum algorithm, called the Fundamental Gap Algorithm (FGA), that computes the minimum eigenvalue of $h$ up to error $ε$ in polynomial time in $n$, $1/ε$, and parameters that depend on $V$. Adiabatic evolution of the ground state is used as a key subroutine, which we analyze with novel techniques that allow us to focus on the low-energy space. We apply the FGA to give the first known polynomial-time algorithm for finding the lowest frequency of an $n$-dimensional convex drum, or mathematically, the minimum eigenvalue of the Dirichlet Laplacian on an $n$-dimensional region that is defined by $m$ linear constraints in polynomial time in $n$, $m$, $1/ε$ and the radius $R$ of a ball encompassing the region.

arXiv:2510.02151•Oct 2, 2025•1 citation

Phase Estimation

Andreas Wichert

The Kitaev's Phase Estimation Algorithm (also referred to as quantum eigenvalue estimation algorithm) is a quantum algorithm to estimate the phase (or eigenvalue) of an eigenvector of a unitary operator. We explain the algorithm and indicate an example of the determination of the eigenvalue of the T gate. Then we introduce the quantum counting algorithm that is based on the quantum phase estimation algorithm and on the Grover's search algorithm. Quantum counting algorithm is a quantum algorithm for counting the number of solutions for a given search problem.

Chapman & Hall/CRC eBooks•Nov 28, 2023•0 citations

A Quantum Algorithm for Computing All Eigenvalues and Eigenstates of Sparse Hermitian Matrices

Krishnakanta Barik, Goutam Paul

Computation of eigenvalues and eigenvectors of a sparse Hermitian matrix is a fundamental problem in algebra, arising both as a problem of independent interest and as a key subroutine in a wide range of computational and scientific applications. In this work, we develop a quantum algorithm that determines the spectrum of a sparse Hermitian matrix, defined as the set of its distinct eigenvalues, and for each eigenvalue, prepares a corresponding eigenvector as a quantum state in its eigenspace. The eigenvalues are represented as binary strings with a prescribed precision, while the corresponding eigenvectors are kept as quantum states, eliminating the need to reconstruct their classical counterparts. The algorithm instead enables estimation of expectation values $\braket{x|M|x}$, where $\ket{x}$ is a prepared eigenstate and $M$ is an observable. For an $n \times n$ $s$-sparse Hermitian matrix $H$, dense methods based on Householder tridiagonalization and QR iteration compute all eigenvalues and eigenvectors in $\mathcal{O}(n^3)$ time. Exploiting sparsity, the Lanczos method computes all eigenvalues in $\mathcal{O}(n^2 s)$ time in exact arithmetic, but recovering all eigenvectors still requires $\mathcal{O}(n^3)$ time. In contrast, our algorithm runs in time $\tilde{\mathcal{O}}(n s^2 \log^2 n / Δ_{\min})$, where $Δ_{\min}$ denotes the minimum spectral gap of the normalized matrix. For inverse gaps up to $Δ_{\min}^{-1} = \mathcal{O}(n)$, the most favorable scaling for $n$ distinct eigenvalues, attained by nearly uniformly spaced spectra such as those of perfect-state-transfer spin chains and the Sylvester-Kac matrix, and for sparsity up to $s = o(\sqrt{n}/\log n)$, the proposed algorithm achieves an improved asymptotic runtime over the classical $\mathcal{O}(n^3)$ approach for computing all eigenvalues and eigenvectors, under standard sparse-access assumptions.

arXiv:2611.16610•Nov 12, 2026•0 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 (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.
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.
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.
Convex optimization is the powerhouse behind the theory and practice of optimization. We introduce a quantum analogue of unconstrained convex optimization: computing the minimum eigenvalue of a Schrödinger operator $h = -Δ+ V $ with convex potential V:Rn→R≥0V:\mathbb R^n \rightarrow \mathbb R_{\ge 0}V:Rn→R≥0​ such that $V(x)\rightarrow\infty $ as ∥x∥→∞\|x\|\rightarrow\infty∥x∥→∞. For this problem, we present an efficient quantum algorithm, called the Fundamental Gap Algorithm (FGA), that computes the minimum eigenvalue of hhh up to error εεε in polynomial time in nnn, 1/ε1/ε1/ε, and parameters that depend on VVV. Adiabatic evolution of the ground state is used as a key subroutine, which we analyze with novel techniques that allow us to focus on the low-energy space. We apply the FGA to give the first known polynomial-time algorithm for finding the lowest frequency of an nnn-dimensional convex drum, or mathematically, the minimum eigenvalue of the Dirichlet Laplacian on an nnn-dimensional region that is defined by mmm linear constraints in polynomial time in nnn, mmm, 1/ε1/ε1/ε and the radius RRR of a ball encompassing the region.
The Kitaev's Phase Estimation Algorithm (also referred to as quantum eigenvalue estimation algorithm) is a quantum algorithm to estimate the phase (or eigenvalue) of an eigenvector of a unitary operator. We explain the algorithm and indicate an example of the determination of the eigenvalue of the T gate. Then we introduce the quantum counting algorithm that is based on the quantum phase estimation algorithm and on the Grover's search algorithm. Quantum counting algorithm is a quantum algorithm for counting the number of solutions for a given search problem.
Computation of eigenvalues and eigenvectors of a sparse Hermitian matrix is a fundamental problem in algebra, arising both as a problem of independent interest and as a key subroutine in a wide range of computational and scientific applications. In this work, we develop a quantum algorithm that determines the spectrum of a sparse Hermitian matrix, defined as the set of its distinct eigenvalues, and for each eigenvalue, prepares a corresponding eigenvector as a quantum state in its eigenspace. The eigenvalues are represented as binary strings with a prescribed precision, while the corresponding eigenvectors are kept as quantum states, eliminating the need to reconstruct their classical counterparts. The algorithm instead enables estimation of expectation values ⟨x∣M∣x⟩\braket{x|M|x}⟨x∣M∣x⟩, where ∣x⟩\ket{x}∣x⟩ is a prepared eigenstate and MMM is an observable. For an n×nn \times nn×n sss-sparse Hermitian matrix HHH, dense methods based on Householder tridiagonalization and QR iteration compute all eigenvalues and eigenvectors in O(n3)\mathcal{O}(n^3)O(n3) time. Exploiting sparsity, the Lanczos method computes all eigenvalues in O(n2s)\mathcal{O}(n^2 s)O(n2s) time in exact arithmetic, but recovering all eigenvectors still requires O(n3)\mathcal{O}(n^3)O(n3) time. In contrast, our algorithm runs in time O~(ns2log⁡2n/Δmin⁡)\tilde{\mathcal{O}}(n s^2 \log^2 n / Δ_{\min})O~(ns2log2n/Δmin​), where Δmin⁡Δ_{\min}Δmin​ denotes the minimum spectral gap of the normalized matrix. For inverse gaps up to Δmin⁡−1=O(n)Δ_{\min}^{-1} = \mathcal{O}(n)Δmin−1​=O(n), the most favorable scaling for nnn distinct eigenvalues, attained by nearly uniformly spaced spectra such as those of perfect-state-transfer spin chains and the Sylvester-Kac matrix, and for sparsity up to s=o(n/log⁡n)s = o(\sqrt{n}/\log n)s=o(n​/logn), the proposed algorithm achieves an improved asymptotic runtime over the classical O(n3)\mathcal{O}(n^3)O(n3) approach for computing all eigenvalues and eigenvectors, under standard sparse-access assumptions.