Parallelizing Quantum Simulation With Decision Diagrams

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. 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. Qubits are mathematically constructed in the Hilbert space whose size grows exponentially. Consequently, the scalability of the straightforward statevector approach is limited. It has been proven effective in adopting decision diagrams (DDs) to mitigate the memory cost issue in various fields. In recent years, researchers have adapted DDs into different forms for representing quantum states and performing quantum calculations efficiently. This leads to the study of DD-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 DDs. In this article, we explore several strategies for parallelizing DD operations with a focus on leveraging them for quantum simulations. The target is to find the optimal parallelization strategies and improve the performance of DD-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.