Near-Optimal Quantum Algorithm and Complexity Analysis for Riccati Problems
Abstract
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 Θ(ℛα) up to logarithmic factors, with the generalized singularity factor ℛ 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.
Related
- Sub-Infinite Horizon Stochastic Linear-Quadratic Optimal Control Problems and Delayed Backward Riccati Equations
- Lifted Restricted Isometry Property and Fast Algorithm for Spectral Compressed Sensing With Near-Optimal Sample Complexity
- A Low-rank ADI Algorithm for the Numerical Solution of Large Discrete-time Non-symmetric Algebraic Riccati Equations
- D-RADI: A Low-rank ADI Algorithm for Solving Large-scale Discrete-time Algebraic Riccati Equations
- Constrained Mean Variance Portfolio Selection under Reflected Factor Dynamics: Stochastic Riccati Equations, Neumann Problems,and a Deep Solver
BibTeX
@misc{wang2026nearoptimal,
title = {{Near-Optimal Quantum Algorithm and Complexity Analysis for Riccati Problems}},
author = {Jingyao Wang and Yanqiao Wang and Bowen Li and Jin-Peng Liu and Zhengfeng Ji},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.37207},
eprint = {2609.37207},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.37207},
}
RIS
TY - UNPB
TI - Near-Optimal Quantum Algorithm and Complexity Analysis for Riccati Problems
AU - Jingyao Wang
AU - Yanqiao Wang
AU - Bowen Li
AU - Jin-Peng Liu
AU - Zhengfeng Ji
PY - 2026
DA - 2026/10/20
PB - arXiv
DO - 10.48550/arxiv.2609.37207
UR - https://arxiv.org/abs/2609.37207
AB - 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 Θ(ℛα) up to logarithmic factors, with the generalized singularity factor ℛ 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.
ER -