Abstract 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 ||Π|| 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. As the oblique eigenprojection serves as a fundamental primitive in the design of quantum algorithms, our result can be used to extend and improve a variety of prior results. Specifically, 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.
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
∥Π∥ 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.
We develop operator-output quantum algorithms for matrix equations and matrix functions using matrix-sign embeddings. For each problem, an augmented matrix
M is chosen so that the target operator is a block of
sign(M) or is recovered from blocks of
(I−sign(M))/2. We approximate the half-plane sign by a logarithmic-sinc formula and implement the shifted inverse families by scaled multiplexing with node-dependent rebalancing. For ordinary Sylvester equations, this yields a block-encoding of the solution with query complexity linear in the relevant conditioning parameters and logarithmic in the inverse error tolerance, under either a field-of-values (FoV) gap or a strip-resolvent bound. The same method extends to generalized Sylvester and Lyapunov equations, principal square and inverse square roots, matrix geometric means, and continuous-time algebraic Riccati equations (CARE), with explicit query-complexity and block-encoding-normalization bounds that cover non-normal and non-diagonalizable cases.
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(λ).
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.
The spectral condition number is a widely adopted measure of worst-case cost for quantum linear system solvers. Yet it can significantly overestimate the actual runtime for a typical problem instance. We present two quantum algorithms that produce the normalized solution
∣x⟩ of linear system
Ax=∣b⟩ to accuracy
ε with complexity independent of the condition number
κ=∥A−1∥. We focus on the standard input model where
A is accessed through a block encoding and
∣b⟩ is prepared by a unitary. But we also introduce an affine dilation model that encodes
A and
∣b⟩ jointly, allowing further refinements of the query complexity. Our truncation-based solver makes an optimal number of queries to
∣b⟩ and
O(κeffpolylog(εκeff)) queries to
A. We prove a family of upper bounds on the effective condition number, including
κeff≤ε1/t∥(A†A)−t/2∣x⟩∥1/t for positive even integer
t and
κeff≤ε1/t∥A−1†(A†A)−(t−1)/2∣x⟩∥1/t for positive odd
t, overcoming the
κ-barrier. Our filtering-based solver is extremely simple with a favorable runtime prefactor. In particular, the solver has query complexity
3ε∥A−1†∣x⟩∥ to leading order when the solution norm is known. We then present a similarly simple solution norm estimator with the same asymptotic cost up to logarithmic factors. Our quantum linear system solvers thus substantially improve a recent algorithm of Li, enabling faster quantum linear system solving beyond the condition number.