Quantum circuit simulator (QCS) is essential for designing quantum algorithms because it assists researchers in understanding how quantum operations work without access to expensive quantum computers. Traditional array-based QCSs suffer from exponential time and memory complexities. To address this problem, Decision Diagram (DD) was introduced to compress simulation data by exploring the circuit regularity. However, for irregular circuit structures, DD-based simulation incurs significant runtime and memory overhead. To overcome this challenge, we present FlatDD, a parallel QCS that capitalizes on the strength of both DD- and array-based approaches. FlatDD parallelizes the simulation workload at multiple levels and leverages caching to reuse historical results. To further enhance the simulation performance for deep circuits, FlatDD introduces a gate-fusion algorithm to reduce the computational cost. Compared to state-of-the-art QCSs on commonly used quantum circuits, FlatDD achieves 54.35 × speed-up and 1.91 × memory reduction.
Quantum circuit simulator (QCS) is essential for designing quantum algorithms because it assists researchers in understanding how quantum operations work without access to expensive quantum computers. Traditional array-based QCSs suffer from exponential time and memory complexities. To address this problem, Decision Diagram (DD) was introduced to compress simulation data by exploring the circuit regularity. However, for irregular circuit structures, DD-based simulation incurs significant runtime and memory overhead. To overcome this challenge, we present FlatDD, a parallel QCS that capitalizes on the strength of both DD- and array-based approaches. FlatDD parallelizes the simulation workload at multiple levels and leverages caching to reuse historical results. To further enhance the simulation performance for deep circuits, FlatDD introduces a gate-fusion algorithm to reduce the computational cost. Compared to state-of-the-art QCSs on commonly used quantum circuits, FlatDD achieves 54.35 × speed-up and 1.91 × memory reduction.
Quantum circuit simulator (QCS) is essential for designing quantum algorithms because it assists researchers in understanding how quantum operations work without access to expensive quantum computers. Traditional array-based QCSs suffer from exponential time and memory complexities. To address this problem, Decision Diagram (DD) was introduced to compress simulation data by exploring the circuit regularity. However, for irregular circuit structures, DD-based simulation incurs significant runtime and memory overhead. To overcome this challenge, we present FlatDD, a high-performance QCS that capitalizes on the strength of both DD- and array-based approaches. FlatDD parallelizes the simulation workload at multiple levels and leverages an efficient caching technique to reuse historical results. To further enhance the simulation performance for deep circuits, FlatDD introduces a gate-fusion algorithm to reduce the computational cost. Compared to state-of-the-art QCSs on commonly used quantum circuits, FlatDD achieves 34.81× speed-up and 1.93× memory reduction.
Quantum circuit simulation (QCS) plays an important role in the designs and analysis of a quantum algorithm, as it assists researchers in understanding how quantum operations work without accessing expensive quantum computers. Despite many QCS methods, they are largely limited to simulating one input at a time. However, many simulation-driven quantum computing applications, such as testing and verification, require simulating multiple inputs to reason a quantum algorithm under different scenarios. We refer to this type of QCS as batch quantum circuit simulation (BQCS). In this paper, we present BQSim, a GPU-accelerated batch quantum circuit simulator. BQSim is inspired by the state-of-the-art decision diagram (DD) that can compactly represent quantum gate matrices, but overcomes its limitation of CPU-centric simulation. Specifically, BQSim uses DD to optimize a quantum circuit for reduced BQCS computation and converts DD to a GPU-efficient data structure. Additionally, BQSim employs a task graph-based execution strategy to minimize repetitive kernel call overhead and efficiently overlap kernel execution with data movement. Compared with three state-of-the-art quantum circuit simulators, cuQuantum, Qiskit Aer, and FlatDD, BQSim is 3.25×, 159.06×, and 311.42× faster on average.
Since people became aware of the power of quantum phenomena in the domain of traditional computation, a great number of complex problems that were once considered intractable in the classical world have been tackled. The downsides of quantum supremacy are its high cost and unpredictability. In order to obtain a stronger control over quantum interactions(by reducing its noise) and reduce its cost, numerous researchers are relying on quantum simulators running on classical computers. The critical obstacle facing classical computers in the task of quantum simulation is its limited memory space. Quantum simulation intrinsically models the state evolution of quantum subsystems, i.e., qubits. Qubits are mathematically constructed in Hilbert space whose size grows exponentially with its number. Consequently, the scalability of the straightforward statevector approach is limited. It has been proven effective to adopt decision diagrams to mitigate the memory cost issue in various fields. In recent years, researchers have adapted decision diagrams into different forms for representing quantum states and performing quantum calculations efficiently. This leads to the study of decision diagram based quantum simulation. However, their advantage of memory efficiency does not let it replace the mainstream statevector and tensor network based approaches. We argue the reason is the lack of effective parallelization strategies in performing calculations on decision diagrams. In this work, we explore several strategies for parallelizing decision diagram operations with the focus on leveraging them for quantum simulations. The target is to find the optimal parallelization strategies and improve the performance of decision diagram based quantum simulation. Based on the experiment results, our proposed strategy achieves a 2-3 times faster simulation of Grover's algorithm and random circuits than the state-of-the-art single-thread DD-based simulator DDSIM.
Recent technological advancements show promise in leveraging quantum mechanical phenomena for computation. This brings substantial speed-ups to problems that are once considered to be intractable in the classical world. However, the physical realization of quantum computers is still far away from us, and a majority of research work is done using quantum simulators running on classical computers. Classical computers face a critical obstacle in simulating quantum algorithms. Quantum states reside in a Hilbert space whose size grows exponentially to the number of subsystems, i.e., qubits. As a result, the straightforward statevector approach does not scale due to the exponential growth of the memory requirement. Decision diagrams have gained attention in recent years for representing quantum states and operations in quantum simulations. The main advantage of this approach is its ability to exploit redundancy. However, mainstream quantum simulators still rely on statevectors or tensor networks. We consider the absence of decision diagrams due to the lack of parallelization strategies. This work explores several strategies for parallelizing decision diagram operations, specifically for quantum simulations. We propose optimal parallelization strategies. Based on the experiment results, our parallelization strategy achieves a 2-3 times faster simulation of Grover’s algorithm and random circuits than the state-of-the-art single-thread DD-based simulator DDSIM.
Classical simulation remains essential for the development of quantum algorithms; however, traditional matrix-based methods struggle with scalability. While the Fast Tensor Decision Diagram (FTDD) framework offers a hybrid approach by combining the strengths of Tensor Networks and Decision Diagrams (DDs) for memory-efficient simulation, its core operations are often bottlenecked by memory management structures. Our primary motivation is to address the high computational and spatial cost associated with the hash tables, as well as to simplify the complexity of the simulation workflow. This work introduces systematic, low-level optimizations to the framework. Our main contribution is the enhancement of the memory management layer for the internal tables. We implemented a node reuse mechanism and designed a controlled strategy for hash table growth. These improvements minimize the memory footprint and reduce the costly hashing overhead inherent in DD-based simulators. We performed a thorough experimental analysis using a diverse set of quantum circuits, which were characterized by well-established metrics. Experimental results demonstrate that our enhancements improve the tool's performance and scalability. Notably, these advancements enable the simulation of complex circuits, such as Quantum Fourier Transform, with hundreds of qubits, on a standard server with 2-Tb of memory.
Despite the recent progress in the physical implementation of quantum computers, a significant amount of research still depends on the use of quantum circuit simulators running on classical hardware. While there are several techniques for quantum circuit simulation, many state-of-the-art simulators rely on an array-based simulation approach. However, this array-based approach has exponential memory complexity with respect to the number of simulated qubits. To address this drawback, complementary approaches based on decision diagrams have been proposed. While these approaches allow simulating circuits that could not be simulated before, they come with their own drawbacks. Unfortunately, no detailed case study has been conducted to date, which compares those complementary approaches and their respective strengths and weaknesses. In this work, we are addressing this by providing a survey on both approaches as well as a detailed case study on their respective performances.