arXiv:2610.26843
Quantum algorithms for optimal control: large-scale finite-horizon linear-quadratic regulation
Xiajie Huang, Cristina Álvarez Yuste, Nikita Guseynov, Nana Liu, Javier González-Conde
Abstract
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.
AI Summary
The paper addresses quantum computation of continuous-time finite-horizon linear-quadratic regulation (LQR) for a fixed initial state. It targets classical estimates of the optimal cost and the optimal control vector at one selected temporal grid point, rather than a Riccati solution operator or the full control trajectory. The method formulates the linear state–costate two-point boundary-value problem as a multiple-shooting linear system $Lq=b$. Under stabilizability and detectability, it proves a condition-number bound independent of the horizon $T$ at fixed step size $h$; under refinement, the bound scales as $O(h^{-1})$. A Riccati–Lyapunov transformation separates forward- and backward-decaying propagation for the analysis, without being computed by the algorithm. High-order Gauss–Legendre discretization, QSVT inverse block-encodings, and amplitude estimation then yield the requested outputs. With bounded sparsity, norms, stability parameters, and initial-state norm, the simplified complexities are $\widetilde O(\varepsilon^{-1}\operatorname{polylog}(n,d,2+T))$ for cost and $\widetilde O(d^{3/2}\varepsilon^{-1}\operatorname{polylog}(n,d,2+T))$ for control. The paper establishes dimension- and horizon-uniform parameter bounds for damped, on-site-pinned mass–spring chains with two endpoint controls and bounded total initial energy. Classical numerical tests examine conditioning and discretization errors. The complexity claims assume sparse-matrix block-encodings, initial-state preparation, and supplied norm and stability bounds. Stability constants need not scale mildly with dimension in general; bounded energy per mass does not suffice for the chain result. Full-trajectory output requires separate readout at each requested node.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.