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 algorithms for the polynomial eigenvalue problems.

Changpeng Shao, Jin-Peng Liu

Published Oct 28, 2020• 0 citations
OpenAlex

Abstract

Polynomial eigenvalue problems (PEPs) arise in a variety of science and engineering applications, and many breakthroughs in the development of classical algorithms to solve PEPs have been made in the past decades. Here we attempt to solve PEPs in a quantum computer. Firstly, for generalized eigenvalue problems (GEPs) $A\x = \lambda B\x$ with $A,B$ symmetric, and $B$ positive definite, we give a quantum algorithm based on block-encoding and quantum phase estimation. In a more general case when $B$ is invertible, $B^{-1}A$ is diagonalizable and all the eigenvalues are real, we propose a quantum algorithm based on the Fourier spectral method to solve ordinary differential equations (ODEs). The inputs of our algorithms can be any desired states, and the outputs are superpositions of the eigenpairs. The complexities are polylog in the matrix size and linear in the precision. The dependence on precision is optimal. Secondly, we show that when $B$ is singular, any quantum algorithm uses at least $\Omega(\sqrt{n})$ queries to compute the eigenvalues, where $n$ is the matrix size. Thirdly, based on the linearization method and the connection between PEPs and higher-order ODEs, we provide two quantum algorithms to solve PEPs by extending the quantum algorithm for GEPs. We also give detailed complexity analysis of the algorithm for two special types of quadratic eigenvalue problems that are important in practice. Finally, under an extra assumption, we propose a quantum algorithm to solve PEPs when the eigenvalues are complex.

Related papers

Computing eigenvalues of diagonalizable matrices in a quantum computer

Changpeng Shao

Solving linear systems and computing eigenvalues are two fundamental problems in linear algebra. For solving linear systems, many efficient quantum algorithms have been discovered. For computing eigenvalues, currently, we have efficient quantum algorithms for Hermitian and unitary matrices. However, the general case is far from fully understood. Combining quantum phase estimation, quantum algorithm to solve linear differential equations and quantum singular value estimation, we propose two quantum algorithms to compute the eigenvalues of diagonalizable matrices that only have real eigenvalues and normal matrices. The output of the quantum algorithms is a superposition of the eigenvalues and the corresponding eigenvectors. The complexities are dominated by solving a linear system of ODEs and performing quantum singular value estimation, which usually can be solved efficiently in a quantum computer. In the special case when the matrix $M$ is $s$-sparse, the complexity is $\widetilde{O}(sρ^2 κ^2/ε^2)$ for diagonalizable matrices that only have real eigenvalues, and $\widetilde{O}(sρ\|M\|_{\max} /ε^2)$ for normal matrices. Here $ρ$ is an upper bound of the eigenvalues, $κ$ is the conditioning of the eigenvalue problem, and $ε$ is the precision to approximate the eigenvalues. We also extend the quantum algorithm to diagonalizable matrices with complex eigenvalues under an extra assumption.

arXiv:1912.08015•Dec 17, 2019•12 citations

Computing Eigenvalues of Diagonalizable Matrices on a Quantum Computer

Changpeng Shao

Computing eigenvalues of matrices is ubiquitous in numerical linear algebra problems. Currently, fast quantum algorithms for estimating eigenvalues of Hermitian and unitary matrices are known. However, the general case is far from fully understood in the quantum case. Based on a quantum algorithm for solving linear ordinary differential equations, we show how to estimate the eigenvalues of diagonalizable matrices that only have real eigenvalues. The output is a superposition of the eigenpairs, and the overall complexity is polylog in the dimension for sparse matrices. Under an assumption, we extend the algorithm to diagonalizable matrices with complex eigenvalues.

ACM Transactions on Quantum Computing•Apr 13, 2022•16 citations

Solving generalized eigenvalue problems by ordinary differential equations on a quantum computer

Changpeng Shao, Jin-Peng Liu

Many eigenvalue problems arising in practice are often of the generalized form A x = λ B x . One particularly important case is symmetric, namely A , B are Hermitian and B is positive definite. The standard algorithm for solving this class of eigenvalue problems is to reduce them to Hermitian eigenvalue problems. For a quantum computer, quantum phase estimation is a useful technique to solve Hermitian eigenvalue problems. In this work, we propose a new quantum algorithm for symmetric generalized eigenvalue problems using ordinary differential equations. The algorithm has lower complexity than the standard one based on quantum phase estimation. Moreover, it works for a wider case than symmetric: B is invertible, B − 1 A is diagonalizable and all the eigenvalues are real.

arXiv:2010.15027•Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences•Jun 1, 2022•14 citations

Computing eigenvalues of matrices in a quantum computer

Changpeng Shao

Eigenproblem arises in a large number of disciplines of sciences and engineering. Combining quantum algorithms to solve linear differential equations, quantum singular value estimation and quantum phase estimation, we propose quantum algorithms to compute the eigenvalues of diagonalizable matrices of two types: matrices that only have real eigenvalues and normal matrices. The quantum algorithms return a quantum state such that the first register stores eigenvalues and the second register stores the corresponding eigenvectors. For normal matrices, the complexity to obtain this quantum state is dominated by the complexity to perform quantum singular value estimation. For the other case, the complexity is determined by the solving of a linear system of differential equations. Under certain conditions (e.g. sparse), the complexities are polylog on the size $n$ of the given matrix. If we perform measurements, then we can obtain all the eigenvalues classically. If $M$ is $s$ sparse, then the complexity is $\widetilde{O}(sn\|M\|_{\max}\kappa^2/\epsilon^2)$, where $\kappa$ is the condition number of the matrix of eigenvectors.

•Dec 17, 2019•4 citations

Efficient quantum algorithm for solving differential equations with Fourier nonlinearity via Koopman linearization

Judd Katz, Gopikrishnan Muraleedharan, Abhijeet Alase

Quantum algorithms offer an exponential advantage with respect to the number of dependent variables for solving certain nonlinear ordinary differential equations (ODEs). These algorithms typically begin by transforming the original nonlinear ODE into a higher-dimensional linear ODE using a linearization technique, most commonly Carleman linearization. Existing works restrict their analysis to ODEs where the nonlinearities are polynomial functions of the dependent variables, significantly limiting their applicability. In this work we construct an efficient quantum algorithm for solving ODEs with `Fourier' nonlinear terms expressible as $d{\bf u}/dt = G_0 + G_1 e^{i{\bf u}}$, where ${\bf u}$ denotes a vector of $n$ complex variables evolving with $t$, $G_0$ is an $n$-dimensional complex vector, $G_1$ is an $n \times n$ complex matrix and $e^{i{\bf u}}$ denotes the vector with entries $\{e^{iu_j}\}$. To tackle the Fourier nonlinear term, which is not expressible as a finite sum of polynomials of ${\bf u}$, our algorithm employs a generalization of the Carleman linearization technique known as Koopman linearization. We also make other methodological advances towards relaxing the stringent dissipativity condition required for efficient solution extraction and towards integrated readout of classical quantities from the solution state. Our results open avenues to the development of efficient quantum algorithms for a significantly wider class of high-dimensional nonlinear ODEs, thereby broadening the scope of their applications.

quant-pharXiv:2512.06488•Dec 9, 2025•4 citations

Quantum oblique eigenprojection

Alexander M. Dalzell, Yuan Su

Every square matrix decomposes its underlying Hilbert space into generalized, nonorthogonal eigensubspaces. We show that a quantum computer can perform such an oblique eigenprojection $Π$ given block encoding access to the input matrix. Our approach has a query complexity nearly linear in the inverse gap and a normalization factor close to $\lVertΠ\rVert$ under a spectral-set condition on the input. This covers common assumptions on the numerical range or diagonalizability and matches known results for orthogonal eigenprojections. We achieve this with a two-sided block preconditioning that uses a discrete Fourier transform of the matrix resolvent. We describe applications to: (i) preparing eigenstates of matrices with complex eigenvalues, extending the quantum eigenvalue transformation algorithm of Low and Su beyond real spectra; (ii) solving continuous-time algebraic Riccati equations, cubically speeding up a prior solver of Rodenas-Ruiz, Zhao, and Lee; and (iii) solving ordinary Sylvester equations, quadratically improving a direct augmented method of Wang and Liu. Our result suggests a promising route to applying nonanalytic matrix functions on quantum computers.

quant-pharXiv:2609.40254•Oct 1, 2026•1 citation
Polynomial eigenvalue problems (PEPs) arise in a variety of science and engineering applications, and many breakthroughs in the development of classical algorithms to solve PEPs have been made in the past decades. Here we attempt to solve PEPs in a quantum computer. Firstly, for generalized eigenvalue problems (GEPs) A\x=λB\xA\x = \lambda B\xA\x=λB\x with A,BA,BA,B symmetric, and BBB positive definite, we give a quantum algorithm based on block-encoding and quantum phase estimation. In a more general case when BBB is invertible, B−1AB^{-1}AB−1A is diagonalizable and all the eigenvalues are real, we propose a quantum algorithm based on the Fourier spectral method to solve ordinary differential equations (ODEs). The inputs of our algorithms can be any desired states, and the outputs are superpositions of the eigenpairs. The complexities are polylog in the matrix size and linear in the precision. The dependence on precision is optimal. Secondly, we show that when BBB is singular, any quantum algorithm uses at least Ω(n)\Omega(\sqrt{n})Ω(n​) queries to compute the eigenvalues, where nnn is the matrix size. Thirdly, based on the linearization method and the connection between PEPs and higher-order ODEs, we provide two quantum algorithms to solve PEPs by extending the quantum algorithm for GEPs. We also give detailed complexity analysis of the algorithm for two special types of quadratic eigenvalue problems that are important in practice. Finally, under an extra assumption, we propose a quantum algorithm to solve PEPs when the eigenvalues are complex.
Solving linear systems and computing eigenvalues are two fundamental problems in linear algebra. For solving linear systems, many efficient quantum algorithms have been discovered. For computing eigenvalues, currently, we have efficient quantum algorithms for Hermitian and unitary matrices. However, the general case is far from fully understood. Combining quantum phase estimation, quantum algorithm to solve linear differential equations and quantum singular value estimation, we propose two quantum algorithms to compute the eigenvalues of diagonalizable matrices that only have real eigenvalues and normal matrices. The output of the quantum algorithms is a superposition of the eigenvalues and the corresponding eigenvectors. The complexities are dominated by solving a linear system of ODEs and performing quantum singular value estimation, which usually can be solved efficiently in a quantum computer. In the special case when the matrix MMM is sss-sparse, the complexity is O~(sρ2κ2/ε2)\widetilde{O}(sρ^2 κ^2/ε^2)O(sρ2κ2/ε2) for diagonalizable matrices that only have real eigenvalues, and O~(sρ∥M∥max⁡/ε2)\widetilde{O}(sρ\|M\|_{\max} /ε^2)O(sρ∥M∥max​/ε2) for normal matrices. Here ρρρ is an upper bound of the eigenvalues, κκκ is the conditioning of the eigenvalue problem, and εεε is the precision to approximate the eigenvalues. We also extend the quantum algorithm to diagonalizable matrices with complex eigenvalues under an extra assumption.
Computing eigenvalues of matrices is ubiquitous in numerical linear algebra problems. Currently, fast quantum algorithms for estimating eigenvalues of Hermitian and unitary matrices are known. However, the general case is far from fully understood in the quantum case. Based on a quantum algorithm for solving linear ordinary differential equations, we show how to estimate the eigenvalues of diagonalizable matrices that only have real eigenvalues. The output is a superposition of the eigenpairs, and the overall complexity is polylog in the dimension for sparse matrices. Under an assumption, we extend the algorithm to diagonalizable matrices with complex eigenvalues.
Many eigenvalue problems arising in practice are often of the generalized form A x = λ B x . One particularly important case is symmetric, namely A , B are Hermitian and B is positive definite. The standard algorithm for solving this class of eigenvalue problems is to reduce them to Hermitian eigenvalue problems. For a quantum computer, quantum phase estimation is a useful technique to solve Hermitian eigenvalue problems. In this work, we propose a new quantum algorithm for symmetric generalized eigenvalue problems using ordinary differential equations. The algorithm has lower complexity than the standard one based on quantum phase estimation. Moreover, it works for a wider case than symmetric: B is invertible, B − 1 A is diagonalizable and all the eigenvalues are real.
Eigenproblem arises in a large number of disciplines of sciences and engineering. Combining quantum algorithms to solve linear differential equations, quantum singular value estimation and quantum phase estimation, we propose quantum algorithms to compute the eigenvalues of diagonalizable matrices of two types: matrices that only have real eigenvalues and normal matrices. The quantum algorithms return a quantum state such that the first register stores eigenvalues and the second register stores the corresponding eigenvectors. For normal matrices, the complexity to obtain this quantum state is dominated by the complexity to perform quantum singular value estimation. For the other case, the complexity is determined by the solving of a linear system of differential equations. Under certain conditions (e.g. sparse), the complexities are polylog on the size nnn of the given matrix. If we perform measurements, then we can obtain all the eigenvalues classically. If MMM is sss sparse, then the complexity is O~(sn∥M∥max⁡κ2/ϵ2)\widetilde{O}(sn\|M\|_{\max}\kappa^2/\epsilon^2)O(sn∥M∥max​κ2/ϵ2), where κ\kappaκ is the condition number of the matrix of eigenvectors.
Quantum algorithms offer an exponential advantage with respect to the number of dependent variables for solving certain nonlinear ordinary differential equations (ODEs). These algorithms typically begin by transforming the original nonlinear ODE into a higher-dimensional linear ODE using a linearization technique, most commonly Carleman linearization. Existing works restrict their analysis to ODEs where the nonlinearities are polynomial functions of the dependent variables, significantly limiting their applicability. In this work we construct an efficient quantum algorithm for solving ODEs with `Fourier' nonlinear terms expressible as du/dt=G0+G1eiud{\bf u}/dt = G_0 + G_1 e^{i{\bf u}}du/dt=G0​+G1​eiu, where u{\bf u}u denotes a vector of nnn complex variables evolving with ttt, G0G_0G0​ is an nnn-dimensional complex vector, G1G_1G1​ is an n×nn \times nn×n complex matrix and eiue^{i{\bf u}}eiu denotes the vector with entries {eiuj}\{e^{iu_j}\}{eiuj​}. To tackle the Fourier nonlinear term, which is not expressible as a finite sum of polynomials of u{\bf u}u, our algorithm employs a generalization of the Carleman linearization technique known as Koopman linearization. We also make other methodological advances towards relaxing the stringent dissipativity condition required for efficient solution extraction and towards integrated readout of classical quantities from the solution state. Our results open avenues to the development of efficient quantum algorithms for a significantly wider class of high-dimensional nonlinear ODEs, thereby broadening the scope of their applications.
Every square matrix decomposes its underlying Hilbert space into generalized, nonorthogonal eigensubspaces. We show that a quantum computer can perform such an oblique eigenprojection ΠΠΠ given block encoding access to the input matrix. Our approach has a query complexity nearly linear in the inverse gap and a normalization factor close to ∥Π∥\lVertΠ\rVert∥Π∥ under a spectral-set condition on the input. This covers common assumptions on the numerical range or diagonalizability and matches known results for orthogonal eigenprojections. We achieve this with a two-sided block preconditioning that uses a discrete Fourier transform of the matrix resolvent. We describe applications to: (i) preparing eigenstates of matrices with complex eigenvalues, extending the quantum eigenvalue transformation algorithm of Low and Su beyond real spectra; (ii) solving continuous-time algebraic Riccati equations, cubically speeding up a prior solver of Rodenas-Ruiz, Zhao, and Lee; and (iii) solving ordinary Sylvester equations, quadratically improving a direct augmented method of Wang and Liu. Our result suggests a promising route to applying nonanalytic matrix functions on quantum computers.