Decision diagrams trade accuracy for efficient circuit simulation of complexity.

The simulation of quantum circuits presents a significant computational challenge, demanding resources that grow exponentially with circuit complexity. Researchers are therefore exploring methods to represent these circuits more efficiently, accepting a degree of approximation to reduce memory requirements. Yexin Yan, Stefan Hillmich, Robert Wille, and Christian Mayr detail a novel approach to approximate quantum simulation utilising decision diagrams, a data structure designed to represent Boolean functions efficiently. Their work, entitled ‘Node Replacement based Approximate Quantum Simulation with Decision Diagrams’, introduces a technique where less critical nodes within the circuit representation are replaced with similar alternatives, mitigating fidelity loss during memory reduction. The team further incorporates Locality Sensitive Hashing (LSH), an algorithmic technique used to efficiently identify similar items within a large dataset, to accelerate the node replacement process. This method demonstrably improves the balance between simulation accuracy and memory usage, particularly when applied to complex ‘supremacy benchmark’ circuits, and offers a potentially scalable pathway towards simulating larger quantum systems on classical computers.

Quantum computation promises computational advantages over classical approaches for specific problems, driving research into demonstrating this potential through the achievement of quantum supremacy—solving a problem intractable for even the most powerful classical computers. Establishing supremacy requires identifying suitable computational challenges and then verifying the accuracy of quantum solutions.

Classical simulation of quantum circuits faces limitations due to the exponential growth in resources needed to represent the quantum state. Tensor networks and decision diagrams (DDs) are employed to mitigate this, but their effectiveness diminishes as circuit size increases. DDs represent the full quantum state vector, but can become unwieldy for circuits lacking inherent redundancies. Consequently, researchers are increasingly focused on approximate simulation methods, balancing computational cost with acceptable accuracy to analyse larger and deeper quantum circuits.

Recent work concentrates on improving this trade-off by selectively reducing the complexity of DD representations. Rather than simply discarding less significant components, this study actively replaces them with similar alternatives, preserving fidelity during memory reduction. Cosine similarity—a measure of the angle between two vectors—is used to quantify the similarity between nodes within the DD, identifying suitable replacements.

To manage the computational cost of this search, the researchers employ Super-Bit Locality Sensitive Hashing (LSH), a technique for efficiently finding approximate nearest neighbours in high-dimensional spaces. Traditional LSH methods can struggle with varying data distributions, prompting the development of Super-Bit LSH, which offers improved performance. A key innovation is the introduction of hierarchical LSH, a dynamic approach that adjusts the number of hash buckets—containers used to group similar nodes—based on the number of nodes at each level of the DD. This adaptability optimises performance as circuit size and depth increase.

The combined effect of node replacement, Super-Bit LSH, and hierarchical LSH demonstrably improves the memory-accuracy trade-off for representing quantum circuits. Simulations can be performed with significantly reduced memory requirements while maintaining a reasonable level of accuracy. Importantly, this approach exhibits good scaling properties, meaning its performance does not degrade rapidly as circuit size and depth increase.

For the first time, researchers have demonstrated a better-than-linear trade-off between memory and fidelity when simulating supremacy benchmark circuits at high depths. This suggests the potential for drastically reducing the resources needed for approximate simulation of these complex quantum computations on classical hardware, offering a valuable tool for verifying and benchmarking quantum algorithms as their scale and complexity continue to grow.