Improving Decision Diagram-Based Quantum Circuit Simulation Using Static Variable Ordering and Multinode Ring Communication

Currently the development of quantum computers is active; however, large-scale machines remain limited and noisy. Furthermore, such quantum computers do not allow direct access to state vectors, posing challenges for quantum algorithm development. Quantum circuit simulators on classical computers offer a solution, with decision diagram (DD)-based simulators being particularly memory-efficient for representing quantum states. However, DD-based simulation still requires optimization, especially concerning variable ordering and multi-node parallelization. Processing time for DDs heavily depends on variable order, but existing static variable ordering methods did not have general applicability. The prior multi-threaded DD simulations showed slowdowns. This study proposes two techniques to address these issues. The first is a scoring-based heuristic static variable ordering method that analyzes an input quantum circuit, such as the distribution of parameterized rotations and multi-bit gates, to suppress the growth of graph nodes and amount of computation. The second is a ring communication approach that reduces communication overhead when performing parallel simulations across multiple computing nodes. Parallel computation requires data exchange between nodes, which results in additional communication time. The proposed ring communication method can eliminate broadcast communication, thereby reducing the waiting time until communication is completed. Evaluations using various benchmark circuits demonstrate that the proposed ordering achieves up to a 4.5 speedup in a single-node environment. Furthermore, the ring communication exhibits superior scalability, achieving up to an 11x speedup with 16 computing nodes. The proposed variable ordering method generally reduces the overall simulation time in multi-node environments.