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:2502.18119

Quantum Eigensolver for Non-Normal Matrices via Ground State Energy Estimation

Honghong Lin, Yun Shang

Published Feb 25, 2025• 0 citations
arXivHTMLPDF

Abstract

Large-scale eigenvalue problems pose a significant challenge to classical computers. While there are efficient quantum algorithms for unitary or Hermitian matrices, eigenvalue problems for non-normal matrices remain open in quantum computing. In this work, we propose a quantum algorithm that given a non-normal matrix, outputs an estimate of an eigenvalue to within additive error $ε$ with probability at least $1-p_{\rm fail}$. Our estimation strategy is to sample points on the complex plane and examine the distance between the sampled point and the eigenvalues. We show that the distance is related to the smallest singular value of the shifted matrix, hence reducing the problem to ground state energy estimation via Hermitianization. With the knowledge of an eigenvalue, we are able to prepare the associated eigenvector using ground state preparation. Our estimating scheme can also be modified to approximate the extreme eigenvalue, and in particular the spectral gap. The algorithm is implemented based on the block encoding input model and requires $O(κ^2ε^{-(2m-1)}\log(1/p_{\rm fail}))$ queries to the block encoding oracle. Our algorithm is the first general eigenvalue algorithm that achieves this scaling. We also perform numerical simulation to validate the algorithms.

DOI
10.48550/arxiv.2502.18119

Related papers

Quantum Eigenvalue Processing

Guang Hao Low, Yuan Su

Many problems in linear algebra-such as those arising from non-Hermitian physics, transcorrelated quantum chemistry and differential equations-can be solved on a quan-tum computer by processing eigenvalues of the non-normal input matrices. However, the existing Quantum Singular Value Transformation (QSVT) framework is ill-suited to this task, as eigenvalues and singular values are different in general. We present a Quantum EigenValue Transformation (QEVT) framework for applying arbitrary polynomial transformations on eigenvalues of block-encoded non-normal operators, and a related Quantum EigenValue Estimation (QEVE) algorithm for operators with real spectra. QEVT has query complexity to the block encoding nearly recovering that of the QSVT for a Hermitian input, and QEVE achieves the Heisenberg-limited scaling for diagonalizable input matrices. As applications, we develop a linear differential equation solver with strictly linear time query complexity for average-case diagonalizable operators, as well as a ground state preparation algorithm that upgrades previous nearly optimal results for Hermitian Hamiltonians to diagonalizable matrices with real spectra. Underpinning our algorithms is an efficient method to prepare a quantum super-position of Faber polynomials, which generalize the nearly-best uniform approximation properties of Chebyshev polynomials to the complex plane. Of independent interest, we also develop techniques to generate$n$Fourier coefficients with 0 (poly log ($n$)) gates compared to prior approaches with linear cost.

Annual Symposium on Foundations of Computer Science•Oct 27, 2024•12 citations

Quantum Eigenvalue Processing

Guang Hao Low, Yuan Su

Abstract. Many problems in linear algebra—such as those arising from non-Hermitian physics, transcorrelated quantum chemistry, and differential equations—can be solved on a quantum computer by processing eigenvalues of the non-normal input matrices. However, the existing Quantum Singular Value Transformation (QSVT) framework is ill-suited for this task because eigenvalues and singular values are different in general. We present a Quantum EigenValue Transformation (QEVT) framework for applying arbitrary polynomial transformations on eigenvalues of block-encoded non-normal operators and a related Quantum EigenValue Estimation (QEVE) algorithm for operators with real spectra. QEVT has query complexity to the block encoding nearly recovering that of the QSVT for a Hermitian input, and QEVE achieves the Heisenberg-limited scaling for diagonalizable input matrices. As applications, we develop a linear differential equation solver with strictly linear time query complexity for average-case diagonalizable operators, as well as a ground state preparation algorithm that upgrades previous nearly optimal results for Hermitian Hamiltonians to diagonalizable matrices with real spectra. Underpinning our algorithms is an efficient method to prepare a quantum superposition of Faber polynomials, which generalize the nearly-best uniform approximation properties of Chebyshev polynomials to the complex plane. Of independent interest, we also develop techniques to generate [Formula: see text] Fourier coefficients with [Formula: see text] gates compared to prior approaches with linear cost.

arXiv:2401.06240•SIAM Journal on Computing•Feb 12, 2026•5 citations

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•5 citations

Quantum Eigenvalue Transformations for Arbitrary Matrices

Xabier Gutiérrez, Lorenzo Laneve, Mikel Sanz

Quantum Signal Processing (QSP) and Quantum Singular Value Transformation (QSVT) provide an efficient framework for implementing polynomials of block-encoded matrices, and thus offer a systematic approach to quantum algorithm design. However, despite a number of recent advances, important limitations remain. In particular, QSP can only transform unitary matrices, by applying a polynomial to their eigenvalues, while QSVT is a singular-value transformation and thus one can only obtain the polynomial of Hermitian matrices. As a consequence, these techniques do not directly apply to an arbitrary non-Hermitian matrix that is not diagonalizable. In this work, we propose a simple yet powerful method to extend these ideas to arbitrary square matrices by acting on their eigenvalues. To this end, we introduce the notion of an $n$-regular block encoding, namely, a block encoding whose $k$-th power reproduces the $k$-th power of the encoded matrix for every $0 < k < n$. We show that applying QSP to any unitary with this property is equivalent to applying a polynomial of degree at most $n$ to the block-encoded matrix, independently of its internal structure. Moreover, we provide a simple construction that transforms any block encoding into an $n$-regular one using only $O(\log n)$ ancillary qubits and operations. Finally, we show that this construction induces the desired transformation on the eigenvalues associated with the Jordan normal form of the matrix; for non-diagonalizable matrices this yields the full matrix function $P(A)$, whose action on each Jordan block involves the derivatives of $P$, and not merely the map $λ\mapsto P(λ)$.

quant-pharXiv:2604.19688•Apr 22, 2026•0 citations

Resolvent-based quantum phase estimation: Towards estimation of parametrized eigenvalues

Abhijeet Alase, Salini Karuvade

Quantum algorithms for estimating the eigenvalues of matrices, including the phase estimation algorithm, serve as core subroutines in a wide range of quantum algorithms, including those in quantum chemistry and quantum machine learning. The standard quantum eigenvalue (phase) estimation algorithm accepts a Hermitian (unitary) matrix and a state in an unknown superposition of its eigenstates as input, and coherently records the estimates for real eigenvalues (eigenphases) in an ancillary register. Extension of quantum eigenvalue and phase estimation algorithms to the case of non-normal input matrices is obstructed by several factors such as non-orthogonality of eigenvectors, existence of generalized eigenvectors and the fact that eigenvalues may lie anywhere on the complex plane. In this work, we propose a novel approach for estimating the eigenvalues of non-normal matrices based on preparation of a state that we call the "resolvent state". We construct the first efficient algorithm for estimating the phases of the unimodular eigenvalues of a given non-unitary matrix. We then construct an efficient algorithm for estimating the real eigenvalues of a given non-Hermitian matrix, achieving complexities that match the best known results while operating under significantly relaxed assumptions on the non-real part of the spectrum. The resolvent-based approach that we introduce also extends to estimating eigenvalues that lie on a parametrized complex curve, subject to explicitly stated conditions, thereby paving the way for a new paradigm of parametric eigenvalue estimation.

arXiv:2410.04837•Oct 7, 2024•1 citation

Quantum Algorithm for Low-Energy Effective Hamiltonians and Subspace Eigenvalue Problem

Chun-Tse Li, Tze Tzen Ong, Chih‐Yun Lin +3 more

Subspace eigenvalue problems arise ubiquitously in quantum chemistry and condensed-matter physics, where the relevant object is often a low-energy manifold rather than a single ground-state wavefunction. In this work, we propose a fault-tolerant quantum algorithm for this subspace-level task based on the Feshbach effective-Hamiltonian formalism. Given block-encoding access to the full Hamiltonian and a chosen $d$-dimensional reference subspace, the algorithm estimates eigenvalues of states with nonzero overlap with the reference subspace through a local secant fixed-point search. It then implements the associated wave operator and prepares an orthonormal basis whose span approximates the target invariant subspace. The construction combines projected block encodings with quantum singular value transformation (QSVT), which approximates the complementary-space resolvent and thereby provides both the self-energy used for eigenvalue estimation and the wave operator used for eigenstate reconstruction. For target accuracy $\varepsilon$, a single evaluation of the effective Hamiltonian has query complexity $\widetilde{O}(d^3/(g^2\varepsilon))$, up to block-encoding normalization factors, where $g$ is the distance between the target eigenvalue and the nearest pole of the effective Hamiltonian. Under the stated local regularity conditions, the secant search requires only $O(\log\log(1/\varepsilon))$ effective-Hamiltonian evaluations to reach the working precision. Classical numerical emulations for an open $4\times2$ Fermi--Hubbard cluster, all-electron LiH bond stretching, and $[\mathrm{Ru(bpy)}_{3}]^{2+}$ demonstrate the resolution and reconstruction of low-energy states and manifolds across spin-sector crossings, near-degeneracies, and dense excited-state spectra.

arXiv:2510.08088•Oct 9, 2025•0 citations
Large-scale eigenvalue problems pose a significant challenge to classical computers. While there are efficient quantum algorithms for unitary or Hermitian matrices, eigenvalue problems for non-normal matrices remain open in quantum computing. In this work, we propose a quantum algorithm that given a non-normal matrix, outputs an estimate of an eigenvalue to within additive error εεε with probability at least 1−pfail1-p_{\rm fail}1−pfail​. Our estimation strategy is to sample points on the complex plane and examine the distance between the sampled point and the eigenvalues. We show that the distance is related to the smallest singular value of the shifted matrix, hence reducing the problem to ground state energy estimation via Hermitianization. With the knowledge of an eigenvalue, we are able to prepare the associated eigenvector using ground state preparation. Our estimating scheme can also be modified to approximate the extreme eigenvalue, and in particular the spectral gap. The algorithm is implemented based on the block encoding input model and requires O(κ2ε−(2m−1)log⁡(1/pfail))O(κ^2ε^{-(2m-1)}\log(1/p_{\rm fail}))O(κ2ε−(2m−1)log(1/pfail​)) queries to the block encoding oracle. Our algorithm is the first general eigenvalue algorithm that achieves this scaling. We also perform numerical simulation to validate the algorithms.
Many problems in linear algebra-such as those arising from non-Hermitian physics, transcorrelated quantum chemistry and differential equations-can be solved on a quan-tum computer by processing eigenvalues of the non-normal input matrices. However, the existing Quantum Singular Value Transformation (QSVT) framework is ill-suited to this task, as eigenvalues and singular values are different in general. We present a Quantum EigenValue Transformation (QEVT) framework for applying arbitrary polynomial transformations on eigenvalues of block-encoded non-normal operators, and a related Quantum EigenValue Estimation (QEVE) algorithm for operators with real spectra. QEVT has query complexity to the block encoding nearly recovering that of the QSVT for a Hermitian input, and QEVE achieves the Heisenberg-limited scaling for diagonalizable input matrices. As applications, we develop a linear differential equation solver with strictly linear time query complexity for average-case diagonalizable operators, as well as a ground state preparation algorithm that upgrades previous nearly optimal results for Hermitian Hamiltonians to diagonalizable matrices with real spectra. Underpinning our algorithms is an efficient method to prepare a quantum super-position of Faber polynomials, which generalize the nearly-best uniform approximation properties of Chebyshev polynomials to the complex plane. Of independent interest, we also develop techniques to generatennnFourier coefficients with 0 (poly log (nnn)) gates compared to prior approaches with linear cost.
Abstract. Many problems in linear algebra—such as those arising from non-Hermitian physics, transcorrelated quantum chemistry, and differential equations—can be solved on a quantum computer by processing eigenvalues of the non-normal input matrices. However, the existing Quantum Singular Value Transformation (QSVT) framework is ill-suited for this task because eigenvalues and singular values are different in general. We present a Quantum EigenValue Transformation (QEVT) framework for applying arbitrary polynomial transformations on eigenvalues of block-encoded non-normal operators and a related Quantum EigenValue Estimation (QEVE) algorithm for operators with real spectra. QEVT has query complexity to the block encoding nearly recovering that of the QSVT for a Hermitian input, and QEVE achieves the Heisenberg-limited scaling for diagonalizable input matrices. As applications, we develop a linear differential equation solver with strictly linear time query complexity for average-case diagonalizable operators, as well as a ground state preparation algorithm that upgrades previous nearly optimal results for Hermitian Hamiltonians to diagonalizable matrices with real spectra. Underpinning our algorithms is an efficient method to prepare a quantum superposition of Faber polynomials, which generalize the nearly-best uniform approximation properties of Chebyshev polynomials to the complex plane. Of independent interest, we also develop techniques to generate [Formula: see text] Fourier coefficients with [Formula: see text] gates compared to prior approaches with linear cost.
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.
Quantum Signal Processing (QSP) and Quantum Singular Value Transformation (QSVT) provide an efficient framework for implementing polynomials of block-encoded matrices, and thus offer a systematic approach to quantum algorithm design. However, despite a number of recent advances, important limitations remain. In particular, QSP can only transform unitary matrices, by applying a polynomial to their eigenvalues, while QSVT is a singular-value transformation and thus one can only obtain the polynomial of Hermitian matrices. As a consequence, these techniques do not directly apply to an arbitrary non-Hermitian matrix that is not diagonalizable. In this work, we propose a simple yet powerful method to extend these ideas to arbitrary square matrices by acting on their eigenvalues. To this end, we introduce the notion of an nnn-regular block encoding, namely, a block encoding whose kkk-th power reproduces the kkk-th power of the encoded matrix for every 0<k<n0 < k < n0<k<n. We show that applying QSP to any unitary with this property is equivalent to applying a polynomial of degree at most nnn to the block-encoded matrix, independently of its internal structure. Moreover, we provide a simple construction that transforms any block encoding into an nnn-regular one using only O(log⁡n)O(\log n)O(logn) ancillary qubits and operations. Finally, we show that this construction induces the desired transformation on the eigenvalues associated with the Jordan normal form of the matrix; for non-diagonalizable matrices this yields the full matrix function P(A)P(A)P(A), whose action on each Jordan block involves the derivatives of PPP, and not merely the map λ↦P(λ)λ\mapsto P(λ)λ↦P(λ).
Quantum algorithms for estimating the eigenvalues of matrices, including the phase estimation algorithm, serve as core subroutines in a wide range of quantum algorithms, including those in quantum chemistry and quantum machine learning. The standard quantum eigenvalue (phase) estimation algorithm accepts a Hermitian (unitary) matrix and a state in an unknown superposition of its eigenstates as input, and coherently records the estimates for real eigenvalues (eigenphases) in an ancillary register. Extension of quantum eigenvalue and phase estimation algorithms to the case of non-normal input matrices is obstructed by several factors such as non-orthogonality of eigenvectors, existence of generalized eigenvectors and the fact that eigenvalues may lie anywhere on the complex plane. In this work, we propose a novel approach for estimating the eigenvalues of non-normal matrices based on preparation of a state that we call the "resolvent state". We construct the first efficient algorithm for estimating the phases of the unimodular eigenvalues of a given non-unitary matrix. We then construct an efficient algorithm for estimating the real eigenvalues of a given non-Hermitian matrix, achieving complexities that match the best known results while operating under significantly relaxed assumptions on the non-real part of the spectrum. The resolvent-based approach that we introduce also extends to estimating eigenvalues that lie on a parametrized complex curve, subject to explicitly stated conditions, thereby paving the way for a new paradigm of parametric eigenvalue estimation.
Subspace eigenvalue problems arise ubiquitously in quantum chemistry and condensed-matter physics, where the relevant object is often a low-energy manifold rather than a single ground-state wavefunction. In this work, we propose a fault-tolerant quantum algorithm for this subspace-level task based on the Feshbach effective-Hamiltonian formalism. Given block-encoding access to the full Hamiltonian and a chosen ddd-dimensional reference subspace, the algorithm estimates eigenvalues of states with nonzero overlap with the reference subspace through a local secant fixed-point search. It then implements the associated wave operator and prepares an orthonormal basis whose span approximates the target invariant subspace. The construction combines projected block encodings with quantum singular value transformation (QSVT), which approximates the complementary-space resolvent and thereby provides both the self-energy used for eigenvalue estimation and the wave operator used for eigenstate reconstruction. For target accuracy ε\varepsilonε, a single evaluation of the effective Hamiltonian has query complexity O~(d3/(g2ε))\widetilde{O}(d^3/(g^2\varepsilon))O(d3/(g2ε)), up to block-encoding normalization factors, where ggg is the distance between the target eigenvalue and the nearest pole of the effective Hamiltonian. Under the stated local regularity conditions, the secant search requires only O(log⁡log⁡(1/ε))O(\log\log(1/\varepsilon))O(loglog(1/ε)) effective-Hamiltonian evaluations to reach the working precision. Classical numerical emulations for an open 4×24\times24×2 Fermi--Hubbard cluster, all-electron LiH bond stretching, and [Ru(bpy)3]2+[\mathrm{Ru(bpy)}_{3}]^{2+}[Ru(bpy)3​]2+ demonstrate the resolution and reconstruction of low-energy states and manifolds across spin-sector crossings, near-degeneracies, and dense excited-state spectra.