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:2311.18529 · IEEE International Conference on Quantum Computing and Engineering (QCE)

Applying an Evolutionary Algorithm to Minimize Teleportation Costs in Distributed Quantum Computing

Leo Sünkel, Manik Dawar, Thomas Gabor

Published Sep 15, 2024• 12 citations
arXivHTMLPDF

Abstract

By connecting multiple quantum computers (QCs) through classical and quantum channels, a quantum communication network can be formed. This gives rise to new applications such as blind quantum computing, distributed quantum computing, and quantum key distribution. In distributed quantum computing, QCs collectively perform a quantum computation. As each device only executes a sub-circuit with fewer qubits than required by the complete circuit, a number of small QCs can be used in combination to execute a large quantum circuit that a single QC could not solve on its own. However, communication between QCs may still occur. Depending on the connectivity of the circuit, qubits must be teleported to different QCs in the network, adding overhead to the actual computation; thus, it is crucial to minimize the number of teleportations. In this paper, we propose an evolutionary algorithm for this problem. More specifically, the algorithm assigns qubits to QCs in the network for each time step of the circuit such that the overall teleportation cost is minimized. Moreover, network-specific constraints such as the capacity of each QC in the network can be taken into account. We run experiments on random as well as benchmarking circuits and give an outline on how this method can be adjusted to be incorporated into more realistic network settings as well as in compilers for distributed quantum computing. Our results show that an evolutionary algorithm is well suited for this problem when compared to the graph partitioning approach as it delivers better results while simultaneously allows the easy integration and consideration of various problem-specific constraints.

DOI
10.1109/qce60285.2024.10272

Related papers

Time-Aware Qubit Assignment and Circuit Optimization for Distributed Quantum Computing

Leo Sünkel, Jonas Stein, Maximilian Zorn +2 more

The emerging paradigm of distributed quantum computing promises a potential solution to scaling quantum computing to currently unfeasible dimensions. While this approach itself is still in its infancy, and many obstacles must still be overcome before its physical implementation, challenges from the software and algorithmic side must also be identified and addressed. For instance, this paradigm shift requires a new form of compiler that considers the network constraints in general as well as phenomena arising due to the nature of quantum communication. In distributed quantum computing, large circuits are divided into smaller subcircuits such that they can be executed individually and simultaneously on multiple QPUs that are connected through quantum channels. As quantum communication, for example, in the form of teleportation, is expensive, it must be used sparingly. We address the problem of assigning qubits to QPUs to minimize communication costs in two different ways. First by applying time-aware algorithms that take into account the changing connectivity of a given circuit as well as the underlying network topology. We define the optimization problem, use simulated annealing and an evolutionary algorithm and compare the results to graph partitioning and sequential qubit assignment baselines. In another approach, we propose an evolutionary-based quantum circuit optimization algorithm that adjusts the circuit itself rather than the schedule to reduce the overall communication cost. We evaluate the techniques against random circuits and different network topologies. Both evolutionary algorithms outperform the baseline in terms of communication cost reduction. We give an outlook on how the approaches can be integrated into a compilation framework for distributed quantum computing.

arXiv:2507.11707•IEEE International Conference on Quantum Computing and Engineering (QCE)•Aug 30, 2025•3 citations

A Genetic Approach to Minimising Gate and Qubit Teleportations for Multi-Processor Quantum Circuit Distribution

Oliver M. Crampton, Panagiotis Promponas, Richard Chen +3 more

Distributed Quantum Computing (DQC) provides a means for scaling available quantum computation by interconnecting multiple quantum processor units (QPUs). A key challenge in this domain is efficiently allocating logical qubits from quantum circuits to the physical qubits within QPUs, a task known to be NP-hard. Traditional approaches, primarily focused on graph partitioning strategies, have sought to reduce the number of required Bell pairs for executing non-local CNOT operations, a form of gate teleportation. However, these methods have limitations in terms of efficiency and scalability. Addressing this, our work jointly considers gate and qubit teleportations introducing a novel meta-heuristic algorithm to minimise the network cost of executing a quantum circuit. By allowing dynamic reallocation of qubits along with gate teleportations during circuit execution, our method significantly enhances the overall efficacy and potential scalability of DQC frameworks. In our numerical analysis, we demonstrate that integrating qubit teleportations into our genetic algorithm for optimising circuit blocking reduces the required resources, specifically the number of EPR pairs, compared to traditional graph partitioning methods. Our results, derived from both benchmark and randomly generated circuits, show that as circuit complexity increases - demanding more qubit teleportations - our approach effectively optimises these teleportations throughout the execution, thereby enhancing performance through strategic circuit partitioning. This is a step forward in the pursuit of a global quantum compiler which will ultimately enable the efficient use of a 'quantum data center' in the future.

arXiv:2405.05875•May 9, 2024•0 citations

Efficient Time-Aware Partitioning of Quantum Circuits for Distributed Quantum Computing

Raymond P. H. Wu, Chathu Ranaweera, Sutharshan Rajasegarar +3 more

To overcome the physical limitations of scaling monolithic quantum computers, distributed quantum computing (DQC) interconnects multiple smaller-scale quantum processing units (QPUs) to form a quantum network. However, this approach introduces a critical challenge, namely the high cost of quantum communication between remote QPUs incurred by quantum state teleportation and quantum gate teleportation. To minimize this communication overhead, DQC compilers must strategically partition quantum circuits by mapping logical qubits to distributed physical QPUs. Static graph partitioning methods are fundamentally ill-equipped for this task as they ignore execution dynamics and underlying network topology, while metaheuristics require substantial computational runtime. In this work, we propose a heuristic based on beam search to solve the circuit partitioning problem. Our time-aware algorithm incrementally constructs a low-cost sequence of qubit assignments across successive time steps to minimize overall communication overhead. The time and space complexities of the proposed algorithm scale quadratically with the number of qubits and linearly with circuit depth, offering a significant computational speedup over common metaheuristics. We demonstrate that our proposed algorithm consistently achieves significantly lower communication costs than static baselines across varying circuit sizes, depths, and network topologies, providing an efficient compilation tool for near-term distributed quantum hardware.

quant-pharXiv:2603.04126•International Conference on Quantum Communications, Networking, and Computing (QCNC)•Mar 5, 2026•1 citation

Evolutionary-Based Circuit Optimization for Distributed Quantum Computing

Leo Sünkel, Jonas Stein, Gerhard Stenzel +3 more

In this work, we evaluate an evolutionary algorithm (EA) to optimize a given circuit in such a way that it reduces the required communication when executed in the Distributed Quantum Computing (DQC) paradigm. We evaluate our approach for a state preparation task using Grover circuits and show that it is able to reduce the required global gates by more than 89% while still achieving high fidelity as well as the ability to extract the correct solution to the given problem. We also apply the approach to reduce circuit depth and number of CX gates. Additionally, we run experiments in which a circuit is optimized for a given network topology after each qubit has been assigned to specific nodes in the network. In these experiments, the algorithm is able to reduce the communication cost (i.e., number of hops between QPUs) by up to 19%.

arXiv:2509.08074•IEEE International Conference on Quantum Artificial Intelligence (QAI)•Nov 2, 2025•1 citation

An Evolutionary Approach to Optimizing Communication Cost in Distributed Quantum Computation

Mahboobeh Houshmand, Mohammadi, Zahra, Mariam Zomorodi Moghadam +1 more

Distributed quantum computing has been well-known for many years as a system composed of a number of small-capacity quantum circuits. Limitations in the capacity of monolithic quantum computing systems can be overcome by using distributed quantum systems which communicate with each other through known communication links. In our previous study, an algorithm with an exponential complexity was proposed to optimize the number of qubit teleportations required for the communications between two partitions of a distributed quantum circuit. In this work, a genetic algorithm is used to solve the optimization problem in a more efficient way. The results are compared with the previous study and we show that our approach works almost the same with a remarkable speed-up. Moreover, the comparison of the proposed approach based on GA with a random search over the search space verifies the effectiveness of GA.

arXiv:1910.07877•Oct 12, 2019•1 citation

Distribution of Quantum Circuits Over General Quantum Networks

Ranjani G. Sundaram, Himanshu Gupta, C. R. Ramakrishnan

Near-term quantum computers can hold only a small number of qubits. One way to facilitate large-scale quantum computations is through a distributed network of quantum computers. In this work, we consider the problem of distributing quantum programs represented as quantum circuits across a quantum network of heterogeneous quantum computers, in a way that minimizes the overall communication cost required to execute the distributed circuit. We consider two ways of communicating: cat-entanglement that creates linked copies of qubits across pairs of computers, and teleportation. The heterogeneous computers impose constraints on cat-entanglement and teleportation operations that can be chosen by an algorithm. We first focus on a special case that only allows cat-entanglements and not teleportations for communication. We provide a two-step heuristic for solving this specialized setting: (i) finding an assignment of qubits to computers using Tabu search, and (ii) using an iterative greedy algorithm designed for a constrained version of the set cover problem to determine cat-entanglement operations required to execute gates locally. For the general case, which allows both forms of communication, we propose two algorithms that subdivide the quantum circuit into several portions and apply the heuristic for the specialized setting on each portion. Teleportations are then used to stitch together the solutions for each portion. Finally, we simulate our algorithms on a wide range of randomly generated quantum networks and circuits, and study the properties of their results with respect to several varying parameters.

arXiv:2206.06437•IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 1, 2022•39 citations
By connecting multiple quantum computers (QCs) through classical and quantum channels, a quantum communication network can be formed. This gives rise to new applications such as blind quantum computing, distributed quantum computing, and quantum key distribution. In distributed quantum computing, QCs collectively perform a quantum computation. As each device only executes a sub-circuit with fewer qubits than required by the complete circuit, a number of small QCs can be used in combination to execute a large quantum circuit that a single QC could not solve on its own. However, communication between QCs may still occur. Depending on the connectivity of the circuit, qubits must be teleported to different QCs in the network, adding overhead to the actual computation; thus, it is crucial to minimize the number of teleportations. In this paper, we propose an evolutionary algorithm for this problem. More specifically, the algorithm assigns qubits to QCs in the network for each time step of the circuit such that the overall teleportation cost is minimized. Moreover, network-specific constraints such as the capacity of each QC in the network can be taken into account. We run experiments on random as well as benchmarking circuits and give an outline on how this method can be adjusted to be incorporated into more realistic network settings as well as in compilers for distributed quantum computing. Our results show that an evolutionary algorithm is well suited for this problem when compared to the graph partitioning approach as it delivers better results while simultaneously allows the easy integration and consideration of various problem-specific constraints.
The emerging paradigm of distributed quantum computing promises a potential solution to scaling quantum computing to currently unfeasible dimensions. While this approach itself is still in its infancy, and many obstacles must still be overcome before its physical implementation, challenges from the software and algorithmic side must also be identified and addressed. For instance, this paradigm shift requires a new form of compiler that considers the network constraints in general as well as phenomena arising due to the nature of quantum communication. In distributed quantum computing, large circuits are divided into smaller subcircuits such that they can be executed individually and simultaneously on multiple QPUs that are connected through quantum channels. As quantum communication, for example, in the form of teleportation, is expensive, it must be used sparingly. We address the problem of assigning qubits to QPUs to minimize communication costs in two different ways. First by applying time-aware algorithms that take into account the changing connectivity of a given circuit as well as the underlying network topology. We define the optimization problem, use simulated annealing and an evolutionary algorithm and compare the results to graph partitioning and sequential qubit assignment baselines. In another approach, we propose an evolutionary-based quantum circuit optimization algorithm that adjusts the circuit itself rather than the schedule to reduce the overall communication cost. We evaluate the techniques against random circuits and different network topologies. Both evolutionary algorithms outperform the baseline in terms of communication cost reduction. We give an outlook on how the approaches can be integrated into a compilation framework for distributed quantum computing.
Distributed Quantum Computing (DQC) provides a means for scaling available quantum computation by interconnecting multiple quantum processor units (QPUs). A key challenge in this domain is efficiently allocating logical qubits from quantum circuits to the physical qubits within QPUs, a task known to be NP-hard. Traditional approaches, primarily focused on graph partitioning strategies, have sought to reduce the number of required Bell pairs for executing non-local CNOT operations, a form of gate teleportation. However, these methods have limitations in terms of efficiency and scalability. Addressing this, our work jointly considers gate and qubit teleportations introducing a novel meta-heuristic algorithm to minimise the network cost of executing a quantum circuit. By allowing dynamic reallocation of qubits along with gate teleportations during circuit execution, our method significantly enhances the overall efficacy and potential scalability of DQC frameworks. In our numerical analysis, we demonstrate that integrating qubit teleportations into our genetic algorithm for optimising circuit blocking reduces the required resources, specifically the number of EPR pairs, compared to traditional graph partitioning methods. Our results, derived from both benchmark and randomly generated circuits, show that as circuit complexity increases - demanding more qubit teleportations - our approach effectively optimises these teleportations throughout the execution, thereby enhancing performance through strategic circuit partitioning. This is a step forward in the pursuit of a global quantum compiler which will ultimately enable the efficient use of a 'quantum data center' in the future.
To overcome the physical limitations of scaling monolithic quantum computers, distributed quantum computing (DQC) interconnects multiple smaller-scale quantum processing units (QPUs) to form a quantum network. However, this approach introduces a critical challenge, namely the high cost of quantum communication between remote QPUs incurred by quantum state teleportation and quantum gate teleportation. To minimize this communication overhead, DQC compilers must strategically partition quantum circuits by mapping logical qubits to distributed physical QPUs. Static graph partitioning methods are fundamentally ill-equipped for this task as they ignore execution dynamics and underlying network topology, while metaheuristics require substantial computational runtime. In this work, we propose a heuristic based on beam search to solve the circuit partitioning problem. Our time-aware algorithm incrementally constructs a low-cost sequence of qubit assignments across successive time steps to minimize overall communication overhead. The time and space complexities of the proposed algorithm scale quadratically with the number of qubits and linearly with circuit depth, offering a significant computational speedup over common metaheuristics. We demonstrate that our proposed algorithm consistently achieves significantly lower communication costs than static baselines across varying circuit sizes, depths, and network topologies, providing an efficient compilation tool for near-term distributed quantum hardware.
In this work, we evaluate an evolutionary algorithm (EA) to optimize a given circuit in such a way that it reduces the required communication when executed in the Distributed Quantum Computing (DQC) paradigm. We evaluate our approach for a state preparation task using Grover circuits and show that it is able to reduce the required global gates by more than 89% while still achieving high fidelity as well as the ability to extract the correct solution to the given problem. We also apply the approach to reduce circuit depth and number of CX gates. Additionally, we run experiments in which a circuit is optimized for a given network topology after each qubit has been assigned to specific nodes in the network. In these experiments, the algorithm is able to reduce the communication cost (i.e., number of hops between QPUs) by up to 19%.
Distributed quantum computing has been well-known for many years as a system composed of a number of small-capacity quantum circuits. Limitations in the capacity of monolithic quantum computing systems can be overcome by using distributed quantum systems which communicate with each other through known communication links. In our previous study, an algorithm with an exponential complexity was proposed to optimize the number of qubit teleportations required for the communications between two partitions of a distributed quantum circuit. In this work, a genetic algorithm is used to solve the optimization problem in a more efficient way. The results are compared with the previous study and we show that our approach works almost the same with a remarkable speed-up. Moreover, the comparison of the proposed approach based on GA with a random search over the search space verifies the effectiveness of GA.
Near-term quantum computers can hold only a small number of qubits. One way to facilitate large-scale quantum computations is through a distributed network of quantum computers. In this work, we consider the problem of distributing quantum programs represented as quantum circuits across a quantum network of heterogeneous quantum computers, in a way that minimizes the overall communication cost required to execute the distributed circuit. We consider two ways of communicating: cat-entanglement that creates linked copies of qubits across pairs of computers, and teleportation. The heterogeneous computers impose constraints on cat-entanglement and teleportation operations that can be chosen by an algorithm. We first focus on a special case that only allows cat-entanglements and not teleportations for communication. We provide a two-step heuristic for solving this specialized setting: (i) finding an assignment of qubits to computers using Tabu search, and (ii) using an iterative greedy algorithm designed for a constrained version of the set cover problem to determine cat-entanglement operations required to execute gates locally. For the general case, which allows both forms of communication, we propose two algorithms that subdivide the quantum circuit into several portions and apply the heuristic for the specialized setting on each portion. Teleportations are then used to stitch together the solutions for each portion. Finally, we simulate our algorithms on a wide range of randomly generated quantum networks and circuits, and study the properties of their results with respect to several varying parameters.