Improving Decision Diagram-Based Quantum Circuit Simulation Using Static Variable Ordering and Multinode Ring Communication
Open Access
- 15 January 2026
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Quantum Engineering
- Vol. 7, 1-15
Abstract
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.Keywords
This publication has 31 references indexed in Scilit:
- Start Small But Dream Big: On Choosing a Static Variable Order for Multiplier BDDs2023
- Reordering Decision Diagrams for Quantum Computing Is Harder Than You Might Think2022
- Concurrency in DD-based Quantum Circuit Simulation2020
- Massively parallel quantum computer simulator, eleven years laterComputer Physics Communications, 2019
- Hand-waving and interpretive dance: an introductory course on tensor networksJournal of Physics A: Mathematical and Theoretical, 2017
- A practical introduction to tensor networks: Matrix product states and projected entangled pair statesAnnals of Physics, 2014
- Analysis of Variable Reordering on the QMDD Representation of Quantum Circuits2007
- Efficient Classical Simulation of Slightly Entangled Quantum ComputationsPhysical Review Letters, 2003
- Multi-Terminal Binary Decision Diagrams: An Efficient Data Structure for Matrix RepresentationFormal Methods in System Design, 1997
- Finitely correlated states on quantum spin chainsCommunications in Mathematical Physics, 1992