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.
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
nFourier coefficients with 0 (poly log (
n)) gates compared to prior approaches with linear cost.
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−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)) 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.
Quantum Singular Value Transformation (QSVT) provides a unified framework for applying polynomial functions to the singular values of a block-encoded matrix. QSVT prepares a state proportional to $\bA^{-1}\bb$ with circuit depth
O(d⋅polylog(N)), where
d is the polynomial degree of the
1/x approximation and
N is the size of $\bA$. Current polynomial approximation methods are over the continuous interval
[a,1], giving $d = O(\sqrt{\kap}\log(1/\varepsilon))$, and make no use of any properties of $\bA$.
We observe here that QSVT solution accuracy depends only on the polynomial accuracy at the eigenvalues of $\bA$. When all
N eigenvalues are known exactly, a pure spectral polynomial
pS can interpolate
1/x at these eigenvalues and achieve unit fidelity at reduced degree. But its practical applicability is limited. To address this, we propose a spectral correction that exploits prior knowledge of
K eigenvalues of $\bA$. Given any base polynomial
p0, such as Remez, of degree
d0, a
K×K linear system enforces exact interpolation of
1/x only at these
K eigenvalues without increasing
d0. The spectrally corrected polynomial
pSC preserves the continuous error profile between eigenvalues and inherits the parity of
p0.
QSVT experiments on the 1D Poisson equation demonstrate up to a
5× reduction in circuit depth relative to the base polynomial, at unit fidelity and improved compliance error. The correction is agnostic to the choice of base polynomial and robust to eigenvalue perturbations up to
10% relative error. Extension to the 2D Poisson equation suggests that correcting a small fraction of the spectrum may suffice to achieve fidelity above
0.999.
Abstract Stability is a fundamental property of dynamical systems, and Lyapunov theory provides a rigorous link between stability and eigenvalue distribution. By computing eigenvalues, quantum algorithms may offer potential advantages for evaluating the stability of high-dimensional systems under appropriate assumptions regarding data access and quantum resource requirements. In this work, we introduce a quantum algorithm based on the quantum singular value transformation (QSVT) to efficiently resolve the complex eigenspectrum of non-Hermitian matrices and determine asymptotic stability. By employing block encoding and QSVT techniques, we implement a polynomial transformation to approximate the singular value threshold problem, enabling the localization of eigenvalues with positive real parts under appropriate requirements regarding block encoding efficiency, matrix conditioning, state overlap, and precision. We validate the method numerically on a one-dimensional non-Hermitian spin-1/2 chain with local gain and loss, demonstrating accurate detection of unstable and stable cases, which is consistent with the results obtained by exact diagonalization. These results show that our quantum algorithm is a reliable and powerful tool for stability analysis and spectral characterization of high-dimensional dynamical systems.
Non-Hermitian systems offer new opportunities for quantum optimization and computation. Here, we show that non-Hermitian quantum adiabatic algorithms require not only a real, gapped spectrum, but also a stable pseudospectrum. We propose a novel framework by mapping non-unitary quantum circuits to local Hamiltonian paths, thereby preserving their optimization advantages and shallow depth. While a direct non-Hermitian extension of the Feynman-Kitaev construction suffers severe pseudospectral instability, our history-decoupled construction yields both a controlled pseudospectrum and a real, gapped spectrum. Using the CK benchmark family of maximum independent set problems, we demonstrate polynomial-evolution-time non-Hermitian adiabatic computation that remains robust against perturbations. We further discuss a feasible optical implementation using coupled waveguides with an auxiliary lossy channel. Our work establishes pseudospectral stability, alongside real, gapped spectra, as key principles and a practical route for non-Hermitian quantum adiabatic computation.