Abstract
We present a quantum algorithm for solving the finite-horizon discrete-time Linear Quadratic Gaussian (LQG) control problem, which integrates optimal control and state estimation in the presence of stochastic disturbances and noise. Classical approaches to LQG require solving a backward Riccati recursion and a forward Kalman filter, both requiring computationally expensive matrix operations with overall time complexity $\mathscr{O}\left(T n^{3}\right)$, where $n$ is the system dimension and $T$ is the time horizon. While efficient classical solvers exist, especially for small to medium-sized systems, their computational complexity grows rapidly with system dimension. To address this, we reformulate the full LQG pipeline using quantum linear algebra primitives, including block-encoded matrix representations and quantum singular value transformation (QSVT) techniques for matrix inversion and multiplication. We formally analyze the time complexity of each algorithmic component. Under standard assumptions on matrix condition numbers and encoding precision, the total runtime of the quantum LQG algorithm scales polylogarithmically with the system dimension $n$ and linearly with the time horizon $T$, offering an asymptotic quantum speedup over classical methods.
Introduction
In modern control theory, the Linear Quadratic Gaussian (LQG) controller is the gold standard for managing linear systems subject to additive white Gaussian noise. The framework is built upon the principle of separation: it combines the Linear Quadratic Regulator (LQR) for optimal control law synthesis with the Kalman Filter for state estimation.
Despite its ubiquity, the LQG controller faces a significant computational hurdle. Solving the underlying Riccati and Kalman equations requires frequent matrix inversions and multiplications. For a system with $n$ dimensions over a time horizon $T$, classical methods scale at $O(Tn^3)$. As we look toward the future of engineering—encompassing massive power grids, complex chemical processing plants, and large-scale autonomous swarms—this cubic scaling in system dimension becomes a bottleneck for real-time optimal control. This paper proposes a quantum framework to alleviate this bottleneck, reducing the dependency on $n$ from polynomial to polylogarithmic.
Quantum Linear Algebra Primitives
To translate the LQG pipeline into a quantum-executable format, we utilize three core "Quantum Basic Linear Algebra Subprograms" (Quantum BLAS):
- Block Encodings: Quantum computers operate via unitary transformations. To process general classical matrices (like the system dynamics matrix $A$), we embed them into the top-left block of a larger unitary operator. This allows the quantum state to represent the matrix's action on a vector.
- Quantum Singular Value Transformation (QSVT): QSVT serves as a versatile tool for applying polynomial functions to the singular values of block-encoded matrices. In this framework, it is primarily used for matrix inversion ($f(x) = x^{-1}$), which is the most computationally intensive aspect of the Riccati and Kalman recursions.
- Linear Combination of Unitaries (LCU): This technique enables the addition and subtraction of matrices within the quantum circuit while maintaining the block-encoded structure, essential for the iterative nature of control algorithms.
The Quantum LQG Pipeline
The proposed algorithm decomposes the LQG problem into three distinct phases:
Phase I: The Backward Pass (Control Synthesis)
In this phase, the algorithm solves the discrete-time Riccati recursion. Starting from the terminal time $T$ and moving backward to $t=0$, the quantum circuit computes the optimal control gains. By leveraging QSVT for the necessary matrix inversions, the algorithm prepares the gain matrices in a block-encoded format.
Phase II: The Forward Pass (State Estimation)
As the system evolves, the algorithm implements a quantum version of the Kalman Filter. This phase processes noisy measurements to produce an optimal estimate of the system's state. Like the backward pass, this relies on iterative matrix updates performed via block encodings.
Phase III: Control Computation
The final phase integrates the control gains from Phase I with the state estimates from Phase II. The quantum computer calculates the final control input to be applied to the physical system.
Complexity and Results
The primary contribution of this work is the formal proof of an asymptotic speedup. The total runtime of the quantum LQG algorithm is established as:
$$O(T \cdot \text{polylog}(n/\epsilon) \cdot \kappa \log(1/\epsilon'))$$
Where:
- $n$ is the system dimension.
- $T$ is the time horizon.
- $\kappa$ is the condition number of the matrices.
- $\epsilon$ is the desired precision.
Compared to the classical $O(Tn^3)$, the quantum algorithm provides an exponential speedup with respect to the system dimension $n$. Notably, the scaling remains linear with respect to $T$. This is an inherent property of control problems; because state estimation at time $k+1$ depends on measurements at time $k$, the process is fundamentally sequential and cannot be parallelized across the time domain.
Discussion and Limitations
While this framework offers a theoretical breakthrough for large-scale control, several practical challenges remain. The algorithm assumes the existence of Quantum-Accessible Random Access Memory (QRAM) or similar data structures to efficiently load classical system matrices into quantum states. Furthermore, the implementation requires a fault-tolerant quantum computer, as the depth of the circuits needed for QSVT and LCU exceeds the capabilities of current Noisy Intermediate-Scale Quantum (NISQ) devices.
Future research will focus on the propagation of errors over long time horizons and the extension of these quantum primitives to continuous-time systems and non-Gaussian noise models. By establishing this unified framework, we provide a foundation for the next generation of high-dimensional, real-time optimal control.
Summary updated