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 $Θ(\mathcal Rα)$ up to logarithmic factors, with the generalized singularity factor $\mathcal R$ that reflects spectral separation, and the output normalization $α$. For DREs and finite-horizon problems, the query complexity has an additional initialization conditioning factor $κ_{\rm 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.
AI Summary
The paper studies quantum construction of block-encodings of solutions to continuous- and discrete-time algebraic Riccati equations (CARE/DARE), differential Riccati equations (DRE), and finite Riccati recursions. The output is an operator encoding, not an explicit classical solution matrix.
Its “Quantum Weighted Riesz Method” embeds each problem in a Hamiltonian matrix or regular pencil, constructs weighted spectral-branch operators using contour-resolvent LCU, and recovers the solution from complete graph-projector block rows via a pseudoinverse. For dynamics, a decaying graph projector combines forward evolution on the decaying branch with inverse evolution on the growing branch, retaining the initial data without directly encoding exponentially growing flow.
Under stated access and normalization assumptions, query costs are $\widetilde O(\mathcal R\alpha)$ for CARE/DARE and $\widetilde O(\mathcal R\kappa_{\rm init}\alpha)$ for dynamic problems. Here $\mathcal R$ measures normalized resolvent conditioning, $\alpha$ is the actual output normalization, and $\kappa_{\rm init}$ describes projected-initial-data conditioning. Explicit oracle pairs and hybrid arguments establish matching algebraic product lower bounds and multiplicative dynamic lower bounds. Circuit reductions establish BQP-complete selected-value problems for single-control DARE and zero-terminal DRE families.
Applications include scalar feedback readout, a two-mode RPA comparison reducing energy-query scaling from $\widetilde O(u^{-3}/\varepsilon)$ to $\widetilde O(u^{-2}/\varepsilon)$, and dimension-independent query bounds for a fixed-parameter thermal network. Limitations include supplied contour/inverse estimates, initialization-rank promises, potentially large output normalizations, and separate state-preparation/readout costs. Optimality is family-specific; the RPA comparison does not establish advantage over optimized alternatives, and thermal-network scaling does not cover fixed-domain mesh refinement.
Little sign of AI-generated textStrong assumptionsUnclear novelty
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
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.
The paper studies quantum construction of block-encodings of solutions to continuous- and discrete-time algebraic Riccati equations (CARE/DARE), differential Riccati equations (DRE), and finite Riccati recursions. The output is an operator encoding, not an explicit classical solution matrix.
Its “Quantum Weighted Riesz Method” embeds each problem in a Hamiltonian matrix or regular pencil, constructs weighted spectral-branch operators using contour-resolvent LCU, and recovers the solution from complete graph-projector block rows via a pseudoinverse. For dynamics, a decaying graph projector combines forward evolution on the decaying branch with inverse evolution on the growing branch, retaining the initial data without directly encoding exponentially growing flow.
Under stated access and normalization assumptions, query costs are O(Rα) for CARE/DARE and O(Rκinitα) for dynamic problems. Here R measures normalized resolvent conditioning, α is the actual output normalization, and κinit describes projected-initial-data conditioning. Explicit oracle pairs and hybrid arguments establish matching algebraic product lower bounds and multiplicative dynamic lower bounds. Circuit reductions establish BQP-complete selected-value problems for single-control DARE and zero-terminal DRE families.
Applications include scalar feedback readout, a two-mode RPA comparison reducing energy-query scaling from O(u−3/ε) to O(u−2/ε), and dimension-independent query bounds for a fixed-parameter thermal network. Limitations include supplied contour/inverse estimates, initialization-rank promises, potentially large output normalizations, and separate state-preparation/readout costs. Optimality is family-specific; the RPA comparison does not establish advantage over optimized alternatives, and thermal-network scaling does not cover fixed-domain mesh refinement.
We develop quantum algorithms for optimal control over a prescribed finite time interval (finite horizon), focusing on continuous-time linear-quadratic regulation (LQR). This foundational control problem often requires solving a nonlinear matrix Riccati equation, which can be costly for large systems and long control durations on conventional classical solvers. We instead work directly with the state-costate optimality equations, reformulating the LQR problem as a multiple-shooting linear system. Importantly, we prove a condition-number bound for the system that is independent of the horizon, under stabilizability and detectability assumptions. By incorporating the initial and final conditions into a single linear system, we can solve the subsequent linear system more efficiently with a quantum linear systems subroutine. For a given initial state, our quantum algorithms return classical estimates of the optimal cost and the optimal control inputs at a selected time, without constructing a Riccati solution operator. Given sparse-matrix block-encodings, an initial-state preparation oracle and a fixed number of control inputs, the query and gate complexities scale polylogarithmically with system size and control duration, provided that sparsity, relevant norms, and stability parameters are bounded. The dependence on the target error is inverse-linear up to logarithmic factors. We establish the required bounds uniformly in system size and duration for a family of damped mass-spring chains with two endpoint controls. Numerical experiments support the analysis.
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.
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.
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 develop Multivariate Quantum Signal Processing for designing matrix-valued transformations of multiple noncommuting nonnormal block-encoded matrices. Our framework equips quantum transducers with the analytic structure of multiport Infinite-Impulse-Response (IIR) filters and establishes a transfer-function methodology for designing quantum query algorithms. Efficiently computable analytic bounds that hold uniformly across the oracle promise yield efficient quantum circuits with logarithmic error dependence and near-unity success probability, paralleling the approximation-theoretic guarantees of univariate QSP/QSVT. We provide a complete characterization of achievable transfer functions and a principled library of analytic IIR components. Our modular designs greatly improve or resolve the per-oracle query complexity of open multi-oracle problems: (1) Hamiltonian simulation under H=∑jHj with weighted quasinorm cost ≈t⟨λ,C⟩1/2+O(∥C∥1log(1/ε)) for block-encoding normalizations λ and costs C; (2) sparse simulation with optimal time--norm Θ(d∥H∥1→2t) and additive error dependence; (3) solving linear systems and (4) differential equations under minimal matrix assumptions with optimal weighted state-preparation and multi-term cost; (5) ground-state preparation and energy estimation; (6) generalized eigenvalue problems. We apply these to exactly simulate downfolded Hamiltonians with leading cost t⟨λeff,Ceff⟩1/2 further reduced by fractional dynamic correlation energy contributions from coarse-grained Hamiltonians, and show similar classical-data-input-reduction results for multiscale graph classification via Kron reduction. We also show the online generalization with anisotropic Kalman filtering of streaming quantum data.
Quantum linear systems algorithms (QLSAs) aim to solve linear systems $A\bb{x}=\bb{b}$ exponentially faster than classical methods under certain conditions. In this work, we develop quantum algorithms for solving linear algebraic equations from an ODE-based perspective. Inspired by the linear combination of Hamiltonian simulation (LCHS) representation in the Fourier approach \cite{Childs2017QLSA}, we express the solution $\bb{x}$ as a linear combination of solutions to a system of linear convection equations, which become Schrödinger-type equations with unitary evolutions in the Fourier domain. We refer to this representation as LC-Schrödingerization. Based on this result, we construct an LCHS-based quantum algorithm with two LCHS instances: one for time-marching and one for numerical integration. The key construction uses the derivative of a Gaussian-smoothed hat function and recovers the solution over a fixed auxiliary interval. This permits a truncation time independent of the target accuracy and avoids the loss in success probability from selecting a single grid point. Periodization and explicit Fourier coefficients provide the corresponding projection error bounds. Under the stated oracle assumptions and given a constant-factor estimate of the solution norm, direct simulation of the select operators and block preconditioning achieve the optimal matrix-query complexity O(κAlogε1) without using variable-time amplitude amplification (VTAA). The same upper bound holds for queries to the right-hand-side preparation oracle.