Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2405.09033 · IEEE International Conference on Quantum Software (QSW)

Accelerating Decision Diagram-based Multi-node Quantum Simulation with Ring Communication and Automatic SWAP Insertion

Yusuke Kimura, Shaowen Li, Hiroyuki Sato, Masahiro Fujita

Published Jul 7, 2024• 2 citations
arXivHTMLPDF

Abstract

An N-bit quantum state requires a vector of length 2N, leading to an exponential increase in the required memory with N in conventional statevector-based quantum simulators. A proposed solution to this issue is the decision diagram-based quantum simulator, which can significantly decrease the necessary memory and is expected to operate faster for specific quantum circuits. However, decision diagram-based quantum simulators are not easily parallelizable because data must be manipulated dynamically, and most implementations run on one thread. This paper introduces ring communication-based optimal parallelization and automatic swap insertion techniques for multi-node implementation of decision diagram-based quantum simulators. The ring communication approach is designed so that each node communicates with its neighboring nodes, which can facilitate faster and more parallel communication than broadcasting where one node needs to communicate with all nodes simultaneously. The automatic swap insertion method, an approach to minimize inter-node communication, has been employed in existing multi-node state vector-based simulators, but this paper proposes two methods specifically designed for decision diagram-based quantum simulators. These techniques were implemented and evaluated using the Shor algorithm and random circuits with up to 38 qubits using a maximum of 256 nodes. The experimental results have revealed that multi-node implementation can reduce run-time by up to 26 times. For example, Shor circuits that need 38 qubits can finish simulation in 147 seconds. Additionally, it was shown that ring communication has a higher speed-up effect than broadcast communication, and the importance of selecting the appropriate automatic swap insertion method was revealed.

DOI
10.1109/qsw62656.2024.00025

Related papers

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

Yusuke Kimura, Shaowen Li, Hiroyuki Satō +2 more

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.

IEEE Transactions on Quantum Engineering•Jan 1, 2026•0 citations

Parallelizing quantum simulation with decision diagrams

Shaowen Li, Yusuke Kimura, Hiroyuki Sato +2 more

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.

arXiv:2312.01570•IEEE International Conference on Quantum Software (QSW)•Jul 1, 2023•5 citations

Parallelizing Quantum Simulation With Decision Diagrams

Shaowen Li, Yusuke Kimura, Hiroyuki Satō +1 more

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.

IEEE Transactions on Quantum Engineering•Jan 1, 2024•7 citations

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

Yusuke Kimura, Shaowen Li, Hiroyuki Sato +1 more

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$2^{N}$for$N$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.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 15, 2024•3 citations

Faster algorithm for achieving minimal-size quantum decision diagrams

Juul Sanders, Sebastiaan Brand, Arend-Jan Quist +1 more

The decision diagram (DD) data structure enables fast linear-algebra calculations by bringing vectors into a normal form and subsequently merging equivalent ones, yielding a minimally-sized DD modulo the equivalence relation. A fruitful application area is quantum-circuit simulation, where the vectors represent quantum states. The Local Invertible Map Decision Diagram (LIMDD) type, merges LIM-equivalent (typically Pauli-gate equivalent) vectors, can efficiently simulate Clifford circuits as well as some high-T-count circuits, and has theoretically been proven exponentially faster for simulation than other well-developed data structures, including other common DD variants. However, these exponential advantages have not fully materialized yet in existing implementations, for which the normal-form procedure, which is a highly complex algorithm, is either absent or only partially implemented. We here present a novel normal-form algorithm for Pauli-LIMDDs, achieving a worst-case speedup from $O(n^3)$ to $O(n^2)$ for an $n$-qubit DD node with a single child node while keeping the $O(n^3)$ run time in case of two distinct children nodes. We implement the algorithm as part of QolDDer, our Pauli-LIMDD simulator for quantum circuits, written from scratch in C/C++. The implementation realizes the theoretically-proven advantages of Pauli-LIMDDs on Clifford circuits, is significantly faster than the existing LIMDD simulators on such circuits, and on a public quantum-circuit data set often outperforms them by an order of magnitude. In the future, we envision that our work will enable further application and development of LIMDD variants, not only for quantum design tasks, but also for analysis of linear-algebra-based systems in general.

quant-pharXiv:2606.24789•Lecture notes in computer science•Jun 24, 2026•0 citations

Node Replacement based Approximate Quantum Simulation with Decision Diagrams

Yan, Yexin, Stefan Hillmich, Robert Wille +1 more

Simulating a quantum circuit with a classical computer requires exponentially growing resources. Decision diagrams exploit the redundancies in quantum circuit representation to efficiently represent and simulate quantum circuits. But for complicated quantum circuits like the quantum supremacy benchmark, there is almost no redundancy to exploit. Therefore, it often makes sense to do a trade-off between simulation accuracy and memory requirement. Previous work on approximate simulation with decision diagrams exploits this trade-off by removing less important nodes. In this work, instead of removing these nodes, we try to find similar nodes to replace them, effectively slowing down the fidelity loss when reducing the memory. In addition, we adopt Locality Sensitive Hashing (LSH) to drastically reduce the computational complexity for searching for replacement nodes. Our new approach achieves a better memory-accuracy trade-off for representing a quantum circuit with decision diagrams with minimal run time overhead. Notably, our approach shows good scaling properties when increasing the circuit size and depth. For the first time, a strong better-than-linear trade-off between memory and fidelity is demonstrated for a decision diagram based quantum simulation when representing the quantum supremacy benchmark circuits at high circuit depths, showing the potential of drastically reducing the resource requirement for approximate simulation of the quantum supremacy benchmarks on a classical computer.

arXiv:2507.04335•Jul 6, 2025•0 citations
An N-bit quantum state requires a vector of length 2N, leading to an exponential increase in the required memory with N in conventional statevector-based quantum simulators. A proposed solution to this issue is the decision diagram-based quantum simulator, which can significantly decrease the necessary memory and is expected to operate faster for specific quantum circuits. However, decision diagram-based quantum simulators are not easily parallelizable because data must be manipulated dynamically, and most implementations run on one thread. This paper introduces ring communication-based optimal parallelization and automatic swap insertion techniques for multi-node implementation of decision diagram-based quantum simulators. The ring communication approach is designed so that each node communicates with its neighboring nodes, which can facilitate faster and more parallel communication than broadcasting where one node needs to communicate with all nodes simultaneously. The automatic swap insertion method, an approach to minimize inter-node communication, has been employed in existing multi-node state vector-based simulators, but this paper proposes two methods specifically designed for decision diagram-based quantum simulators. These techniques were implemented and evaluated using the Shor algorithm and random circuits with up to 38 qubits using a maximum of 256 nodes. The experimental results have revealed that multi-node implementation can reduce run-time by up to 26 times. For example, Shor circuits that need 38 qubits can finish simulation in 147 seconds. Additionally, it was shown that ring communication has a higher speed-up effect than broadcast communication, and the importance of selecting the appropriate automatic swap insertion method was revealed.
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.
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.
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.
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 length2N2^{N}2NforNNNqubits. 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.
The decision diagram (DD) data structure enables fast linear-algebra calculations by bringing vectors into a normal form and subsequently merging equivalent ones, yielding a minimally-sized DD modulo the equivalence relation. A fruitful application area is quantum-circuit simulation, where the vectors represent quantum states. The Local Invertible Map Decision Diagram (LIMDD) type, merges LIM-equivalent (typically Pauli-gate equivalent) vectors, can efficiently simulate Clifford circuits as well as some high-T-count circuits, and has theoretically been proven exponentially faster for simulation than other well-developed data structures, including other common DD variants. However, these exponential advantages have not fully materialized yet in existing implementations, for which the normal-form procedure, which is a highly complex algorithm, is either absent or only partially implemented. We here present a novel normal-form algorithm for Pauli-LIMDDs, achieving a worst-case speedup from O(n3)O(n^3)O(n3) to O(n2)O(n^2)O(n2) for an nnn-qubit DD node with a single child node while keeping the O(n3)O(n^3)O(n3) run time in case of two distinct children nodes. We implement the algorithm as part of QolDDer, our Pauli-LIMDD simulator for quantum circuits, written from scratch in C/C++. The implementation realizes the theoretically-proven advantages of Pauli-LIMDDs on Clifford circuits, is significantly faster than the existing LIMDD simulators on such circuits, and on a public quantum-circuit data set often outperforms them by an order of magnitude. In the future, we envision that our work will enable further application and development of LIMDD variants, not only for quantum design tasks, but also for analysis of linear-algebra-based systems in general.
Simulating a quantum circuit with a classical computer requires exponentially growing resources. Decision diagrams exploit the redundancies in quantum circuit representation to efficiently represent and simulate quantum circuits. But for complicated quantum circuits like the quantum supremacy benchmark, there is almost no redundancy to exploit. Therefore, it often makes sense to do a trade-off between simulation accuracy and memory requirement. Previous work on approximate simulation with decision diagrams exploits this trade-off by removing less important nodes. In this work, instead of removing these nodes, we try to find similar nodes to replace them, effectively slowing down the fidelity loss when reducing the memory. In addition, we adopt Locality Sensitive Hashing (LSH) to drastically reduce the computational complexity for searching for replacement nodes. Our new approach achieves a better memory-accuracy trade-off for representing a quantum circuit with decision diagrams with minimal run time overhead. Notably, our approach shows good scaling properties when increasing the circuit size and depth. For the first time, a strong better-than-linear trade-off between memory and fidelity is demonstrated for a decision diagram based quantum simulation when representing the quantum supremacy benchmark circuits at high circuit depths, showing the potential of drastically reducing the resource requirement for approximate simulation of the quantum supremacy benchmarks on a classical computer.