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

Leo Sünkel, Manik Dawar, Thomas Gabor

TL;DR

Researchers from LMU Munich have developed an evolutionary algorithm (EA) to minimize the "teleportation tax" in distributed quantum computing. By treating circuit partitioning as a dynamic optimization problem over time, their approach outperforms traditional graph-partitioning methods, offering a flexible way to scale quantum computations across multiple small devices.

What Problem Does This Paper Address?

We are currently in the Noisy Intermediate-Scale Quantum (NISQ) era, where individual quantum computers (QCs) are limited by small qubit counts and high error rates. One promising path to scaling is Distributed Quantum Computing (DQC): connecting multiple small QCs (or QPUs) via a quantum network to act as one large, virtual machine.

However, there is a catch. If a logic gate requires two qubits that are physically located on different QPUs, the system must perform quantum teleportation. Teleportation is "expensive"—it consumes entanglement, a precious and finite resource in quantum networks, and adds significant latency and noise to the computation. To make DQC viable, we need to partition quantum circuits across the network in a way that minimizes these teleportation costs while respecting the limited capacity of each individual QPU.

Methods

The authors propose using an Evolutionary Algorithm (EA) to find the optimal mapping of qubits to QPUs.

1. Solution Representation

Unlike static partitioning, the authors represent a solution as an $n \times m$ matrix, where $n$ is the number of qubits and $m$ is the number of time steps in the circuit. Each cell contains an integer identifying which QPU holds that specific qubit at that specific time. This allows the algorithm to account for the dynamics of the circuit—qubits can move between QPUs as the computation progresses.

2. The Fitness Function

The "goodness" of a solution is calculated based on three factors:

  • Movement Cost: A penalty is added every time a qubit changes its QPU assignment between time steps (representing a teleportation).
  • Gate Cost: A penalty is added if the qubits involved in a multi-qubit gate are not on the same QPU.
  • Capacity Penalty: A heavy "penalty weight" ($\delta$) is applied if a QPU is assigned more qubits than its physical capacity allows.

3. Evolution Strategy

The algorithm starts with a random population of mappings and evolves them over 1,000 generations using:

  • Crossover: Combining parts of two "parent" mappings (single-point or uniform crossover).
  • Mutation: Randomly reassigning a qubit to a different QPU, or shuffling entries within rows or columns to explore new configurations.

Datasets

The researchers evaluated their EA against two types of circuits:

  1. Random Circuits: Generated using Qiskit with depths ranging from 88 to 511 gates and qubit counts of 4 and 8.
  2. Benchmarking Circuits: Specifically, the Quantum Fourier Transform (QFT) from the MQT Bench suite, scaled from 4 to 50 qubits.

They compared their results against a baseline Graph Partitioning (GP) approach using the Kernighan-Lin algorithm, a standard method for dividing networks.

Key Insights and Ideas

  • Time-Awareness is Critical: Traditional graph partitioning often treats a circuit as a static object. By using a matrix representation that includes the time dimension, the EA can decide when it is more efficient to move a qubit versus keeping it stationary, leading to more global optimizations.
  • Flexibility via Penalties: One of the biggest advantages of the EA approach is its extensibility. If a specific network has QPUs with different capacities or unreliable links, you don't need a new algorithm; you simply adjust the penalty terms in the fitness function.
  • Breaking the "Teleport Back" Assumption: Many existing DQC compilers assume a qubit must be teleported back to its "home" QPU after a remote gate. The EA discovers that it is often more efficient to let qubits stay in their new locations, significantly reducing total teleportation counts.

Key Results

The EA consistently outperformed the Graph Partitioning baseline across almost all test cases:

  • Random Circuits: For an 8-qubit circuit with a depth of 511, the EA achieved a teleportation cost of 161.8, compared to 209.4 for the GP approach—a significant reduction in overhead.
  • QFT Benchmarks: While both methods performed equally on very small 4-qubit circuits, the EA pulled ahead as complexity grew. For a 50-qubit QFT circuit, the EA reduced the cost to 1227.6 compared to the baseline's 1253.0.
  • Scalability: The performance gap between the EA and the baseline widened as the circuits became deeper, suggesting that EAs are better at handling the long-term dependencies in complex quantum algorithms.

Limitations and Future Work

While promising, the paper notes a few areas for improvement:

  • Computational Overhead: Evolutionary algorithms are iterative and can be computationally expensive compared to simple heuristics.
  • Refining the Representation: The current model treats every gate as a discrete time step. In reality, multiple gates can often run in parallel. Incorporating more realistic scheduling (like DAG-based representations) could further optimize results.
  • Network Topology: The study primarily looked at a two-QPU setup. Future work will need to test how the EA handles complex network topologies (e.g., star or grid layouts) where the cost of teleportation might vary between different pairs of nodes.

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},
}

Loading related content...

Figure