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

Matrix Inversion by Quantum Walk

Alastair Kay, Christino Tamon

Published Aug 8, 2025• 1 citation
arXivHTMLPDF

Abstract

The HHL algorithm for matrix inversion is a landmark algorithm in quantum computation. Its ability to produce a state $|x\rangle$ that is the solution of $Ax=b$, given the input state $|b\rangle$, is envisaged to have diverse applications. In this paper, we substantially simplify the algorithm, originally formed of a complex sequence of phase estimations, amplitude amplifications and Hamiltonian simulations, by replacing the phase estimations with a continuous time quantum walk. The key technique is the use of weak couplings to access the matrix inversion embedded in perturbation theory.

DOI
10.48550/arxiv.2508.06611

Related papers

Towards Solution of Integral Equations in Electromagnetics on Quantum Computers

Christopher Phillips, Vladimir Okhmatovski

We present some of the fundamental methods in quantum computing for matrix equations, framed in terms of their applicability to solution of integral equations in electromagnetics. In particular, we describe the HHL algorithm for matrix inversion and matrix vector products, as well as techniques of Hamiltonian simulation for general matrices.

Digest - IEEE Antennas and Propagation Society. International Symposium•Dec 4, 2021•0 citations

Quantum linear systems algorithms: a primer

Danial Dervovic, Mark Herbster, Peter Mountney +3 more

The Harrow-Hassidim-Lloyd (HHL) quantum algorithm for sampling from the solution of a linear system provides an exponential speed-up over its classical counterpart. The problem of solving a system of linear equations has a wide scope of applications, and thus HHL constitutes an important algorithmic primitive. In these notes, we present the HHL algorithm and its improved versions in detail, including explanations of the constituent sub- routines. More specifically, we discuss various quantum subroutines such as quantum phase estimation and amplitude amplification, as well as the important question of loading data into a quantum computer, via quantum RAM. The improvements to the original algorithm exploit variable-time amplitude amplification as well as a method for implementing linear combinations of unitary operations (LCUs) based on a decomposition of the operators using Fourier and Chebyshev series. Finally, we discuss a linear solver based on the quantum singular value estimation (QSVE) subroutine.

arXiv:1802.08227•Feb 22, 2018•140 citations

Solution of 2x2 Matrix Equation on NISQ Computer with QW-HHL Algorithm

Christopher D. Phillips, Helia Akbari, Vladimir Okhmatovski

Case study of solving a$2 \times 2$matrix equation on a noisy intermediate-scale quantum (NISQ) computer is presented. The structure of the matrix equation is customized for the recently proposed quantum-walk Harrow/Hassidim/Lloyd (QW-HHL) algorithm in such a way that it minimizes the depth of the pertinent quantum circuit. Simplified operators in the QW-HHL algorithm are described for the particular$2 \times 2$matrix equation to facilitate understanding of the method. Without uncomputation stage of the HHL algorithm, the 7-qubit circuit consists of 63 logical steps, and features only 1,600 basic gates in the transpiled circuit. Such shallow depth of the circuit allows us to preserve quantum state containing the solution with fidelity of about 70% in the execution on IBM Fez quantum computer.

Digest - IEEE Antennas and Propagation Society. International Symposium•Jul 1, 2026•0 citations

QW-HHL: A Quantum Computer Amenable General Matrix Equation Solver

Christopher D. Phillips, Helia Akbari, Vladimir Okhmatovski

Quantum computation offers a promising alternative to classical computing methods in many areas of numerical science, with algorithms that make use of the unique ways in which quantum computers store and manipulate data often achieving dramatic improvements in performance over their classical counterparts. The potential efficiency of quantum computers is particularly important for numerical simulations, where the capabilities of classical computing systems are often insufficient for the analysis of real-world problems. In this work, we study problems involving the solution of matrix equations, for which there is limited research on efficient, general, and fully implemented quantum procedures. We develop a generalization of the Harrow/Hassidim/Lloyd algorithm by providing an alternative unitary for eigenphase estimation. This unitary, which we have adopted from research in the area of quantum walks, has the advantage of being well defined for any arbitrary matrix equation, thereby allowing the solution procedure to be directly implemented on quantum hardware for any well-conditioned system. The procedure is most useful for sparse matrix equations, as it allows for the inverse of a matrix to be applied with O(sN log(N)) complexity, where N is the number of unknowns, and s is an upper bound on the number of nonzero elements in any row of the system matrix. This efficiency is competitive with the most sophisticated available classical solvers, and is independent of the structure of the input matrix. Hence, this procedure represents an important step towards the achievement of quantum advantage over classical algorithms for practical problems in numerical science.

IEEE journal on multiscale and multiphysics computational techniques•Jan 1, 2026•1 citation

HHL Algorithm for Tensor-Decomposable Matrices

Cezary Pilaszewicz, Marian Margraf

We use the HHL algorithm to retrieve a quantum state holding the algebraic normal form (ANF) of a Boolean function. Unlike the standard HHL applications, we do not describe the cipher as an exponentially big system of equations. Rather, we perform a set of small matrix inversions which correspond to the Boolean Möbius transform. This creates a superposition holding information about the ANF in the form |Af⟩=1C∑I=02n−1cI|I⟩, where cI is the coefficient of the ANF and C is a scaling factor. The procedure has a time complexity of O~(n) for a Boolean function with n-bit input. We also propose two approaches by which some information about the ANF can be extracted from such a state. Next, we use a similar approach, the Dual Boolean Möbius transform, to compute the preimage under the algebraic transition matrix. We show that such a matrix is well-suited for the HHL algorithm when the attacker gets oracle access in the Q2 setting to the Boolean function.

Quantum Reports•Aug 19, 2025•1 citation

Tripartite entanglement and matrix inversion quantum algorithm

Mi-Ra Hwang, MuSeong Kim, Eylee Jung +2 more

Abstract The role of entanglement is discussed in the Harrow-Hassidim-Lloyd (HHL) algorithm. We compute all tripartite entanglement at every steps of the HHL algorithm. The tripartite entanglement is generated at the first quantum phase estimation (QPE) step. However, it turns out that amount of the generated entanglement is not maximal except very rare cases. In the second rotation step some tripartite entanglement is used. Thus, the net tripartite entanglement is diminished. At the final inverse-QPE step the matrix inversion task is completed at the price of complete annihilation of the entanglement. An implication of this result is briefly discussed.

arXiv:2203.10780•Nov 23, 2022•2 citations
The HHL algorithm for matrix inversion is a landmark algorithm in quantum computation. Its ability to produce a state ∣x⟩|x\rangle∣x⟩ that is the solution of Ax=bAx=bAx=b, given the input state ∣b⟩|b\rangle∣b⟩, is envisaged to have diverse applications. In this paper, we substantially simplify the algorithm, originally formed of a complex sequence of phase estimations, amplitude amplifications and Hamiltonian simulations, by replacing the phase estimations with a continuous time quantum walk. The key technique is the use of weak couplings to access the matrix inversion embedded in perturbation theory.
The Harrow-Hassidim-Lloyd (HHL) quantum algorithm for sampling from the solution of a linear system provides an exponential speed-up over its classical counterpart. The problem of solving a system of linear equations has a wide scope of applications, and thus HHL constitutes an important algorithmic primitive. In these notes, we present the HHL algorithm and its improved versions in detail, including explanations of the constituent sub- routines. More specifically, we discuss various quantum subroutines such as quantum phase estimation and amplitude amplification, as well as the important question of loading data into a quantum computer, via quantum RAM. The improvements to the original algorithm exploit variable-time amplitude amplification as well as a method for implementing linear combinations of unitary operations (LCUs) based on a decomposition of the operators using Fourier and Chebyshev series. Finally, we discuss a linear solver based on the quantum singular value estimation (QSVE) subroutine.
Case study of solving a2×22 \times 22×2matrix equation on a noisy intermediate-scale quantum (NISQ) computer is presented. The structure of the matrix equation is customized for the recently proposed quantum-walk Harrow/Hassidim/Lloyd (QW-HHL) algorithm in such a way that it minimizes the depth of the pertinent quantum circuit. Simplified operators in the QW-HHL algorithm are described for the particular2×22 \times 22×2matrix equation to facilitate understanding of the method. Without uncomputation stage of the HHL algorithm, the 7-qubit circuit consists of 63 logical steps, and features only 1,600 basic gates in the transpiled circuit. Such shallow depth of the circuit allows us to preserve quantum state containing the solution with fidelity of about 70% in the execution on IBM Fez quantum computer.
Quantum computation offers a promising alternative to classical computing methods in many areas of numerical science, with algorithms that make use of the unique ways in which quantum computers store and manipulate data often achieving dramatic improvements in performance over their classical counterparts. The potential efficiency of quantum computers is particularly important for numerical simulations, where the capabilities of classical computing systems are often insufficient for the analysis of real-world problems. In this work, we study problems involving the solution of matrix equations, for which there is limited research on efficient, general, and fully implemented quantum procedures. We develop a generalization of the Harrow/Hassidim/Lloyd algorithm by providing an alternative unitary for eigenphase estimation. This unitary, which we have adopted from research in the area of quantum walks, has the advantage of being well defined for any arbitrary matrix equation, thereby allowing the solution procedure to be directly implemented on quantum hardware for any well-conditioned system. The procedure is most useful for sparse matrix equations, as it allows for the inverse of a matrix to be applied with O(sN log(N)) complexity, where N is the number of unknowns, and s is an upper bound on the number of nonzero elements in any row of the system matrix. This efficiency is competitive with the most sophisticated available classical solvers, and is independent of the structure of the input matrix. Hence, this procedure represents an important step towards the achievement of quantum advantage over classical algorithms for practical problems in numerical science.
We use the HHL algorithm to retrieve a quantum state holding the algebraic normal form (ANF) of a Boolean function. Unlike the standard HHL applications, we do not describe the cipher as an exponentially big system of equations. Rather, we perform a set of small matrix inversions which correspond to the Boolean Möbius transform. This creates a superposition holding information about the ANF in the form |Af⟩=1C∑I=02n−1cI|I⟩, where cI is the coefficient of the ANF and C is a scaling factor. The procedure has a time complexity of O~(n) for a Boolean function with n-bit input. We also propose two approaches by which some information about the ANF can be extracted from such a state. Next, we use a similar approach, the Dual Boolean Möbius transform, to compute the preimage under the algebraic transition matrix. We show that such a matrix is well-suited for the HHL algorithm when the attacker gets oracle access in the Q2 setting to the Boolean function.
Abstract The role of entanglement is discussed in the Harrow-Hassidim-Lloyd (HHL) algorithm. We compute all tripartite entanglement at every steps of the HHL algorithm. The tripartite entanglement is generated at the first quantum phase estimation (QPE) step. However, it turns out that amount of the generated entanglement is not maximal except very rare cases. In the second rotation step some tripartite entanglement is used. Thus, the net tripartite entanglement is diminished. At the final inverse-QPE step the matrix inversion task is completed at the price of complete annihilation of the entanglement. An implication of this result is briefly discussed.