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• 0 citations
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•62 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

A Quantum-Walk-Unitary HHL Matrix Equation Solver and Its Challenges in the NISQ Era

Xinbo Li, Christopher Phillips, Ian Jeffrey +1 more

The Harrow/Hassidim/Lloyd algorithm is a celebrated quantum matrix equation solver. Its Hamiltonian simulation involves a quantum walk process. A newly developed Quantum Walk Unitary HHL (QWU-HHL) leverages the spectral relationship between the quantum walk operator and the system matrix, and uses the quantum walk operator as its unitary in the phase estimation directly, allowing Hamiltonian simulation in the classical HHL to be removed, hence improving its efficiency. Despite the potential of being exponentially faster than classical matrix equation solvers, HHL is not feasible in the noisy intermediate-scale quantum era because its quantum circuit is too deep to preserve an accurate solution. In this work, we investigate the error behavior of QWU-HHL on a 7-qubit quantum system. Instead of executing the entire circuit, the behaviors of its sub-circuits which each contain only an initialization and a single gate are recorded. The error caused by isolated initialization and operation are analyzed.

IEEE MTT-S International Microwave Symposium digest•Jun 11, 2023•1 citation
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.
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.
The Harrow/Hassidim/Lloyd algorithm is a celebrated quantum matrix equation solver. Its Hamiltonian simulation involves a quantum walk process. A newly developed Quantum Walk Unitary HHL (QWU-HHL) leverages the spectral relationship between the quantum walk operator and the system matrix, and uses the quantum walk operator as its unitary in the phase estimation directly, allowing Hamiltonian simulation in the classical HHL to be removed, hence improving its efficiency. Despite the potential of being exponentially faster than classical matrix equation solvers, HHL is not feasible in the noisy intermediate-scale quantum era because its quantum circuit is too deep to preserve an accurate solution. In this work, we investigate the error behavior of QWU-HHL on a 7-qubit quantum system. Instead of executing the entire circuit, the behaviors of its sub-circuits which each contain only an initialization and a single gate are recorded. The error caused by isolated initialization and operation are analyzed.