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

Leo Sünkel, Manik Dawar, Thomas Gabor

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. 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.

Introduction

In the current Noisy Intermediate-Scale Quantum (NISQ) era, individual quantum computers (QCs) are constrained by limited qubit counts and high error rates. Distributed Quantum Computing (DQC) offers a scalable alternative by interconnecting multiple small QCs via a quantum network to function as a single large-scale virtual machine. However, this architecture introduces a "teleportation tax." When a logic gate involves qubits located on different physical devices, quantum teleportation is required. This process consumes entanglement—a scarce resource—and introduces latency and noise. Minimizing these teleportation costs while adhering to the physical capacity of each device is essential for making DQC viable.

Methods

The researchers developed an Evolutionary Algorithm (EA) to optimize the mapping of qubits to individual quantum processing units (QPUs) over the duration of a circuit.

Solution Representation

Unlike static partitioning methods, the EA represents a solution as an $n \times m$ matrix. Here, $n$ denotes the number of qubits and $m$ represents the discrete time steps of the circuit. Each entry in the matrix identifies which QPU holds a specific qubit at a given time. This dynamic representation allows the algorithm to model qubit movement across the network as the computation progresses.

Matrix representation of qubit-to-QPU mapping over time steps.

Fitness Function and Evolution Strategy

The fitness of a candidate mapping is evaluated based on three primary metrics:

  1. Movement Cost: Penalties for qubits changing QPU assignments between time steps (teleportation).
  2. Gate Cost: Penalties for multi-qubit gates where the involved qubits are on different QPUs.
  3. Capacity Penalty: A heavy weight ($\delta$) applied if a QPU's qubit assignment exceeds its physical capacity.

The population evolves over 1,000 generations using crossover (combining parent mappings) and mutation (randomly reassigning qubits or shuffling entries) to explore the solution space.

Experimental Evaluation

The EA was tested against a baseline Graph Partitioning (GP) approach using the Kernighan-Lin algorithm. Two types of circuits were used for benchmarking:

  • Random Circuits: Depths from 88 to 511 gates with 4 and 8 qubits.
  • Quantum Fourier Transform (QFT): Circuits from the MQT Bench suite, ranging from 4 to 50 qubits.

Results and Discussion

The EA consistently outperformed the GP baseline, particularly as circuit depth and complexity increased.

Comparison of EA and GP results for random circuits of varying depths and qubit counts.

For an 8-qubit random circuit with a depth of 511, the EA reduced the teleportation cost to 161.8, compared to 209.4 for the GP approach. In QFT benchmarks, the EA maintained a lead, achieving a cost of 1227.6 for a 50-qubit circuit versus 1253.0 for the baseline.

A key insight from the study is that the EA often discovers it is more efficient to leave a qubit at a new location after a remote gate rather than teleporting it back to a "home" QPU. This "time-aware" optimization is a significant advantage over static graph partitioning, which often treats a circuit as a static object.

Conclusion

Evolutionary algorithms provide a flexible and effective framework for minimizing communication overhead in distributed quantum networks. By incorporating time-dependent mapping and penalty-based constraints, the EA handles the dynamic nature of quantum circuits better than traditional heuristics. Future work will focus on reducing computational overhead and extending the model to handle more complex network topologies and parallel gate execution.

Summary updated

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.
BibTeX
@inproceedings{sunkel2024applying,
  author = {Leo Sünkel and Manik Dawar and Thomas Gabor},
  title = {{Applying an Evolutionary Algorithm to Minimize Teleportation Costs in Distributed Quantum Computing}},
  booktitle = {QCE},
  year = {2024},
  doi = {10.1109/qce60285.2024.10272},
}
Figure