Node Replacement based Approximate Quantum Simulation with Decision Diagrams
Yexin Yan, Stefan Hillmich, Robert Wille, Christian Mayr · 2025
Read Node Replacement based Approximate Quantum Simulation with Decision Diagrams by Yexin Yan, Stefan Hillmich, Robert Wille, Christian Mayr (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-04335.txt.
Introduction
Yexin Yan, Stefan Hillmich, Robert Wille, and Christian Mayr improve a trick for faking quantum computers on classical ones in this 2025 paper. Simulating quantum circuits classically costs resources that explode with size. Decision diagrams compress the simulation by exploiting repeated patterns, but hard circuits like the quantum supremacy benchmarks have almost no repetition to exploit.
Approximate simulation trades a little accuracy for a lot of memory. Earlier methods deleted the least important diagram nodes; this team instead replaces them with similar nodes, slowing the accuracy loss. A hashing technique finds replacement candidates fast enough to keep the overhead small. The result is a better memory-accuracy balance, scaling well as circuits grow deeper. For the supremacy benchmarks the team demonstrates, for the first time, a better-than-linear trade between memory saved and fidelity kept.
Catalog record
| CREATOR | Yexin Yan, Stefan Hillmich, Robert Wille, Christian Mayr |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 42 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-04335
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Node Replacement based Approximate Quantum Simulation with Decision Diagrams Yexin Yan, Stefan Hillmich, Robert Wille, Christian Mayr Abstract Simulating a quantum circuit with a classical computer requires exponentially growing resources. Decision diagrams exploit the redundancies in quantum circuit representation to efficiently represent and simulate quantum circuits. But for complicated quantum circuits like the quantum supremacy benchmark, there is almost no redundancy to exploit. Therefore, it often makes sense to do a trade-off between simulation accuracy and memory requirement. Previous work on approximate simulation with decision diagrams exploits this trade-off by removing less important nodes. In this work, instead of removing these nodes, we try to find similar nodes to replace them, effectively slowing down the fidelity loss when reducing the memory. In addition, we adopt Locality Sensitive Hashing (LSH) to drastically reduce the computational complexity for searching for replacement nodes. Our new approach achieves a better memory-accuracy trade-off for representing a quantum circuit with decision diagrams with minimal run time overhead. Notably, our approach shows good scaling properties when increasing the circuit size and depth. For the first time, a strong better-than-linear trade-off between memory and fidelity is demonstrated for a decision diagram based quantum simulation when representing the quantum supremacy benchmark circuits at high circuit depths, showing the potential of drastically reducing the resource requirement for approximate simulation of the quantum supremacy benchmarks on a classical computer. I Introduction Quantum computing is an emerging computational paradigm that promises to provide computational power far beyond classical computers [ 1 ] [ 2 ] [ 3 ] . ’Quantum Supremacy’ is claimed to be achieved, if a quantum computer performs a task that is impossible for a classical computer to perform within reasonable time and energy [ 4 ] [ 5 ] . The quantum supremacy benchmark (also known as random quantum circuit (RQC)) [ 5 ] was proposed as one such computational task to compare the computational power of a quantum computer and a classical computer. Therefore, simulating the quantum supremacy benchmark on a classical computer more efficiently would narrow down the gap between quantum computers and classical computers. At the same time, simulating the supremacy benchmark on a classical computer also provides verification for the quantum hardware performing the same task [ 6 ] . Different approaches have been proposed for simulating quantum circuits. Tensor network (TN)-based simulators [ 7 ] [ 6 ] can efficiently represent a quantum circuit and calculate a certain quantum state. But calculating the complete state vector still requires exponential time. On the other hand, the decision diagram (DD)-based approach [ 8 ] [ 9 ] can represent the full state vector, but constructing and representing the quantum circuit with a DD might still require exponentially growing resources in the worst case. While exact simulation of the quantum supremacy benchmark almost always requires exponentially growing computational and memory resources, approximate simulation might offer a path to simulate larger and deeper circuits with acceptable accuracy and resources. The goal of approximate quantum simulation is to improve the trade-off between memory and accuracy, i.e. to simulate a quantum circuit with higher accuracy and less memory. Additionally, it would be desirable that the approximation algorithm doesn’t take too much run time. For TN-based approaches, linear trade-off between memory and accuracy when simulating the quantum supremacy circuit has been achieved by adopting the Schrödinger-Feynman algorithm and selectively simulating a fraction of the paths [ 10 ] [ 6 ] . For DD-based approaches, better-than-linear trade-off between memory and accuracy has been achieved by removing nodes with lower contribution [ 11 ] . But as shown in this work, with the node removal approach, the trade-off becomes more linear when increasing the circuit depth, due to further randomization of the state vector. In this work, we focus on reducing the memory requirement of the DD of the quantum supremacy circuit after the DD is constructed. To this end, we propose replacing the nodes with similar nodes instead of removing them. Additionally, we adopt Locality Sensitive Hashing (LSH) to drastically reduce the computational complexity for finding similar nodes for replacement. We demonstrate in this work: 1. substantial improvement of memory-accuracy trade-off compared to the previous work [ 11 ] 2. 4 node replacement strategies suitable for different fidelity regions 3. better memory-accuracy trade-off when scaling up the circuit size 4. an LSH-based algorithm for efficiently searching for similar nodes for replacement 5. for the first time, a strong better-than-linear trade-off between memory and accuracy for the quantum supremacy benchmark at high circuit depths. This paper is organized as follows. In ” II Results ” we show the improvement of our approach compared to the previous work, the 4 node replacement strategies, LSH-based node search and scaling properties. In ” III Discussion ” we summarize the results achieved in this work and discuss about limitations and future work. In ” IV Methods ” we present the details of our approach, including quantifying the fidelity loss when replacing nodes, the 4 node replacement strategies, reasons for choosing the distance metric for LSH, and the implementation of hierarchical Super-Bit LSH. II Results The simulation results are obtained with the quantum supremacy benchmarks [ 5 ] , since they represent the worst case where little redundancy can be exploited. But our approach is generally applicable to other quantum algorithms. First, we show the results of using LSH for node replacement. Then we show the results of node replacement strategies. The results for the node replacement strategies are obtained using LSH. For simplicity, the different node replacement strategies are summarized as ”NxX”, meaning replacing N levels for X times (see ” IV Methods ”). Under this convention, single level node replacement is shown as ”1x1”, multiple level node replacement is shown as ”Nx1”, independent node replacement is shown as ”1xX” and independent multiple level node replacement is shown as ”NxX”. II-A Locality Sensitive Hashing LSH results in drastically reduced program run time for searching for replacement nodes, while maintaining similar fidelity compared to the exhaustive approach (see ” IV-H General Idea of LSH ”). The node replacement strategy 1x1 (see ” IV-D Details of Single Level Node Replacement ”) is chosen to demonstrate the effect of this approach. Fig. 1 : Memory ratio vs. fidelity for exhaustive search (solid lines) and LSH (dots). Quantum supremacy circuits with 4x4 and 4x5 qubits and depths of 10 and 15 are shown (benchmarks inst4x4_10_0, inst4x4_15_0, inst4x5_10_0, inst4x5_15_0). LSH provides a good approximation of the exhaustive approach. In Figure 1 , we show LSH provides a good approximation of the exhaustive approach by comparing LSH with exhaustive approach on 4 benchmark circuits: inst_4x4_10_0, inst_4x4_15_0, inst_4x5_10_0 and inst_4x5_15_0. The root mean square error (RMSE) of memory ratio between LSH and exhaustive is summarized in Table I . The error caused by LSH is around 1% for inst_4x4_10_0 and inst_4x4_15_0, and under 1% for inst_4x5_10_0 and inst_4x5_15_0. In addition, in Table I , we show the run time speed-up for searching for replacement nodes, with the same 4 benchmark circuits as above. The run time is obtained with 50% replaced nodes and 50% replacement nodes in the lowest level of the DD. The number of nodes in the lowest level is