Decision Diagram vs. State Vector: A Comparative Study on Quantum Computing Simulation Efficiency

To efficiently develop algorithms for quantum com-puters, a quantum simulator capable of handling many qubits at high speed is essential. However, a state vector-based simulator needs to store a vector of length <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$2^{N}$</tex> for <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$N$</tex> qubits. In today's typical desktop computing environment, a maximum of around 30 qubits can be handled. A decision diagram-based simulator is expected to solve the problem of memory requirement for some set of quantum algorithms. Decision diagram stores state vectors as graphs, which may significantly reduce memory usage in the presence of regularities in the state vector. In this study, we have implemented our decision diagram-based quantum simulator and conducted experiments using various algorithms to compare with the state vector-based simulator. Algorithms such as Grover and Shor show significant speedup and superiority of performance for larger numbers of qubits, whereas random circuits with many parameterized rotation gates show slower performance. As described above, researchers should understand the characteristics of simulators so that quantum algorithms can be developed more efficiently.