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:2404.04554

A quantum algorithm for the Kalman filter using block encoding

Hao Jie Shi, Guofeng Zhang, Ming Zhang

Published Apr 6, 2024• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2404.04554

Related papers

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

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

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.

arXiv:2507.09841•IEEE International Conference on Quantum Computing and Engineering (QCE)•Aug 30, 2025•2 citations

From Block-encoding to Generalized Quantum Signal Processing: Principles, Algorithms and Applications

Tal Gurfinkel, Kaushika De Silva, Anuradha Mahasinghe +9 more

Modern quantum algorithms are increasingly formulated as coherent procedures for implementing polynomial transformations of operators and singular values. This perspective provides a powerful and unifying language for quantum algorithm design, connecting a wide range of distinct problems through five closely related key tools: block-encoding, qubitization, QSP, QSVT and GQSP. Block-encoding embeds non-unitary matrices into larger unitaries; qubitization converts block-encodings into structured operators; QSP, QSVT and GQSP enable polynomial transformations with near-optimal query complexity. Together, these techniques form a general toolkit for transforming matrix functions into implementable quantum circuits. This paper develops these techniques from first principles as a unified framework for constructing quantum algorithms. We apply this framework to representative applications to highlight design principles and demonstrate how distinct algorithms can be constructed from a unified sequence of operator transformations. A central contribution is a systematic decision workflow for selecting the appropriate approach according to the operator structure and the desired transformation polynomial. This perspective clarifies when direct GQSP or through qubitization, or Laurent expansion, or QSVT is most appropriate. We organize algorithmic design into an end-to-end pipeline: identifying the target matrix function, constructing an appropriate block-encoding, determining the relevant spectral domain, designing a polynomial or Laurent-polynomial approximation, synthesizing the phase factors, and translating the transformation into an executable quantum circuit. By applying this unified framework to example applications, we showcase a practical methodology for reasoning, designing, and implementing quantum algorithms based on polynomial transformations.

quant-pharXiv:2609.09977•Sep 10, 2026•0 citations

Improved Quantum Algorithms for Eigenvalues Finding and Gradient Descent

Nhat A. Nghiem, Tzu-Chieh Wei

Block encoding is a key ingredient in the recently developed quantum singular value transformation (QSVT) framework, which provides a unifying description for many quantum algorithms. Initially introduced to simplify and optimize resource utilization in various problems, such as searching, amplitude estimation, and Hamiltonian simulation, it is reasonable to expect that the capabilities of QSVT extend beyond these applications and offer untapped potential for designing new quantum algorithms. In this article, we affirm this perspective by leveraging block encoding to substantially enhance two previously proposed quantum algorithms: largest eigenvalue estimation and quantum gradient descent. Unlike previous works that rely on sophisticated approaches, our findings demonstrate that even just elementary operations within the unitary block encoding framework can eliminate major scaling factors present in their original counterparts. This results in significantly more efficient quantum algorithms capable of tackling target computational problems with remarkable efficiency. Furthermore, we illustrate how our proposed method can be extended to other contexts, including matrix inversion and multiple eigenvalue estimation.

arXiv:2312.14786•Dec 22, 2023•0 citations

Performance Evaluation of Quantum Kalman Filter for Target Tracking: A Quantum Information Perspective

B Manjukiran, Shantaramara Rai C, Gnane Swarnadh Satapathi +2 more

The Quantum Kalman Filter (QKF) emerges as an innovative approach to address the challenges of state estimation in quantum systems, adapting classical Kalman filtering to the complexities of quantum mechanics. This paper examines the theoretical framework, practical implementation hurdles, and potential applications of QKF in quantum information processing and sensing. By incorporating quantum measurement principles and stochastic dynamics, QKF offers a solution for optimal state estimation in noisy quantum environments. The study presents simulation results and comparative analyses with classical Kalman filtering for tracking single targets, underscoring the advantages and limitations of QKF in advancing quantum technology applications.

International Conference on Intelligent Systems and Pioneering Innovations in Robotics and Electric Mobility (INSPIRE)•Nov 20, 2025•0 citations

Review of the Applications of Kalman Filtering in Quantum Systems

Kezhao Ma, Jia Kong, Yihan Wang +1 more

State variable and parameter estimations are important for signal sensing and feedback control in both traditional engineering systems and quantum systems. The Kalman filter, which is one of the most popular signal recovery techniques in classical systems for decades, has now been connected to the stochastic master equations of linear quantum mechanical systems. Various studies have invested effort on mapping the state evolution of a quantum system into a set of classical filtering equations. However, establishing proper evolution models with symmetry to classical filter equation for quantum systems is not easy. Here, we review works that have successfully built a Kalman filter model for quantum systems and provide an improved method for optimal estimations. We also discuss a practical scenario involving magnetic field estimations in quantum systems, where non-linear Kalman filters could be considered an estimation solution.

Symmetry•Nov 22, 2022•13 citations

Sign Embedding Quantum Algorithms for Matrix Equations and Matrix Functions

Yanqiao Wang, Jin-Peng Liu

We develop operator-output quantum algorithms for matrix equations and matrix functions using matrix-sign embeddings. For each problem, an augmented matrix $M$ is chosen so that the target operator is a block of $\text{sign}(M)$ or is recovered from blocks of $(I-\text{sign}(M))/2$. We approximate the half-plane sign by a logarithmic-sinc formula and implement the shifted inverse families by scaled multiplexing with node-dependent rebalancing. For ordinary Sylvester equations, this yields a block-encoding of the solution with query complexity linear in the relevant conditioning parameters and logarithmic in the inverse error tolerance, under either a field-of-values (FoV) gap or a strip-resolvent bound. The same method extends to generalized Sylvester and Lyapunov equations, principal square and inverse square roots, matrix geometric means, and continuous-time algebraic Riccati equations (CARE), with explicit query-complexity and block-encoding-normalization bounds that cover non-normal and non-diagonalizable cases.

quant-pharXiv:2604.25333•Apr 29, 2026•0 citations
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.
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.
Modern quantum algorithms are increasingly formulated as coherent procedures for implementing polynomial transformations of operators and singular values. This perspective provides a powerful and unifying language for quantum algorithm design, connecting a wide range of distinct problems through five closely related key tools: block-encoding, qubitization, QSP, QSVT and GQSP. Block-encoding embeds non-unitary matrices into larger unitaries; qubitization converts block-encodings into structured operators; QSP, QSVT and GQSP enable polynomial transformations with near-optimal query complexity. Together, these techniques form a general toolkit for transforming matrix functions into implementable quantum circuits. This paper develops these techniques from first principles as a unified framework for constructing quantum algorithms. We apply this framework to representative applications to highlight design principles and demonstrate how distinct algorithms can be constructed from a unified sequence of operator transformations. A central contribution is a systematic decision workflow for selecting the appropriate approach according to the operator structure and the desired transformation polynomial. This perspective clarifies when direct GQSP or through qubitization, or Laurent expansion, or QSVT is most appropriate. We organize algorithmic design into an end-to-end pipeline: identifying the target matrix function, constructing an appropriate block-encoding, determining the relevant spectral domain, designing a polynomial or Laurent-polynomial approximation, synthesizing the phase factors, and translating the transformation into an executable quantum circuit. By applying this unified framework to example applications, we showcase a practical methodology for reasoning, designing, and implementing quantum algorithms based on polynomial transformations.
Block encoding is a key ingredient in the recently developed quantum singular value transformation (QSVT) framework, which provides a unifying description for many quantum algorithms. Initially introduced to simplify and optimize resource utilization in various problems, such as searching, amplitude estimation, and Hamiltonian simulation, it is reasonable to expect that the capabilities of QSVT extend beyond these applications and offer untapped potential for designing new quantum algorithms. In this article, we affirm this perspective by leveraging block encoding to substantially enhance two previously proposed quantum algorithms: largest eigenvalue estimation and quantum gradient descent. Unlike previous works that rely on sophisticated approaches, our findings demonstrate that even just elementary operations within the unitary block encoding framework can eliminate major scaling factors present in their original counterparts. This results in significantly more efficient quantum algorithms capable of tackling target computational problems with remarkable efficiency. Furthermore, we illustrate how our proposed method can be extended to other contexts, including matrix inversion and multiple eigenvalue estimation.
The Quantum Kalman Filter (QKF) emerges as an innovative approach to address the challenges of state estimation in quantum systems, adapting classical Kalman filtering to the complexities of quantum mechanics. This paper examines the theoretical framework, practical implementation hurdles, and potential applications of QKF in quantum information processing and sensing. By incorporating quantum measurement principles and stochastic dynamics, QKF offers a solution for optimal state estimation in noisy quantum environments. The study presents simulation results and comparative analyses with classical Kalman filtering for tracking single targets, underscoring the advantages and limitations of QKF in advancing quantum technology applications.
State variable and parameter estimations are important for signal sensing and feedback control in both traditional engineering systems and quantum systems. The Kalman filter, which is one of the most popular signal recovery techniques in classical systems for decades, has now been connected to the stochastic master equations of linear quantum mechanical systems. Various studies have invested effort on mapping the state evolution of a quantum system into a set of classical filtering equations. However, establishing proper evolution models with symmetry to classical filter equation for quantum systems is not easy. Here, we review works that have successfully built a Kalman filter model for quantum systems and provide an improved method for optimal estimations. We also discuss a practical scenario involving magnetic field estimations in quantum systems, where non-linear Kalman filters could be considered an estimation solution.
We develop operator-output quantum algorithms for matrix equations and matrix functions using matrix-sign embeddings. For each problem, an augmented matrix MMM is chosen so that the target operator is a block of sign(M)\text{sign}(M)sign(M) or is recovered from blocks of (I−sign(M))/2(I-\text{sign}(M))/2(I−sign(M))/2. We approximate the half-plane sign by a logarithmic-sinc formula and implement the shifted inverse families by scaled multiplexing with node-dependent rebalancing. For ordinary Sylvester equations, this yields a block-encoding of the solution with query complexity linear in the relevant conditioning parameters and logarithmic in the inverse error tolerance, under either a field-of-values (FoV) gap or a strip-resolvent bound. The same method extends to generalized Sylvester and Lyapunov equations, principal square and inverse square roots, matrix geometric means, and continuous-time algebraic Riccati equations (CARE), with explicit query-complexity and block-encoding-normalization bounds that cover non-normal and non-diagonalizable cases.