Noisy Quantum Simulation Using Tracking, Uncomputation and Sampling

TUSQ: Tracking, Uncomputation, and Sampling for Noisy Quantum Simulation Siddharth Dangwal∗, Tina Oberoi∗, Ajay Sailopal∗, Dhirpal Shah, Frederic T. Chong University of Chicago I. ABSTRACT Quantum computers have grown rapidly in size and qubit quality in recent years, enabling the execution of complex quantum circuits. However, for most researchers, access to compute time on quantum hardware is limited. This necessitates the need to build simulators that mimic the execution of quantum circuits on noisy quantum hardware accurately and scalably. In this work, we propose TUSQ - Tracking, Uncomputation, and Sampling for Noisy Quantum Simulation. TUSQ is a simulator that can perform noisy simulation of up to 30-qubit Adder circuits on a single Nvidia A100 GPU in less than 820 seconds. To represent the stochastic noisy channels accurately, we average the output of multiple quantum circuits with fixed noisy gates sampled from the channels. However, this leads to a substantial increase in circuit overhead, which slows down the simulation. To eliminate this overhead, TUSQ uses two modules: the Error Characterization Module (ECM), and the Tree-based Execution Module (TEM). The ECM tracks the number of unique circuit executions needed to accurately represent the noise. Here ECM reduces the initial n1circuit executions to n2by eliminating redundancies (n2< n1). This is followed by the TEM, which reuses computation across these n2circuits. We evaluate TUSQ for a total of 198 benchmarks and report an average speedup of 59.06×and 13.38×over Qiskit and CUDA-Q . For larger benchmarks (more than than 15 qubits), the average speedup is 64.16×and 24.55×over Qiskit and CUDA-Q respectively II. INTRODUCTION Quantum computing has the potential to offer speedups in tasks like factoring [11], unordered search [5], and physics and chemistry simulations [7], [10]. However, compute time on these devices is still scarce and expensive [1]. In order to advance quantum computing research, we need simulators that accurately mimic noisy quantum hardware. This presents a need for scalable noisy simulators whereas most current quantum simulators focus on noiseless simulation. In noiseless Quantum Circuit Simulation(QCS), we start with a complex vector representing the quantum state and multiply it by deterministic unitary matrices (representing quantum gates) to obtain a final vector. This vector is sampled multiple times to obtain an output distribution. This type of simulation is called State Vector Simulation (SVS). Note that *These authors contributed equally to this work. the matrix-vector multiplications needed to obtain the final vector need to be performed only once here. Noisy QCS, on the other hand, encounters stochastic noisy operations which may “manifest” as different gates during different runs. To accurately account for the effect of the stochastic noisy operation, we need to perform the entire sequence of matrix-vector multiplications every time we sample the output vector. Hence, if our output distribution consists of Ssamples, we need to perform Sdistinct SVSs resulting in a S-fold time overhead. A popular alternative to SVS is Density Matrix Simulation (DMS) which can account for the effect of stochastic noisy operations on a quantum state in one circuit execution. But DMS has a quadratically higher memory overhead (O(22n)as opposed to SVS O(2n)), which makes it an infeasible choice [4], [6], [9]. This work addresses both speed and circuit size limitations by proposing TUSQ: Tracking, Uncomputation, and Sampling for Noisy Quantum Simulation. Similar to CUDA-Q [3], [9] or Qiskit Statevector Simulator [2], TUSQ performs multiple SVSs to represent noisy simulation of one circuit, thereby achieving a quadratically smaller memory footprint than DMS. In order to reduce the resulting time overhead, we propose two modules - Error Characterization Module (ECM), and Treebased Execution Module (TEM). The basic principal behind these modules is to identify instances of redundant or relatively unimportant computation and eliminate them which results in fast noisy QCS. Since sampling state vector is less expensive than obtaining state vectors [9], we track all circuit instances where the final state vector would be the same. If there are Ksuch instances, we perform the state vector computation just once and sample it Ktimes instead of performing SVS Kseparate times. This is done using ECM. To carry out the tracking process, we use a lightweight intermediate representation of each circuit, which lets us predict whether its output state vector would be unique or not without actually computing it. Once we are sure that all state vectors would be distinct, the TEM identifies opportunities to eliminate redundant computation across circuits. For example, if two circuits are the same for the first half and differ in the second half, we do not need to perform matrix-vector multiplications from scratch for both. If we assume that all operations on these circuits are unitary, then these circuits are represented as U1Uc and U2Ucrespectively. Ucis the common first half, while U1and U2are the different second halves of the circuits. We can compute the “final state vector” for the first circuit 1 0 100 200 300 400 500 Iteration 0 2 4 6 Cost 10 Qubits 0 100 200 300 400 Iteration 15 Qubits TUSQ (no Pruning) TUSQ (with Pruning) Fig. 1. Convergence plots for minimum eigenvalue estimation of the 10 and 15 qubit Ising Hamiltonians, with and without pruning error. We see that plots in both cases show similar convergence, highlighting the negligible effect of pruning error on application performance. (say v1), apply U−1 1to uncompute back to the intermediate state vector and then apply U2on this intermediate state vector to get the “final state vector” for the second circuit (v2). This is similar to rollback-recovery performed routinely in classical computer architecture, especially in distributed systems [8]. When generalized for all gates across all circuits, we effectively perform a depth-first tree traversal. We can also prune the tree to eliminate unimportant computation while sampling from only the significantly weighted leaf nodes, further reducing execution overhead. An important assumption here is that all gates in our circuit (even noisy gates) are unitary. The net result of these optimizations is that we can simulate a 30 qubit Adder circuit on a single Nvidia A100 GPU in 819.87 seconds. The same benchmark on popular GPU simulators like CUDA-Q and Qiskit takes more than 10 hours. III. EVALUATION A. Deviation in Fidelity All the steps of the TUSQ pipeline are fidelity preserving except one TEM optimization, ”pruning”. Relative fidelity difference between the pruning, and no-pruning approaches (δpruning,no pruning) is found to be in range 1.66% to 7.15%. The practical effect of these small deviations on fidelity is minimal, if any. For example, while finding the minimal eigenvalue of 10 and 15 qubit Ising Hamiltonians with and without pruning errors, we see similar convergence plots as shown in Figure 1. Hence, we see that for most cases, the pruning error does not have a “practical effect” on our observable. B. Speedup Figure 2 shows the performance of TUSQ compared to Qiskit and CUDA-Q for 186 benchmarks. The height of each bar represents the value of the relative speedup. Some bars touch the roof of the plot and are marked with an ∞sign. These correspond to cases which could not be completed in 40 hours and timed out on Perlmutter. TUSQ outperforms Qiskit on all benchmarks, and CUDAQ on 181 out of 186 benchmarks. The benchmarks where TUSQ is worse than CUDA-Q are the 9 and 13 qubit Phase Code, and the 13 qubit QAOA with p=6,8 and 10. These 14 16 18 20 22 24 26 28 Number of Qubits 100 101 102 103 104 CUDA-Q, Adder Qiskit, Adder CUDA-Q, GHZ Qiskit, GHZ CUDA-Q, QFT Qiskit, QFT 5 9 13 17 21 25 Number of Qubits CUDA-Q, Bitcode Qiskit, Bitcode CUDA-Q, Phasecode Qiskit, Phasecode Relative Speedup ( ) of TUSQ over Qiskit / CUDA-Q Fig. 2. Relative Speedup Offered by TUSQ over Qiskit and CUDA-Q for Adder, GHZ, Bitcode and Phasecode (Subplot B). In the sub-plot, the numbers in black over the bars is the time taken by TUSQ (in seconds) to simulate the program. The height of a bar quantifies how much longer it took for CUDAQ/Qiskit to simulate the same program relative to TUSQ. The higher the bar, the greater TUSQ’s speedup. There are cases where the program timed out since the estimated simulation time is more than the Perlmutter limit. These are represented with a bar reaching the roof of the plot and marked with a rotated ∞sign. are small programs with fast simulation times where TUSQ’s preprocessing overheads on CPU end up being the bottleneck instead of the GPU compute time. In these cases, a naive GPU simulation with minimal pre-processing, as performed by CUDA-Q turns out to be a better strategy. Practically, the time taken by TUSQ to simulate these programs is also small. TUSQ takes 1.36, 4.49, 29.37, 44.20, and 77.14 seconds to simulate these circuits respectively. We observe that in general, TUSQ’s relative speedup increases with number of qubits. This is expected since simulation time scales exponentially in the number of qubits. Hence, any improvement in simulation speed would also scale exponentially. Compared to Qiskit, TUSQ’s average relative speedup is 52.50×, and upto 7878.03×. Compared to CUDA-Q, the relative speedup is 12.53×on average and goes up to 439.38×. For larger programs sizes (greater than 15 qubits only) the average relative speedups are 55.42×for Qiskit and 23.03× in case of CUDA-Q. IV. CONCLUSION Although statevector simulations are inherently not indefinitely scalable owing to their exponential space and time footprints, this does not hamper the practicality of TUSQ. TUSQ creates an efficient noisy simulator for any paradigm that performs matrix-vector multiplications under the hood, making it somewhat agnostic to the exact simulation paradigm. Noisy quantum circuit simulation highly valuable for applications like training ML-based QEC decoders [9], ends up being substantially slower compared to noiseless simulation. However, a large amount of this computation is redundant. TUSQ eliminates these redundancies and improve simulation speed. Compared to Qiskit and CUDA-Q, TUSQ achieves an average speedup of 59.06×and13.38×, which goes up to 7878.03×and 439.38×respectively. REFERENCES [1] “Ibm quantum experience,” https://quantum-computing.ibm.com, accessed: 2020-11-18. [2] “Qiskit statevector simulator - gpu,” https://qiskit.github.io/qiskit-aer/ stubs/qiskit aer.StatevectorSimulator.html. 2 [3] H. Bayraktar, A. Charara, D. Clark, S. Cohen, T. Costa, Y.-L. L. Fang, Y. Gao, J. Guan, J. Gunnels, A. Haidar et al., “cuquantum sdk: A high-performance library for accelerating quantum science,” in 2023 IEEE International Conference on Quantum Computing and Engineering (QCE), vol. 1. IEEE, 2023, pp. 1050–1061. [4] Y.-T. Chen, C. Farquhar, and R. M. Parrish, “Low-rank density-matrix evolution for noisy quantum circuits,” npj Quantum Information, vol. 7, no. 1, p. 61, 2021. [5] L. K. Grover, “A fast quantum mechanical algorithm for database search,” in Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, 1996, pp. 212–219. [6] T. Jones, A. Brown, I. Bush, and S. C. Benjamin, “Quest and high performance simulation of quantum computers,” Scientific reports, vol. 9, no. 1, p. 10736, 2019. [7] A. Kandala, A. Mezzacapo, K. Temme, M. Takita, M. Brink, J. M. Chow, and J. M. Gambetta, “Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets,” Nature, vol. 549, no. 7671, pp. 242–246, 2017. [8] R. Koo and S. Toueg, “Checkpointing and rollback-recovery for distributed systems,” IEEE Transactions on software Engineering, no. 1, pp. 23–31, 1987. [9] T. L. Patti, T. Nguyen, J. G. Lietz, A. J. McCaskey, and B. Khailany, “Augmenting simulated noisy quantum data collection by orders of magnitude using pre-trajectory sampling with batched execution,” arXiv preprint arXiv:2504.16297, 2025. [10] A. Peruzzo, J. McClean, P. Shadbolt, M.-H. Yung, X.-Q. Zhou, P. J. Love, A. Aspuru-Guzik, and J. L. O’brien, “A variational eigenvalue solver on a photonic quantum processor,” Nature communications, vol. 5, p. 4213, 2014. [11] P. W. Shor, “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer,” SIAM Journal on Computing, vol. 26, no. 5, p. 1484–1509, Oct 1997. [Online]. Available: http://dx.doi.org/10.1137/S0097539795293172 3