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

Effect of matrix sparsity and quantum noise on quantum random walk linear solvers

Wu, Benjamin, Hrushikesh Pramod Patil, Predrag Krstić

Published May 27, 2022• 0 citations
arXivHTMLPDF

Abstract

We study the effects of quantum noise in hybrid quantum-classical solver for sparse systems of linear equations using quantum random walks, applied to stoquastic Hamiltonian matrices. In an ideal noiseless quantum computer, sparse matrices achieve solution vectors with lower relative error than dense matrices. However, we find quantum noise reverses this effect, with overall error increasing as sparsity increases. We identify invalid quantum random walks as the cause of this increased error and propose a revised linear solver algorithm which improves accuracy by mitigating these invalid walks.

DOI
10.48550/arxiv.2205.14180

Related papers

Preconditioning for a Variational Quantum Linear Solver

Aruto Hosaka, Koichi Yanagisawa, Shota Koshikawa +3 more

We apply preconditioning, which is widely used in classical solvers for linear systems $A\textbf{x}=\textbf{b}$, to the variational quantum linear solver. By utilizing incomplete LU factorization as a preconditioner for linear equations formed by $128\times128$ random sparse matrices, we numerically demonstrate a notable reduction in the required ansatz depth, demonstrating that preconditioning is useful for quantum algorithms. This reduction in circuit depth is crucial to improving the efficiency and accuracy of Noisy Intermediate-Scale Quantum (NISQ) algorithms. Our findings suggest that combining classical computing techniques, such as preconditioning, with quantum algorithms can significantly enhance the performance of NISQ algorithms.

arXiv:2312.15657•Dec 25, 2023•14 citations

Scalable Program Implementation and Simulation of the Large-Scale Quantum Algorithm: $1024\times 1024$ Quantum Linear Solver and Beyond

Zhaoyun Chen, Cheng Xue, Xi‐Ning Zhuang +5 more

Program implementation and simulation are essential for research in the field of quantum algorithms. However, complex and large-scale quantum algorithms can pose challenges for existing quantum programming languages and simulators. Here, we present a scalable program implementation of the quantum walk on a sparse matrix and the quantum linear solver based on the quantum walk. Our implementation is based on a practical scenario in which the sparse matrix is stored in the compressed-sparse-column format in quantum random access memory. All necessary modules are implemented unitarily and are ensured to be decomposed at the quantum gate level, including implementing a quantum binary search and a modification of the original algorithm. The program is validated using a highly efficient quantum circuit simulator which is based on the register level and sparse state representation. With only a single core, we simulate the quantum walk on a 16384-dimensional matrix with 582 qubits in 1.1 minutes per step, as well as a quantum linear solver up to 1024 dimensions and 212245 steps in 70 hours. Our work narrows the gap between the simulation of a quantum algorithm and its classical counterparts, where the asymptotic complexity of our quantum linear solver simulation approximates a classical linear solver. These program implementation and simulation techniques have the potential to expand the boundary of numerical research for large-scale quantum algorithms, with implications for the development of error-correction-era quantum computing solutions.

arXiv:2303.06890•Mar 13, 2023•2 citations

Hybrid classical-quantum linear solver using Noisy Intermediate-Scale Quantum machines

Chih-Chieh Chen, Shiue-Yuan Shiau, Ming-Feng Wu +1 more

We propose a realistic hybrid classical-quantum linear solver to solve systems of linear equations of a specific type, and demonstrate its feasibility with Qiskit on IBM Q systems. This algorithm makes use of quantum random walk that runs in [Formula: see text](N log(N)) time on a quantum circuit made of [Formula: see text](log(N)) qubits. The input and output are classical data, and so can be easily accessed. It is robust against noise, and ready for implementation in applications such as machine learning.

arXiv:1903.10949•Scientific Reports•Nov 7, 2019•42 citations

A Quantum Computer Amenable Sparse Matrix Equation Solver

Christopher D. Phillips, 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 way 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 currently exists no efficient, general quantum procedure. 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 $\mathcal{O}\left(N_{nz}\log\left(N\right)\right)$ complexity, where $N$ is the number of unknowns, and $N_{nz}$ is the total number of nonzero elements in the system matrix. This efficiency is independent of the matrix structure, and hence the quantum procedure can outperform classical methods for many common system types. We show this using the example of sparse approximate inverse (SPAI) preconditioning, which involves the application of matrix inverses for matrices with $N_{nz}=\mathcal{O}\left(N\right)$.

arXiv:2112.02600•Dec 5, 2021•4 citations

Randomized Adiabatic Quantum Linear Solver Algorithm with Optimal Complexity Scaling and Detailed Running Costs

David Jennings, Matteo Lostaglio, Sam Pallister +2 more

Solving linear systems of equations is a fundamental problem with a wide variety of applications across many fields of science, and there is increasing effort to develop quantum linear solver algorithms. Subaşı . [Phys. Rev. Lett. 122, 060504 (2019)] proposed a randomized algorithm inspired by adiabatic quantum computing, based on a sequence of random Hamiltonian simulation steps, with suboptimal scaling in the condition number κ of the linear system and the target error ϵ . Here we go beyond these results in several ways. Firstly, using filtering [Lin and Tong, Quantum 4, 361 (2020)] and Poissonization techniques [Cunningham and Roland, ArXiv:2406.03972 (2024)], the algorithm complexity is improved to the optimal scaling O ( κ log  ( 1 / ϵ ) ) —an exponential improvement in ϵ , and a shaving of a log  κ scaling factor in κ . Secondly, the algorithm is further modified to achieve constant factor improvements, which are vital as we progress towards hardware implementations on fault-tolerant devices. We introduce a cheaper randomized walk operator method replacing Hamiltonian simulation—which also removes the need for potentially challenging classical precomputations; randomized routines are sampled over optimized random variables; circuit constructions are improved. We obtain a closed formula rigorously upper bounding the expected number of times one needs to apply a block-encoding of the linear system matrix to output a quantum state encoding the solution to the linear system. The upper bound is 837 κ at ϵ = 10 − 10 for Hermitian matrices.

arXiv:2305.11352•PRX Quantum•Oct 7, 2025•52 citations

A quantum algorithm for simulating non-sparse Hamiltonians

Chunhao Wang, Leonard Wossnig

We present a quantum algorithm for simulating the dynamics of Hamiltonians that are not necessarily sparse. Our algorithm is based on the input model where the entries of the Hamiltonian are stored in a data structure in a quantum random access memory (qRAM) which allows for the efficient preparation of states that encode the rows of the Hamiltonian. We use a linear combination of quantum walks to achieve poly-logarithmic dependence on precision. The time complexity of our algorithm, measured in terms of the circuit depth, is O(t\sqrt{N}\norm{H}\,\polylog(N, t\norm{H}, 1/\epsilon)), where t is the evolution time, $N$ is the dimension of the system, and $\epsilon$ is the error in the final state, which we call precision. Our algorithm can be directly applied as a subroutine for unitary implementation and quantum linear systems solvers, achieving \widetilde{O}(\sqrt{N}) dependence for both applications.

arXiv:1803.08273•Quantum Information and Computation•Jun 1, 2020•29 citations
We study the effects of quantum noise in hybrid quantum-classical solver for sparse systems of linear equations using quantum random walks, applied to stoquastic Hamiltonian matrices. In an ideal noiseless quantum computer, sparse matrices achieve solution vectors with lower relative error than dense matrices. However, we find quantum noise reverses this effect, with overall error increasing as sparsity increases. We identify invalid quantum random walks as the cause of this increased error and propose a revised linear solver algorithm which improves accuracy by mitigating these invalid walks.
We apply preconditioning, which is widely used in classical solvers for linear systems Ax=bA\textbf{x}=\textbf{b}Ax=b, to the variational quantum linear solver. By utilizing incomplete LU factorization as a preconditioner for linear equations formed by 128×128128\times128128×128 random sparse matrices, we numerically demonstrate a notable reduction in the required ansatz depth, demonstrating that preconditioning is useful for quantum algorithms. This reduction in circuit depth is crucial to improving the efficiency and accuracy of Noisy Intermediate-Scale Quantum (NISQ) algorithms. Our findings suggest that combining classical computing techniques, such as preconditioning, with quantum algorithms can significantly enhance the performance of NISQ algorithms.
Scalable Program Implementation and Simulation of the Large-Scale Quantum Algorithm: 1024×10241024\times 10241024×1024 Quantum Linear Solver and Beyond
Program implementation and simulation are essential for research in the field of quantum algorithms. However, complex and large-scale quantum algorithms can pose challenges for existing quantum programming languages and simulators. Here, we present a scalable program implementation of the quantum walk on a sparse matrix and the quantum linear solver based on the quantum walk. Our implementation is based on a practical scenario in which the sparse matrix is stored in the compressed-sparse-column format in quantum random access memory. All necessary modules are implemented unitarily and are ensured to be decomposed at the quantum gate level, including implementing a quantum binary search and a modification of the original algorithm. The program is validated using a highly efficient quantum circuit simulator which is based on the register level and sparse state representation. With only a single core, we simulate the quantum walk on a 16384-dimensional matrix with 582 qubits in 1.1 minutes per step, as well as a quantum linear solver up to 1024 dimensions and 212245 steps in 70 hours. Our work narrows the gap between the simulation of a quantum algorithm and its classical counterparts, where the asymptotic complexity of our quantum linear solver simulation approximates a classical linear solver. These program implementation and simulation techniques have the potential to expand the boundary of numerical research for large-scale quantum algorithms, with implications for the development of error-correction-era quantum computing solutions.
We propose a realistic hybrid classical-quantum linear solver to solve systems of linear equations of a specific type, and demonstrate its feasibility with Qiskit on IBM Q systems. This algorithm makes use of quantum random walk that runs in [Formula: see text](N log(N)) time on a quantum circuit made of [Formula: see text](log(N)) qubits. The input and output are classical data, and so can be easily accessed. It is robust against noise, and ready for implementation in applications such as machine learning.
Quantum computation offers a promising alternative to classical computing methods in many areas of numerical science, with algorithms that make use of the unique way 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 currently exists no efficient, general quantum procedure. 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(Nnzlog⁡(N))\mathcal{O}\left(N_{nz}\log\left(N\right)\right)O(Nnz​log(N)) complexity, where NNN is the number of unknowns, and NnzN_{nz}Nnz​ is the total number of nonzero elements in the system matrix. This efficiency is independent of the matrix structure, and hence the quantum procedure can outperform classical methods for many common system types. We show this using the example of sparse approximate inverse (SPAI) preconditioning, which involves the application of matrix inverses for matrices with Nnz=O(N)N_{nz}=\mathcal{O}\left(N\right)Nnz​=O(N).
Solving linear systems of equations is a fundamental problem with a wide variety of applications across many fields of science, and there is increasing effort to develop quantum linear solver algorithms. Subaşı . [Phys. Rev. Lett. 122, 060504 (2019)] proposed a randomized algorithm inspired by adiabatic quantum computing, based on a sequence of random Hamiltonian simulation steps, with suboptimal scaling in the condition number κ of the linear system and the target error ϵ . Here we go beyond these results in several ways. Firstly, using filtering [Lin and Tong, Quantum 4, 361 (2020)] and Poissonization techniques [Cunningham and Roland, ArXiv:2406.03972 (2024)], the algorithm complexity is improved to the optimal scaling O ( κ log  ( 1 / ϵ ) ) —an exponential improvement in ϵ , and a shaving of a log  κ scaling factor in κ . Secondly, the algorithm is further modified to achieve constant factor improvements, which are vital as we progress towards hardware implementations on fault-tolerant devices. We introduce a cheaper randomized walk operator method replacing Hamiltonian simulation—which also removes the need for potentially challenging classical precomputations; randomized routines are sampled over optimized random variables; circuit constructions are improved. We obtain a closed formula rigorously upper bounding the expected number of times one needs to apply a block-encoding of the linear system matrix to output a quantum state encoding the solution to the linear system. The upper bound is 837 κ at ϵ = 10 − 10 for Hermitian matrices.
We present a quantum algorithm for simulating the dynamics of Hamiltonians that are not necessarily sparse. Our algorithm is based on the input model where the entries of the Hamiltonian are stored in a data structure in a quantum random access memory (qRAM) which allows for the efficient preparation of states that encode the rows of the Hamiltonian. We use a linear combination of quantum walks to achieve poly-logarithmic dependence on precision. The time complexity of our algorithm, measured in terms of the circuit depth, is O(t\sqrt{N}\norm{H}\,\polylog(N, t\norm{H}, 1/\epsilon)), where t is the evolution time, NNN is the dimension of the system, and ϵ\epsilonϵ is the error in the final state, which we call precision. Our algorithm can be directly applied as a subroutine for unitary implementation and quantum linear systems solvers, achieving \widetilde{O}(\sqrt{N}) dependence for both applications.