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.
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.
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.
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(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), whose action on each Jordan block involves the derivatives of P, and not merely the map λ↦P(λ).
Given the ability to apply an unknown quantum channel acting on a d-dimensional system, we develop a quantum algorithm for transforming its singular values. The spectrum of a quantum channel as a superoperator is naturally tied to its Liouville representation, which is in general non-Hermitian. Our key contribution is an approximate block-encoding scheme for this representation in a Hermitized form, given only black-box access to the channel; this immediately allows us to apply polynomial transformations to the channel's singular values by quantum singular value transformation (QSVT). We then demonstrate an O(d3/δ) upper bound and an Ω(d/δ) lower bound for the query complexity of constructing a quantum channel that is δ-close in diamond norm to a block-encoding of the unnormalized Hermitized Liouville representation. We show our method applies practically to the problem of learning the q-th singular value moments of unknown quantum channels for arbitrary q>2,q∈R, which has implications for testing if a quantum channel is entanglement breaking. Our results establish a general framework for manipulating black-box quantum channels with QSVT and related methods, enabling direct evaluation of the channel's spectral properties without tomography or significant classical post-processing.
Non-Hermitian many-body systems can be spectrally unstable, so small perturbations may induce large eigenvalue shifts. The pseudospectrum quantifies this instability and provides a perturbation-robust diagnostic. For inverse-polynomially small ε, we show that deciding whether a point z∈C is ε-close to the spectrum is PSPACE-hard for 5-local operators, whereas deciding whether z lies in the ε-pseudospectrum is QMA-complete for 4-local operators. This identifies pseudospectrum membership as a more realistic computational target. We then present a concrete quantum framework for deciding pseudospectrum membership, which combines a singular-value estimation step with a dissipative state preparation algorithm. Our Quantum Singular-value Gaussian-filtered Search (QSIGS) combines quantum singular value transformation (QSVT) with classical post-processing to achieve Heisenberg-limited query scaling for singular-value estimation. To prepare suitable input states, we introduce an algorithmic Lindbladian protocol for approximate ground right singular vectors and prove its effectiveness for the Hatano--Nelson model. Finally, we demonstrate the full pipeline on a trapped-ion quantum computer and distinguish points inside and outside the target pseudospectrum near the exceptional point of a minimal non-Hermitian qubit model.
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 generatenFourier coefficients with 0 (poly log (n)) 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 M is s-sparse, the complexity is O(sρ2κ2/ε2) for diagonalizable matrices that only have real eigenvalues, and 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.