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

量子計算の並列シミュレーションにおける通信量削減手法

柴田, 章博

Published Mar 24, 2009• 0 citations
OpenAlex

Abstract

Quantum computer simulators are widely used for evaluating the performance of quantum algorithms.In quantum computer simulations, the amount of necessary memory increases exponentially with the number of quantum bits.When performing quantum computer simulations with distributed memory parallel computers, many communications between two nodes are needed.The communication costs between two nodes increase exponentially with the number of quantum bits.In this paper, a fast simulation algorithm for distributed memory parallel computers is proposed.The method can reduce communication costs between nodes by inserting swap gates to the original quantum circuit.The performance of the proposed method was evaluated by experiments.In the experiments, a Ripple carry adder circuit, a Quantum Fourier Transform circuit, a Modular addition circuit, and a Modular multiplication circuit were used.As a result, it has been shown that the proposed method can reduce communication costs.

Related papers

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

Yusuke Kimura, Shaowen Li, Hiroyuki Sato +1 more

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.

arXiv:2405.09033•IEEE International Conference on Quantum Software (QSW)•Jul 7, 2024•2 citations

Distributed Memory Techniques for Classical Simulation of Quantum Circuits

Ryan LaRose

In this paper we describe, implement, and test the performance of distributed memory simulations of quantum circuits on the MSU Laconia Top500 supercomputer. Using OpenMP and MPI hybrid parallelization, we first use a distributed matrix-vector multiplication with one-dimensional partitioning and discuss the shortcomings of this method due to the exponential memory requirements in simulating quantum computers. We then describe a more efficient method that stores only the $2^n$ amplitudes of the $n$ qubit state vector $|ψ\rangle$ and optimize its single node performance. In our multi-node implementation, we use a single amplitude communication protocol that maximizes the number of qubits able to be simulated and minimizes the ratio of qubits that require communication to those that do not, and we present an algorithm for efficiently determining communication pairs among processors. We simulate up to 30 qubits on a single node and 33 qubits with the state vector partitioned across 64 nodes. Lastly, we discuss the advantages and disadvantages of our communication scheme, propose potential improvements, and describe other optimizations such as storing the state vector non-sequentially in memory to map communication requirements to idle qubits in the circuit.

arXiv:1801.01037•Bulletin of the American Physical Society•Jan 2, 2018•7 citations

Minimizing Communications of Quantum Circuit Simulations on Distributed Systems

Longshan Xu, Edwin H.‐M. Sha, Yuhong Song +2 more

Efficient full-state quantum circuit simulations are useful tools for the design of quantum algorithms. Multi-node distributed systems are commonly employed as such simulations require a large amount of computation power and memory space. In distributed systems, communication overhead can be the performance bottleneck. This paper presents a distributed simulation framework called QuanTrans. A quantum circuit is composed of many levels of quantum gates. The simulation is conducted level by level. For circuits with particular structures, it employs a hybrid simulation approach to replace intermediate multi-level communications with one level of final merge operation, whose communication volume is comparable to that of one level of simulation in previous work. A circuit without such structures is sliced to find applicable sub-circuits with a single or multiple consecutive level(s). One level of communication is required for each sub-circuit, so we further propose a polynomial-time optimal circuit slicing algorithm. It can transform any circuit such that the number of sliced sub-circuits is the minimum after transformation. Experimental results show that QuanTrans can effectively reduce communication time and simulation time.

IEEE Transactions on Parallel and Distributed Systems•Jan 12, 2026•1 citation

Cache Blocking Technique to Large Scale Quantum Computing Simulation on Supercomputers

Jun Doi, Hiroshi Horii

Classical computers require large memory resources and computational power to simulate quantum circuits with a large number of qubits. Even supercomputers that can store huge amounts of data face a scalability issue in regard to parallel quantum computing simulations because of the latency of data movements between distributed memory spaces. Here, we apply a cache blocking technique by inserting swap gates in quantum circuits to decrease data movements. We implemented this technique in the open source simulation framework Qiskit Aer. We evaluated our simulator on GPU clusters and observed good scalability.

arXiv:2102.02957•IEEE International Conference on Quantum Computing and Engineering (QCE)•Oct 1, 2020•27 citations

Distributed quantum logic algorithm

Boris Arseniev

Parallel computation enables multiple processors to execute different parts of a task simultaneously, improving processing speed and efficiency. In quantum computing, parallel gate implementation involves executing gates independently in different registers, directly impacting the circuit depth, the number of sequential quantum gate operations, and thus the algorithm execution time. This work examines a method for reducing circuit depth by introducing auxiliary qubits to enable parallel gate execution, potentially enhancing the performance of quantum simulations on near-term quantum devices. We show that any circuit on $n$ qubits with depth $O\left(M n^2\right)$, where $M = M(n)$ is some function of $n$, can be transformed into a circuit with depth $O\left(\log_2(M) n^2\right)$ operating on $O\left(M n\right)$ qubits. This technique may be particularly useful in noisy environments, where recent findings indicate that only the final $O\left(\log n\right)$ layers influence the expectation value of observables. It may also optimize Trotterization by exponentially reducing the number of Trotter steps. Additionally, the method may offer advantages for distributed quantum computing, and the intuition of treating quantum states as gates and operators as vectors used in this work may have broader applications in quantum computation.

arXiv:2411.11979•Nov 18, 2024•0 citations

Arithmetic on a distributed-memory quantum multicomputer

Rodney Van Meter, W. J. Munro, Kae Nemoto +1 more

We evaluate the performance of quantum arithmetic algorithms run on a distributed quantum computer (a quantum multicomputer). We vary the node capacity and I/O capabilities, and the network topology. The tradeoff of choosing between gates executed remotely, through “teleported gates” on entangled pairs of qubits (telegate), versus exchanging the relevant qubits via quantum teleportation, then executing the algorithm using local gates (teledata), is examined. We show that the teledata approach performs better, and that carry-ripple adders perform well when the teleportation block is decomposed so that the key quantum operations can be parallelized. A node size of only a few logical qubits performs adequately provided that the nodes have two transceiver qubits. A linear network topology performs acceptably for a broad range of system sizes and performance parameters. We therefore recommend pursuing small, high-I/O bandwidth nodes and a simple network. Such a machine will run Shor's algorithm for factoring large numbers efficiently.

arXiv:quant-ph/0607160•ACM Journal on Emerging Technologies in Computing Systems•Jan 1, 2008•65 citations
Quantum computer simulators are widely used for evaluating the performance of quantum algorithms.In quantum computer simulations, the amount of necessary memory increases exponentially with the number of quantum bits.When performing quantum computer simulations with distributed memory parallel computers, many communications between two nodes are needed.The communication costs between two nodes increase exponentially with the number of quantum bits.In this paper, a fast simulation algorithm for distributed memory parallel computers is proposed.The method can reduce communication costs between nodes by inserting swap gates to the original quantum circuit.The performance of the proposed method was evaluated by experiments.In the experiments, a Ripple carry adder circuit, a Quantum Fourier Transform circuit, a Modular addition circuit, and a Modular multiplication circuit were used.As a result, it has been shown that the proposed method can reduce communication costs.
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.
In this paper we describe, implement, and test the performance of distributed memory simulations of quantum circuits on the MSU Laconia Top500 supercomputer. Using OpenMP and MPI hybrid parallelization, we first use a distributed matrix-vector multiplication with one-dimensional partitioning and discuss the shortcomings of this method due to the exponential memory requirements in simulating quantum computers. We then describe a more efficient method that stores only the 2n2^n2n amplitudes of the nnn qubit state vector ∣ψ⟩|ψ\rangle∣ψ⟩ and optimize its single node performance. In our multi-node implementation, we use a single amplitude communication protocol that maximizes the number of qubits able to be simulated and minimizes the ratio of qubits that require communication to those that do not, and we present an algorithm for efficiently determining communication pairs among processors. We simulate up to 30 qubits on a single node and 33 qubits with the state vector partitioned across 64 nodes. Lastly, we discuss the advantages and disadvantages of our communication scheme, propose potential improvements, and describe other optimizations such as storing the state vector non-sequentially in memory to map communication requirements to idle qubits in the circuit.
Efficient full-state quantum circuit simulations are useful tools for the design of quantum algorithms. Multi-node distributed systems are commonly employed as such simulations require a large amount of computation power and memory space. In distributed systems, communication overhead can be the performance bottleneck. This paper presents a distributed simulation framework called QuanTrans. A quantum circuit is composed of many levels of quantum gates. The simulation is conducted level by level. For circuits with particular structures, it employs a hybrid simulation approach to replace intermediate multi-level communications with one level of final merge operation, whose communication volume is comparable to that of one level of simulation in previous work. A circuit without such structures is sliced to find applicable sub-circuits with a single or multiple consecutive level(s). One level of communication is required for each sub-circuit, so we further propose a polynomial-time optimal circuit slicing algorithm. It can transform any circuit such that the number of sliced sub-circuits is the minimum after transformation. Experimental results show that QuanTrans can effectively reduce communication time and simulation time.
Classical computers require large memory resources and computational power to simulate quantum circuits with a large number of qubits. Even supercomputers that can store huge amounts of data face a scalability issue in regard to parallel quantum computing simulations because of the latency of data movements between distributed memory spaces. Here, we apply a cache blocking technique by inserting swap gates in quantum circuits to decrease data movements. We implemented this technique in the open source simulation framework Qiskit Aer. We evaluated our simulator on GPU clusters and observed good scalability.
Parallel computation enables multiple processors to execute different parts of a task simultaneously, improving processing speed and efficiency. In quantum computing, parallel gate implementation involves executing gates independently in different registers, directly impacting the circuit depth, the number of sequential quantum gate operations, and thus the algorithm execution time. This work examines a method for reducing circuit depth by introducing auxiliary qubits to enable parallel gate execution, potentially enhancing the performance of quantum simulations on near-term quantum devices. We show that any circuit on nnn qubits with depth O(Mn2)O\left(M n^2\right)O(Mn2), where M=M(n)M = M(n)M=M(n) is some function of nnn, can be transformed into a circuit with depth O(log⁡2(M)n2)O\left(\log_2(M) n^2\right)O(log2​(M)n2) operating on O(Mn)O\left(M n\right)O(Mn) qubits. This technique may be particularly useful in noisy environments, where recent findings indicate that only the final O(log⁡n)O\left(\log n\right)O(logn) layers influence the expectation value of observables. It may also optimize Trotterization by exponentially reducing the number of Trotter steps. Additionally, the method may offer advantages for distributed quantum computing, and the intuition of treating quantum states as gates and operators as vectors used in this work may have broader applications in quantum computation.
We evaluate the performance of quantum arithmetic algorithms run on a distributed quantum computer (a quantum multicomputer). We vary the node capacity and I/O capabilities, and the network topology. The tradeoff of choosing between gates executed remotely, through “teleported gates” on entangled pairs of qubits (telegate), versus exchanging the relevant qubits via quantum teleportation, then executing the algorithm using local gates (teledata), is examined. We show that the teledata approach performs better, and that carry-ripple adders perform well when the teleportation block is decomposed so that the key quantum operations can be parallelized. A node size of only a few logical qubits performs adequately provided that the nodes have two transceiver qubits. A linear network topology performs acceptably for a broad range of system sizes and performance parameters. We therefore recommend pursuing small, high-I/O bandwidth nodes and a simple network. Such a machine will run Shor's algorithm for factoring large numbers efficiently.