⚛️ quantum physics

Quantum algorithms for optimal control: large-scale finite-horizon linear-quadratic regulation

This paper presents quantum algorithms that solve large-scale finite-horizon linear-quadratic regulation problems by reformulating them as multiple-shooting linear systems with horizon-independent condition numbers, achieving polylogarithmic scaling in system size and control duration without requiring the explicit construction of a Riccati solution operator.

Original authors: Xiajie Huang, Cristina Álvarez Yuste, Nikita Guseynov, Nana Liu, Javier González-Conde

Published 2026-10-20

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Xiajie Huang, Cristina Álvarez Yuste, Nikita Guseynov, Nana Liu, Javier González-Conde

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a world where machines must make split-second decisions to stay balanced, where power grids must adjust instantly to shifting demand, or where spacecraft must navigate complex trajectories with perfect precision. In all these cases, engineers rely on a mathematical framework known as optimal control. The goal is simple: guide a system from a starting point to a desired destination while using the least amount of energy or time possible. For decades, the most reliable tool for solving these problems has been a method called linear-quadratic regulation. It works beautifully when the system behaves in a straight, predictable line and the cost of making mistakes grows in a smooth, predictable way. However, when the time window for the task is fixed and finite—say, a specific number of seconds for a drone to land or a power plant to stabilize—the math becomes incredibly difficult. The equations required to find the perfect path involve a complex, non-linear puzzle that grows exponentially harder as the system gets larger or the time window stretches longer. Classical computers, the ones we use today, often hit a wall here, struggling to crunch the numbers fast enough to be useful for large-scale, real-time applications.

A team of researchers has now developed a new approach that uses the principles of quantum computing to bypass these bottlenecks. Instead of trying to solve the difficult non-linear puzzle directly, they found a way to reframe the entire problem. They took the standard equations that describe how a system moves and how the cost of errors accumulates, and combined them into a single, massive system of linear equations. Think of it as taking a tangled knot of strings and laying them out flat on a table; while the knot is hard to untie, the flat arrangement is easy to measure. By organizing the problem this way, they transformed a chaotic, time-dependent challenge into a structured, static one. This new formulation allows them to use a specialized quantum algorithm designed to solve linear systems, a task where quantum computers are known to hold a significant advantage over their classical counterparts.

The researchers proved that this new method works efficiently even for very long time periods and very large systems, provided the system is stable enough to be controlled. They demonstrated that the difficulty of the calculation does not explode as the time window gets longer, a problem that has plagued previous attempts. In fact, they showed that for a specific family of systems—like a long chain of masses connected by springs, which is a common model for everything from bridges to molecular chains—the difficulty of the calculation grows so slowly that it becomes almost negligible as the system gets bigger. This means that a quantum computer could, in theory, find the optimal control inputs for a massive system in a fraction of the time it would take a classical supercomputer.

To ensure their theory was sound, the team ran extensive numerical experiments on a classical computer to simulate how their method would behave. They tested three different types of systems: the chain of masses and springs, a line of vehicles following a leader, and a chemical reaction spreading through a field. In every case, the simulations confirmed that their mathematical reformulation was accurate and that the system remained well-behaved, or "well-conditioned," regardless of how long the simulation ran or how many parts the system had. They found that the method could estimate the best possible cost and the exact control actions needed at any specific moment with high precision. The results suggest that for systems with a fixed number of control inputs, the time required to find the solution grows so slowly with the size of the system that it is effectively constant for practical purposes.

This work does not claim to have solved every control problem in existence, nor does it claim that quantum computers are ready to run these algorithms on hardware available today. The researchers are clear that their findings are based on theoretical proofs and simulations. However, they have established a clear path forward. By proving that the underlying mathematical structure of these problems can be tamed and made efficient for quantum processing, they have removed a major theoretical barrier. Their findings suggest that once quantum hardware matures, it will be possible to solve large-scale, time-sensitive control problems that are currently out of reach, potentially revolutionizing how we manage complex infrastructure, guide autonomous vehicles, and stabilize critical energy systems. The key insight is that by changing the perspective on the problem, the impossible becomes merely difficult, and the difficult becomes manageable.

Technical Summary: Quantum Algorithms for Large-Scale Finite-Horizon Linear-Quadratic Regulation

Problem Formulation
This work addresses the computational challenge of solving the continuous-time finite-horizon Linear-Quadratic Regulator (LQR) problem for large-scale systems. The problem involves minimizing a quadratic cost functional over a prescribed time interval $[0, T]$ subject to linear dynamics $\dot{x}(t) = Ax(t) + Bu(t)$ . Unlike infinite-horizon LQR, which reduces to an Algebraic Riccati Equation (ARE), the finite-horizon case requires solving a time-dependent Differential Riccati Equation (DRE). Classical numerical methods for the DRE are computationally expensive for large state dimensions ( $n$ ) and long horizons ( $T$ ), often scaling polynomially or worse with these parameters. Furthermore, existing quantum approaches for nonlinear matrix differential equations, such as those based on Möbius transformations, have been shown to suffer from condition numbers that grow exponentially with the time horizon $T$ , rendering them impractical for long-duration control tasks.

Methodology
The authors propose a quantum algorithmic framework that avoids direct solution of the nonlinear Riccati equation. Instead, the method reformulates the optimal control problem using Pontryagin's Maximum Principle (PMP), which yields a linear two-point boundary-value problem (TPBVP) involving the state $x(t)$ and the costate $\lambda(t)$ .

Multiple-Shooting Reformulation: The continuous TPBVP is discretized using a Gauss–Legendre Runge–Kutta scheme. The state and costate variables at temporal grid points are collected into a vector $q$ , and the evolution equations along with boundary conditions are assembled into a large, sparse linear system $L_{ex}q = b$ . This "multiple-shooting" approach transforms the differential control problem into a linear algebra problem.
Conditioning Analysis via Riccati–Lyapunov Decoupling: A critical theoretical contribution is the proof that the condition number of the resulting linear system, $\kappa(L_{ex})$ , is bounded uniformly with respect to the time horizon $T$ , provided the system satisfies stabilizability and detectability assumptions. The authors achieve this by applying a Riccati–Lyapunov change of variables that decouples the system into forward-stable and backward-stable subsystems. This transformation separates growing modes, ensuring that the influence of grid points decays exponentially with their separation, thereby preventing the exponential blow-up of the condition number with $T$ .
Quantum Linear Systems Algorithm (QLSA): The linear system is solved using a Quantum Linear Systems Algorithm (QLSA) based on Quantum Singular Value Transformation (QSVT) and block-encoding techniques. The algorithm constructs block-encodings of the system matrices and the inverse of the discretized operator.
Output Extraction: The algorithm does not output the full classical trajectory. Instead, it provides classical estimates of the optimal cost $J^*$ and the optimal control vector $u^*(t_k)$ at a single, selected temporal grid point $t_k$ . These quantities are extracted via Hadamard tests and amplitude estimation applied to the quantum state representing the solution.

Key Contributions and Results

Horizon-Uniform Conditioning: The paper establishes a rigorous bound on the condition number of the multiple-shooting linear system that is independent of the time horizon $T$ . This result relies on the exponential decay of the closed-loop propagator under stabilizability and detectability, a property proven to hold uniformly for a family of coupled mass-spring chains.
Complexity Scaling: Under the assumption of sparse-matrix block-encodings and bounded stability parameters, the query and gate complexities of the proposed quantum algorithms scale polylogarithmically with the state dimension $n$ $n$ and the time horizon $T$ $T$ . Specifically:
- Optimal-cost estimation: $\tilde{O}(\varepsilon^{-1} \text{polylog}(n, d, T))$ .
- Optimal-control estimation: $\tilde{O}(d^{3/2}\varepsilon^{-1} \text{polylog}(n, d, T))$ .
  Here, $\varepsilon$ is the target error, $d$ is the control dimension, and $\tilde{O}$ suppresses logarithmic factors in the error and failure probability.
Dimension-Uniform Example: The authors demonstrate that for a specific family of coupled mass-spring chains with fixed endpoint controls, the stability parameters and matrix norms remain bounded independent of the number of masses. This confirms that the polylogarithmic scaling holds for physically relevant, large-scale systems with bounded total initial energy.
Numerical Validation: Classical numerical experiments on mass-spring chains, vehicle platoons, and reaction-diffusion systems validate the theoretical conditioning bounds and the accuracy of the Gauss discretization. The experiments confirm that the condition number remains stable as the horizon increases and that the discretization error decreases rapidly with the number of Runge-Kutta stages.

Significance and Claims
The paper claims to provide a foundational step toward quantum acceleration for large-scale optimal control. By reformulating the finite-horizon LQR problem as a linear system with a horizon-independent condition number, the authors overcome a major barrier that previously limited quantum approaches to this domain (specifically, the exponential dependence on $T$ found in prior DRE linearization methods).

The significance lies in the ability to estimate optimal costs and controls for high-dimensional systems over long time intervals with resources that scale efficiently (polylogarithmically) rather than exponentially. The work emphasizes that the Riccati and Lyapunov solutions are used solely for the theoretical conditioning analysis and are not computed by the quantum algorithm, thereby avoiding the overhead of solving nonlinear equations on a quantum computer. The authors maintain a modest scope, focusing on the estimation of specific quantities at selected time points rather than the reconstruction of the full classical control trajectory, which would require readout at every node. The results are presented as a theoretical framework supported by numerical evidence, with future work suggested for preconditioning weakly damped systems and refining resource bounds for specific control functionals.

More like this