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• 5 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 eigenvalue 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•Physical Review Applied•Apr 6, 2026•13 citations

New Quantum Algorithm For Solving Linear System of Equations

Nhat A. Nghiem

Linear equations play a pivotal role in many areas of science and engineering, making efficient solutions to linear systems highly desirable. The development of quantum algorithms for solving linear systems has been a significant breakthrough, with such algorithms rapidly becoming some of the most influential in quantum computing. Subsequent advances have focused on improving the efficiency of quantum linear solvers and extending their core techniques to address various challenges, such as least-squares data fitting. In this article, we introduce a new quantum algorithm for solving linear systems based on the gradient descent method. Inspired by the vector/density state formalism, we represent a point, or vector, as a density state-like entity, enabling us to leverage recent advancements in quantum algorithmic frameworks, such as block encoding, to directly manipulate operators and carry out the gradient descent method in a quantum setting. The operator corresponding to the intermediate solution is updated iteratively, with a provable guarantee of convergence. The quantum state representing the final solution to the linear system can then be extracted by further measurement. We provide a detailed complexity analysis and compare our approach with existing methods, demonstrating significant improvement in certain aspects.

arXiv:2502.13630•Feb 19, 2025•4 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

Preconditioned block encodings for quantum linear systems

Leigh B. Lapworth, Christoph Sünderhauf

Abstract Quantum linear system solvers like the quantum singular value transformation (QSVT) require a block encoding of the system matrix A within a unitary operator UA . Unfortunately, block encoding often results in significant subnormalisation and increase in the matrix’s effective condition number κ, affecting the efficiency of solvers. Matrix preconditioning is a well-established classical technique to reduce κ by multiplying A by a preconditioner P. Here, we study quantum preconditioning for block encodings. We consider four preconditioners and two encoding approaches: (a) separately encoding A and its preconditioner P, followed by quantum multiplication, and (b) classically multiplying A and P before encoding the product in U PA . Their impact on subnormalisation factors and condition number κ are analysed using practical matrices from computational fluid dynamics (CFD). Our results show that (a) quantum multiplication introduces excessive subnormalisation factors, negating improvements in κ. We study preamplified quantum multiplication to reduce subnormalisation. Conversely, we see that (b) encoding of the classical product can significantly improve the effective condition number using the sparse approximate inverse preconditioner with infill. Further, we introduce a new matrix filtering technique that reduces the circuit depth without adversely affecting the matrix solution. We apply these methods to reduce the number of QSVT phase factors by a factor of 25 for an example CFD matrix of size 1024 × 1024.

arXiv:2502.20908•Quantum Science and Technology•Oct 3, 2025•12 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.
Linear equations play a pivotal role in many areas of science and engineering, making efficient solutions to linear systems highly desirable. The development of quantum algorithms for solving linear systems has been a significant breakthrough, with such algorithms rapidly becoming some of the most influential in quantum computing. Subsequent advances have focused on improving the efficiency of quantum linear solvers and extending their core techniques to address various challenges, such as least-squares data fitting. In this article, we introduce a new quantum algorithm for solving linear systems based on the gradient descent method. Inspired by the vector/density state formalism, we represent a point, or vector, as a density state-like entity, enabling us to leverage recent advancements in quantum algorithmic frameworks, such as block encoding, to directly manipulate operators and carry out the gradient descent method in a quantum setting. The operator corresponding to the intermediate solution is updated iteratively, with a provable guarantee of convergence. The quantum state representing the final solution to the linear system can then be extracted by further measurement. We provide a detailed complexity analysis and compare our approach with existing methods, demonstrating significant improvement in certain aspects.
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.
Abstract Quantum linear system solvers like the quantum singular value transformation (QSVT) require a block encoding of the system matrix A within a unitary operator UA . Unfortunately, block encoding often results in significant subnormalisation and increase in the matrix’s effective condition number κ, affecting the efficiency of solvers. Matrix preconditioning is a well-established classical technique to reduce κ by multiplying A by a preconditioner P. Here, we study quantum preconditioning for block encodings. We consider four preconditioners and two encoding approaches: (a) separately encoding A and its preconditioner P, followed by quantum multiplication, and (b) classically multiplying A and P before encoding the product in U PA . Their impact on subnormalisation factors and condition number κ are analysed using practical matrices from computational fluid dynamics (CFD). Our results show that (a) quantum multiplication introduces excessive subnormalisation factors, negating improvements in κ. We study preamplified quantum multiplication to reduce subnormalisation. Conversely, we see that (b) encoding of the classical product can significantly improve the effective condition number using the sparse approximate inverse preconditioner with infill. Further, we introduce a new matrix filtering technique that reduces the circuit depth without adversely affecting the matrix solution. We apply these methods to reduce the number of QSVT phase factors by a factor of 25 for an example CFD matrix of size 1024 × 1024.