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 $\text{sign}(M)$ or is recovered from blocks of $(I-\text{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.
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.
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.
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.
Determining whether every trajectory of the linear system x˙=Ax converges to zero (or, equivalently, whether A is Hurwitz stable) is a fundamental problem in control theory. It arises, for example, in verifying the stability of feedback controllers and state observers, as well as of linearized dynamical models. We study the quantum query complexity of deciding whether a matrix A∈Cn×n is Hurwitz stable, given an exact normalized block-encoding of A. The query complexity is characterized in terms of the system dimension n and a supplied lower bound 0<ν≤ωA on the imaginary-axis distance ωA:=mint∈Rσmin(A−itI), where σmin(A) is the smallest singular value of A. We prove a query-complexity lower bound of Ω(n/ν), which holds even when A is restricted to be real and diagonal. For general matrices with nonzero ωA, we encode an approximation of the right-half-plane spectral projector sign+(A):=(I+sign(A))/2 as a block of a matrix inverse, where A is Hurwitz if and only if the projector is zero. To test this, we produce a quantum algorithm which determines if a (β,b,1/(4n))-block-encoded projector matrix (like sign+(A)) is zero or not; for constant success probability, it has complexity Θ(βn). When the zero test is applied to specific approximations of sign+(A), this yields an upper bound of O(nν−2log(n/ν)) queries in the general case, and O(nν−1logn) when A is Hermitian or normal. The latter upper bound matches the lower bound up to a logarithmic factor. Thus the dimension dependence of quantum Hurwitz testing is nearly optimal, while the remaining factor in the non-normal case isolates an open conditioning gap.
We present a quantum algorithm for solving algebraic Riccati equations, with applications to quantum-chemical random-phase approximation (RPA) and higher-order RPA theories. Our method block-encodes stabilizing Riccati solutions via Riesz projectors onto invariant subspaces of an associated non-normal matrix, implemented using contour-integral resolvents and quantum singular value transformations. Applied to m-particle, m-hole RPA, our algorithm yields a block-encoding of the amplitude solution and estimates the electronic correlation-energy density with it. Under localized-orbital sparsity assumptions, the end-to-end cost scales linearly with system size and polynomially with excitation rank m, suggesting an exponential advantage in m over plausible classical local-correlation heuristics. More broadly, this work provides a framework for quantum algorithms for nonlinear matrix equations in quantum chemistry and opens a possible route toward developing quantum algorithms for coupled-cluster theory.
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.
We develop quantum algorithms that construct block-encodings of solution matrices for continuous- and discrete-time algebraic Riccati equations (CAREs and DAREs), differential Riccati equations (DREs), and finite Riccati recursions. The Quantum Weighted Riesz Method, unifying four kinds of Riccati problems, constructs projectors onto the solution graphs using weighted Riesz branching operators and recovers the solution matrices. Under the stated access and normalization assumptions, our algorithms for CAREs and DAREs have near-optimal query complexity Θ(Rα) up to logarithmic factors, with the generalized singularity factor R that reflects spectral separation, and the output normalization α. For DREs and finite-horizon problems, the query complexity has an additional initialization conditioning factor κinit. We establish product query lower bounds for specified input-oracle families, demonstrating necessary joint dependence on spectral separation and initialization or output scale. We also prove that selected-value promise problems are BQP-complete on explicit circuit-generated families of single-control discrete-time algebraic and zero-terminal differential Riccati equations. Applications include classical feedback evaluation for linear-quadratic control, a query-complexity comparison for stable random-phase approximation Riccati equations in quantum chemistry, and heated boundary control with numerical validation.