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

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, Tai‐Ping Sun, Huanyu Liu, Ye Li, Yu-Chun Wu, Guo‐Ping Guo

Published Mar 13, 2023• 2 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2303.06890

Related papers

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

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

Efficient Simulation of Szegedy Quantum Walk Formulations and Algorithms

Sergio A. Ortega, Daniel K. Park

Quantum walks provide a versatile framework for quantum algorithms across a wide range of applications. We develop efficient classical simulation methods for Szegedy quantum walks that avoid explicit construction of the full unitary evolution operator. Unlike previous approaches restricted to a particular walk formulation, our framework is built from fundamental update and reflection operators, enabling the simulation of a broader class of Szegedy walk formulations. We further extend these methods to phase-estimation-based algorithms coupled to the walk, including implementations suitable for large sparse graphs. The resulting methods achieve optimal $O(N^2)$ complexity for dense graphs with $N$ nodes. For sparse graphs, the computational cost scales linearly with the number of edges, which is $O(N)$ in many cases. We implement the framework in the Python package SQWLib and illustrate its capabilities through simulations of representative algorithms, including quantum simulated annealing and quantum search on graphs. These results provide a practical tool for studying Szegedy-walk-based algorithms numerically beyond purely analytical treatments.

quant-pharXiv:2606.14226•Physical Review A•Jun 15, 2026•1 citation

SparQSim: An Efficient Quantum Algorithm Simulator Leveraging State Sparsity

Tai‐Ping Sun, Yunjie Wang, Zhaoyun Chen +6 more

Abstract Quantum computing promises advantages for problems in physics, chemistry, and optimization, yet current noisy and small-scale devices limit the implementation of large quantum algorithms. Classical simulation therefore remains essential for algorithm design, verification, and performance benchmarking. However, existing Schrödinger- and Feynman-based simulators suffer from exponential scaling or limited oracle integration. Here we present SparQSim, a C++-based, Feynmaninspired simulator that exploits state sparsity to reduce memory consumption and supports registerlevel operations with integrated quantum random access memory (QRAM). Benchmarks from QASMBench and MQTBench show that for circuits with substantial state space sparsity, which represent the core application scenario of SparQSim, the method surpasses Schrödinger style simulators in both runtime and memory efficiency. Moreover, full-process simulations of quantum linear-system solvers yield results consistent with theoretical predictions. SparQSim provides a flexible and scalable platform for efficient simulation and optimization of quantum algorithms.

arXiv:2503.15118•Chinese Physics B•Feb 10, 2026•3 citations

Leveraging State Sparsity for More Efficient Quantum Simulations

Samuel Jaques, Thomas Häner

High-performance techniques to simulate quantum programs on classical hardware rely on exponentially large vectors to represent quantum states. When simulating quantum algorithms, the quantum states that occur are often sparse due to special structure in the algorithm or even in the underlying problem. We thus introduce a new simulation method that exploits this sparsity to reduce memory usage and simulation runtime. Moreover, our prototype implementation includes optimizations such as gate (re)scheduling, which amortizes data structure accesses and reduces memory usage. To benchmark our implementation, we run quantum algorithms for factoring, for computing integer and elliptic curve discrete logarithms, and for chemistry. Our simulator successfully runs a factoring instance of a 20-bit number using 102 qubits, and elliptic curve discrete logarithm over a 10-bit curve with 110 qubits. While previous work needed a supercomputer to simulate such instances of factoring, our approach succeeds in less than four minutes using a single core and less than 100 MB of memory. To the best of our knowledge, we are the first to fully simulate a quantum algorithm to compute elliptic curve discrete logarithms.

arXiv:2105.01533•ACM Transactions on Quantum Computing•Feb 24, 2022•27 citations
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 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.
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.
Quantum walks provide a versatile framework for quantum algorithms across a wide range of applications. We develop efficient classical simulation methods for Szegedy quantum walks that avoid explicit construction of the full unitary evolution operator. Unlike previous approaches restricted to a particular walk formulation, our framework is built from fundamental update and reflection operators, enabling the simulation of a broader class of Szegedy walk formulations. We further extend these methods to phase-estimation-based algorithms coupled to the walk, including implementations suitable for large sparse graphs. The resulting methods achieve optimal O(N2)O(N^2)O(N2) complexity for dense graphs with NNN nodes. For sparse graphs, the computational cost scales linearly with the number of edges, which is O(N)O(N)O(N) in many cases. We implement the framework in the Python package SQWLib and illustrate its capabilities through simulations of representative algorithms, including quantum simulated annealing and quantum search on graphs. These results provide a practical tool for studying Szegedy-walk-based algorithms numerically beyond purely analytical treatments.
Abstract Quantum computing promises advantages for problems in physics, chemistry, and optimization, yet current noisy and small-scale devices limit the implementation of large quantum algorithms. Classical simulation therefore remains essential for algorithm design, verification, and performance benchmarking. However, existing Schrödinger- and Feynman-based simulators suffer from exponential scaling or limited oracle integration. Here we present SparQSim, a C++-based, Feynmaninspired simulator that exploits state sparsity to reduce memory consumption and supports registerlevel operations with integrated quantum random access memory (QRAM). Benchmarks from QASMBench and MQTBench show that for circuits with substantial state space sparsity, which represent the core application scenario of SparQSim, the method surpasses Schrödinger style simulators in both runtime and memory efficiency. Moreover, full-process simulations of quantum linear-system solvers yield results consistent with theoretical predictions. SparQSim provides a flexible and scalable platform for efficient simulation and optimization of quantum algorithms.
High-performance techniques to simulate quantum programs on classical hardware rely on exponentially large vectors to represent quantum states. When simulating quantum algorithms, the quantum states that occur are often sparse due to special structure in the algorithm or even in the underlying problem. We thus introduce a new simulation method that exploits this sparsity to reduce memory usage and simulation runtime. Moreover, our prototype implementation includes optimizations such as gate (re)scheduling, which amortizes data structure accesses and reduces memory usage. To benchmark our implementation, we run quantum algorithms for factoring, for computing integer and elliptic curve discrete logarithms, and for chemistry. Our simulator successfully runs a factoring instance of a 20-bit number using 102 qubits, and elliptic curve discrete logarithm over a 10-bit curve with 110 qubits. While previous work needed a supercomputer to simulate such instances of factoring, our approach succeeds in less than four minutes using a single core and less than 100 MB of memory. To the best of our knowledge, we are the first to fully simulate a quantum algorithm to compute elliptic curve discrete logarithms.