Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2507.09841 · IEEE International Conference on Quantum Computing and Engineering (QCE)

Quantum Solution Framework for Finite-Horizon LQG Control via Block Encodings and QSVT

Nahid Binandeh Dehaghani, Rafał Wiśniewski, A. Pedro Aguiar

Published Aug 30, 2025• 2 citations
arXivHTMLPDF

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.

DOI
10.1109/qce65121.2025.00040

Related papers

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

Xiajie Huang, Cristina Álvarez Yuste, Nikita Guseynov +2 more

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.

quant-pharXiv:2610.26843•Oct 20, 2026•0 citations

Quantum-Assisted Barrier Sequential Quadratic Programming for Nonlinear Optimal Control

Nahid Binandeh Dehaghani, Rafał Wiśniewski, A. Pedro Aguiar

We propose a quantum-assisted framework for solving constrained finite-horizon nonlinear optimal control problems using a barrier Sequential Quadratic Programming (SQP) approach. A quantum subroutine is incorporated to efficiently solve the Schur complement step using block-encoding and Quantum Singular Value Transformation techniques. We formally analyze the time complexity and convergence behavior under the cumulative effect of quantum errors, establishing local input-to-state stability and convergence to a neighborhood of the stationary point, with explicit error bounds in terms of the barrier parameter and quantum solver accuracy. The proposed framework enables computational complexity to scale polylogarithmically with the system dimension demonstrating the potential of quantum algorithms to enhance classical optimization routines in nonlinear control applications.

arXiv:2510.18116•IEEE Control Systems Letters•Jan 1, 2025•1 citation

Near-Optimal Quantum Algorithm and Complexity Analysis for Riccati Problems

Jingyao Wang, Yanqiao Wang, Bowen Li +2 more

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.

quant-pharXiv:2609.37207•Sep 30, 2026•0 citations

A quantum algorithm for the Kalman filter using block encoding

Hao Jie Shi, Guofeng Zhang, Ming Zhang

Quantum algorithms offer significant speed-ups over their classical counterparts in various applications. In this paper, we develop quantum algorithms for the Kalman filter widely used in classical control engineering using the block encoding method. The entire calculation process is achieved by performing matrix operations on Hamiltonians based on the block encoding framework, including addition, multiplication, and inversion, which can be completed in a unified framework compared to previous quantum algorithms for solving control problems. We demonstrate that the quantum algorithm exponentially accelerates the computation of the Kalman filter compared to traditional methods. The time complexity can be reduced from $O(n^3)$ to $O(κpoly\log(n/ε)\log(1/ε'))$, where $n$ represents the matrix dimension, $κ$ denotes the condition number for the matrix to be inverted, $ε$ indicates desired precision in block encoding, $ε'$ signifies desired precision in matrix inversion. This paper provides a comprehensive quantum solution for implementing the Kalman filter and serves as an attempt to broaden the scope of quantum computation applications. Finally, we present an illustrative example implemented in Qiskit (a Python-based open-source toolkit) as a proof-of-concept.

arXiv:2404.04554•Apr 6, 2024•0 citations

A QSVT-Based Quantum Jacobi Algorithm for Linear Systems with Application to the Poisson Equation

Louisa M. Piskol, Thorsten Grahs, Stefan Langer +1 more

Many computational fluid dynamics (CFD) algorithms solve partial differential equations by discretization, resulting in large and sparse systems of linear equations. While iterative methods are widely used to solve these systems classically, most existing quantum linear system solvers target the solution through matrix inversion rather than approximating it using an iterative procedure. In this work, we develop a quantum implementation of the Jacobi method based on quantum singular value transformation (QSVT). By reformulating the Jacobi iteration as a polynomial transformation of a block-encoded operator, the algorithm requires only a constant ancilla overhead with respect to the number of iterations while maintaining a circuit depth that scales linearly with the iteration number. We demonstrate the algorithm for one- and two-dimensional Poisson problems, including the pressure Poisson equation arising in Chorin's projection method for the lid-driven cavity flow. The proposed algorithm provides a promising building block for future quantum implementations of multigrid methods and preconditioning techniques, bringing quantum algorithms closer to established CFD solution strategies.

quant-pharXiv:2609.24266•Sep 22, 2026•0 citations

Adiabatic Quantum Linear Optimal Control for Discrete Time Dynamical Systems

Mayank Jha, Prasanna Date

This paper presents a novel approach for solving finite-horizon linear optimal control based on block-Toeplitz least-squares problem, by recasting the latter as Quadratic Unconstrained Binary Optimization (QUBO) suitable for adiabatic quantum computing (AQC). Classical block-Toeplitz leastsquares problem, scales as$O\left((N m)^{3}\right)$for horizon length$N$and control dimension$m$. We demonstrate that this Toeplitzstructured least-squares cost can be transformed into a QUBO formulation by introducing binary precision vectors that encode each continuous control parameter into finite number of bits. We establish the general case in mathematically rigorous manner wherein the total number of binary decision variables remain dependent on$N$. To respect current quantum annealer capabilities, we propose a basis-function parametrization that approximates the full control sequence with a small set of basis coefficients, reducing the total number of binary-variables and rendering the latter independent of$N$. Through simulation study, we show that, for large datasets, the QUBO pipeline, comprising of hardware-constant anneal step outperforms classical least square based solvers by several factors whilst demonstrating acceptable accuracy.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Aug 30, 2025•0 citations
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 complexityO(Tn3)\mathscr{O}\left(T n^{3}\right)O(Tn3), wherennnis the system dimension andTTTis 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 dimensionnnnand linearly with the time horizonTTT, offering an asymptotic quantum speedup over classical methods.
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 propose a quantum-assisted framework for solving constrained finite-horizon nonlinear optimal control problems using a barrier Sequential Quadratic Programming (SQP) approach. A quantum subroutine is incorporated to efficiently solve the Schur complement step using block-encoding and Quantum Singular Value Transformation techniques. We formally analyze the time complexity and convergence behavior under the cumulative effect of quantum errors, establishing local input-to-state stability and convergence to a neighborhood of the stationary point, with explicit error bounds in terms of the barrier parameter and quantum solver accuracy. The proposed framework enables computational complexity to scale polylogarithmically with the system dimension demonstrating the potential of quantum algorithms to enhance classical optimization routines in nonlinear control applications.
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α)Θ(\mathcal Rα)Θ(Rα) up to logarithmic factors, with the generalized singularity factor R\mathcal RR that reflects spectral separation, and the output normalization ααα. For DREs and finite-horizon problems, the query complexity has an additional initialization conditioning factor κinitκ_{\rm init}κ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.
Quantum algorithms offer significant speed-ups over their classical counterparts in various applications. In this paper, we develop quantum algorithms for the Kalman filter widely used in classical control engineering using the block encoding method. The entire calculation process is achieved by performing matrix operations on Hamiltonians based on the block encoding framework, including addition, multiplication, and inversion, which can be completed in a unified framework compared to previous quantum algorithms for solving control problems. We demonstrate that the quantum algorithm exponentially accelerates the computation of the Kalman filter compared to traditional methods. The time complexity can be reduced from O(n3)O(n^3)O(n3) to O(κpolylog⁡(n/ε)log⁡(1/ε′))O(κpoly\log(n/ε)\log(1/ε'))O(κpolylog(n/ε)log(1/ε′)), where nnn represents the matrix dimension, κκκ denotes the condition number for the matrix to be inverted, εεε indicates desired precision in block encoding, ε′ε'ε′ signifies desired precision in matrix inversion. This paper provides a comprehensive quantum solution for implementing the Kalman filter and serves as an attempt to broaden the scope of quantum computation applications. Finally, we present an illustrative example implemented in Qiskit (a Python-based open-source toolkit) as a proof-of-concept.
Many computational fluid dynamics (CFD) algorithms solve partial differential equations by discretization, resulting in large and sparse systems of linear equations. While iterative methods are widely used to solve these systems classically, most existing quantum linear system solvers target the solution through matrix inversion rather than approximating it using an iterative procedure. In this work, we develop a quantum implementation of the Jacobi method based on quantum singular value transformation (QSVT). By reformulating the Jacobi iteration as a polynomial transformation of a block-encoded operator, the algorithm requires only a constant ancilla overhead with respect to the number of iterations while maintaining a circuit depth that scales linearly with the iteration number. We demonstrate the algorithm for one- and two-dimensional Poisson problems, including the pressure Poisson equation arising in Chorin's projection method for the lid-driven cavity flow. The proposed algorithm provides a promising building block for future quantum implementations of multigrid methods and preconditioning techniques, bringing quantum algorithms closer to established CFD solution strategies.
This paper presents a novel approach for solving finite-horizon linear optimal control based on block-Toeplitz least-squares problem, by recasting the latter as Quadratic Unconstrained Binary Optimization (QUBO) suitable for adiabatic quantum computing (AQC). Classical block-Toeplitz leastsquares problem, scales asO((Nm)3)O\left((N m)^{3}\right)O((Nm)3)for horizon lengthNNNand control dimensionmmm. We demonstrate that this Toeplitzstructured least-squares cost can be transformed into a QUBO formulation by introducing binary precision vectors that encode each continuous control parameter into finite number of bits. We establish the general case in mathematically rigorous manner wherein the total number of binary decision variables remain dependent onNNN. To respect current quantum annealer capabilities, we propose a basis-function parametrization that approximates the full control sequence with a small set of basis coefficients, reducing the total number of binary-variables and rendering the latter independent ofNNN. Through simulation study, we show that, for large datasets, the QUBO pipeline, comprising of hardware-constant anneal step outperforms classical least square based solvers by several factors whilst demonstrating acceptable accuracy.