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.
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.
In the current era of Noisy Intermediate Scale Quantum (NISQ) computing, efficient digital simulation of quantum systems holds significant importance for quantum algorithm development, verification and validation. However, analysis of sparsity within these simulations remains largely unexplored. In this paper, we present a novel observation regarding the prevalent sparsity patterns inherent in quantum circuits. We introduce DiaQ, a new sparse matrix format tailored to exploit this quantum-specific sparsity, thereby enhancing simulation performance. Our contribution extends to the development of libdiaq, a numerical library implemented in C++ with OpenMP for multi-core acceleration and SIMD vectorization, featuring essential mathematical kernels for digital quantum simulations. Furthermore, we integrate DiaQ with SV-Sim, a state vector simulator, yielding substantial performance improvements across various quantum circuits (e.g., ~26.67% for GHZ-28 and ~32.72% for QFT-29 with multi-core parallelization and SIMD vectorization on Frontier). Evaluations conducted on benchmarks from SupermarQ and QASMBench demonstrate that DiaQ represents a significant step towards achieving highly efficient quantum simulations.
Simulating quantum circuits on classical hardware remains essential for developing and validating quantum algorithms, particularly in this era of noisy and limited quantum devices. Classical simulation is computationally demanding, due to the exponential growth of the Hilbert space with the number of qubits, because of quantum entanglement. Tensor networks offer a versatile tool for quantum circuit simulation, helping to reduce the associated computational cost. While tensor networks leverage entanglement to represent quantum states in compressed form, many quantum systems also exhibit additional symmetries, such as conserved particle number, that induce block sparsity in quantum states and quantum operators. We demonstrate through numerical experiments how block sparsity can be exploited to enhance the performance of the simulation of quantum circuits, in terms of execution time and memory usage.
Quantum Random Access Memory (QRAM) represents a crucial component in the realization of practical quantum computers, enabling fast and probabilistic data access for quantum algorithms. However, accurately simulating QRAM's operation presents a formidable challenge due to the inherent randomness and quantum mechanical nature of the system. This work investigates and proposes novel simulation techniques and optimization algorithms aimed at mitigating this computational complexity. We explore various approaches, including stochastic simulation methods, reduced-order modeling, and tailored optimization strategies, focusing on minimizing the number of quantum operations required for accurate QRAM simulation. The results demonstrate significant reductions in computational cost while maintaining a reasonable level of fidelity, paving the way for more efficient design and analysis of QRAM architectures. The core claim of this research is that the development of QRAM is fundamentally limited by the complexity of its simulation, and this work offers a direct path toward overcoming this bottleneck.
Classical simulation of quantum circuits is critical for the development of implementations of quantum algorithms: it does not require access to specialized hardware, facilitates debugging by allowing direct access to the quantum state, and is the only way to test on inputs that are too big for current NISQ computers. Many quantum algorithms rely on invariants that result in sparsity in the state vector. A sparse state vector simulator only computes with non-zero amplitudes. For important classes of algorithms, this results in an asymptotic improvement in simulation time. While promising prior work has investigated ways to exploit sparsity, it is still unclear what is the best way to scale sparse simulation to modern multi-core architectures. In this work, we address this challenge and present qblaze , a highly optimized sparse state vector simulator based on (i) a compact sorted array representation, and (ii) new, easily parallelizable and highly-scalable algorithms for all quantum operations. Our extensive experimental evaluation shows that qblaze is often orders-of-magnitude more efficient than prior sparse state vector simulators even on a single thread, and also that qblaze scales well to a large number of CPU cores. Overall, our work enables testing quantum algorithms on input sizes that were previously out of reach.
Scalable Program Implementation and Simulation of the Large-Scale Quantum Algorithm: 1024×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.