⚛️ quantum physics

A Multilevel Framework for Partitioning Quantum Circuits

This paper presents a multilevel framework that adapts the Fiduccia-Mattheyses heuristic and introduces a novel objective function to efficiently partition quantum circuits across distributed quantum processing units, significantly reducing entanglement costs and scaling to larger circuit sizes compared to state-of-the-art methods.

Original authors: Felix Burt, Kuan-Cheng Chen, Kin K. Leung

Published 2026-02-05

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Felix Burt, Kuan-Cheng Chen, Kin K. Leung

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a massive, incredibly complex puzzle. In the world of quantum computing, this puzzle is a "quantum circuit"—a set of instructions for a quantum computer. The problem is that today's quantum computers (called QPUs) are like small, single-person workbenches. They can't hold the entire puzzle at once.

To solve the big puzzle, scientists have to split it into smaller pieces and send those pieces to different workbenches (QPUs) that are connected by a network. However, there's a catch: to make the pieces talk to each other, they have to use a special, fragile resource called entanglement (think of it as a "quantum telephone line").

Using these telephone lines is expensive. It takes a lot of time to set them up, and they are very noisy (prone to errors). If you just randomly chop up the puzzle and send the pieces to different workbenches, you end up making thousands of phone calls, which slows everything down and ruins the result.

The Paper's Solution: A Smart "Multilevel" Strategy

This paper introduces a new, smarter way to chop up the quantum puzzle. The authors, Felix Burt, Kuan-Cheng Chen, and Kin K. Leung, built a framework that acts like a highly efficient project manager. Here is how they do it, using simple analogies:

1. The "Teleportation" Toolkit

Usually, when two pieces of the puzzle need to talk, you have to move one piece to the other workbench (State Teleportation) or set up a special link to let them talk from a distance (Gate Teleportation).

The Innovation: The authors realized you can do even better. Sometimes, you can group several instructions together and send them all down the same "quantum line" at once. They call this Multi-gate Teleportation.
The New Trick: They also discovered a method called Nested State Teleportation. Imagine you have a package that needs to go from Workbench A to Workbench C, but it has to stop at Workbench B first. Instead of sending it A→B, then B→C (two expensive trips), they found a way to send it A→C directly, using B just as a temporary holding spot. This saves a huge amount of "phone line" usage.

2. The "Map" and the "Zoom" (Multilevel Framework)

To find the best way to split the puzzle, the authors turned the quantum circuit into a giant, 3D map (a "hypergraph") where every instruction is a node and every connection is a line.

The Problem: This map is so huge and complex that a standard computer program gets lost trying to find the best path. It's like trying to find the shortest route through a city by looking at every single street sign at once.
The Solution (Coarsening): They use a technique called Multilevel Partitioning. Imagine looking at a map of a country.
1. Zoom Out (Coarsening): First, they blur the map so much that cities look like single dots. They solve the problem on this simple, blurry map. It's easy to see the big picture here.
2. Zoom In (Uncoarsening): Then, they slowly zoom back in, revealing the streets. Because they already solved the big picture, they just need to make small adjustments as the details appear.
3. Refinement: At every level of zoom, they use a smart algorithm (based on a famous method called Fiduccia-Mattheyses) to tweak the solution, ensuring the pieces are balanced and the "phone calls" are minimized.

3. Escaping the "Dead Ends"

Sometimes, a computer gets stuck in a "local minimum"—a situation where it thinks it has found the best solution, but it's actually just a small valley in a mountain range, and a much better solution exists over the next hill.

The Fix: The authors added an "Exploratory" mode. Instead of just taking the best step forward, the algorithm occasionally takes a few "risky" steps that might make things worse temporarily, just to see if it can find a better valley on the other side. This helps it escape dead ends and find the true best solution.

The Results: What Did They Achieve?

The authors tested their new framework against the best existing methods using many different types of quantum puzzles (circuits).

Less "Phone Calls": On average, their method reduced the need for entanglement (the "phone calls") by 35% compared to the next best method. In some cases, it was even better.
Faster Processing: Because they used the "Zoom In/Out" strategy, the computer didn't have to work as hard to find the solution. It was often faster than the competition, especially for very large circuits.
Scalability: Their method could handle circuits with hundreds of qubits (the basic units of quantum information) that other methods simply couldn't solve in a reasonable amount of time.

The Catch (Limitations)

The paper notes a trade-off. To get these huge savings in "phone calls," the system sometimes needs more "holding rooms" (communication qubits) on the workbenches to keep the links open while multiple instructions are being processed. If a quantum computer doesn't have enough of these holding rooms, the method might need to be adjusted.

In Summary:
This paper presents a new, highly efficient way to split quantum computer tasks across multiple machines. By using a "zoom-in/zoom-out" strategy and a clever new way of grouping instructions, they managed to drastically reduce the expensive communication required to run these tasks, making distributed quantum computing much more practical and powerful.

Technical Summary: A Multilevel Framework for Partitioning Quantum Circuits

Problem Statement
Distributed Quantum Computing (DQC) offers a pathway to scalable quantum systems by linking multiple Quantum Processing Units (QPUs) via entanglement. However, executing quantum algorithms across these distributed nodes introduces significant overheads. Naive mapping of circuits to QPUs results in high communication costs, specifically the consumption of entangled pairs (e-bits), increased execution time, and heightened noise. The core challenge lies in optimally assigning logical qubits to QPUs and determining the most efficient method to cover non-local operations (gates acting on qubits residing on different QPUs). While existing methods address this, they often fail to capture the full spectrum of teleportation possibilities or struggle with the NP-hard nature of the optimization problem, particularly as circuit sizes and network scales increase.

Methodology
The authors propose a comprehensive multilevel framework that formalizes quantum circuit partitioning as a hypergraph partitioning problem. The workflow consists of several distinct stages:

Graph Construction and Gate Grouping:
- Circuits are transpiled into a specific gate set ( $U(\theta, \phi, \lambda)$ and $CP(\theta)$ ) and converted into a temporally extended graph where nodes represent qubits at specific time steps.
- This graph is generalized into a hypergraph by grouping gates based on "compatibility" for multi-gate teleportation. A group is formed if two-qubit gates share a common control qubit, are contiguous, and are not interrupted by non-diagonal single-qubit gates on the control.
- The framework introduces nested state teleportation, a novel protocol where gate teleportation procedures are partially collapsed into state teleportation. This allows the system to dynamically choose between state and gate teleportation by redirecting the "ending process" of a multi-gate teleportation procedure.
Objective Function:
- A unique cost function is designed to minimize the number of e-bits required. The cost of a hyper-edge is defined by the number of partitions spanned by the receiver set that are not accounted for by the root set (effectively counting cuts that require new entanglement resources).
- The objective is to minimize the sum of these costs across all edges: $\min_{\Phi} \sum_{e \in E} c_e(\Phi)$ .
Partitioning Algorithm (Adapted FM):
- The well-known Fiduccia-Mattheyses (FM) heuristic is adapted to handle the temporal hypergraph structure and specific balance constraints (qubit capacity per QPU at each time step).
- To ensure efficiency, the authors pre-compute costs for all possible hyper-edge configurations and use auxiliary data structures (root/receiver counts) to calculate "delta gains" in constant time.
- To escape local minima inherent in static initial assignments, the authors introduce exploratory passes that do not roll back to the best cumulative gain, allowing the algorithm to traverse sequences of moves that temporarily increase cost to reach better global optima.
Multilevel Framework:
- Inspired by state-of-the-art graph partitioners (e.g., METIS, KaHyPar), the framework employs temporal coarsening. Instead of random node merging, it merges time steps (e.g., window, block, or recursive coarsening).
- The process involves:
  - Coarsening: Reducing temporal resolution to create a smaller, coarser hypergraph.
  - Partitioning: Solving the partitioning problem on the coarsest graph.
  - Uncoarsening and Refinement: Gradually restoring temporal resolution, using the solution from the previous level as a starting point, and applying FM refinement at each level.
- The recursive coarsening strategy (merging adjacent time steps) is identified as the most effective, offering logarithmic scaling in the number of levels.
Circuit Extraction:
- The final partitioned graph is converted back into a distributed quantum circuit. This includes scheduling entanglement generation, starting/ending processes for teleportation, and managing communication qubit resources.

Key Contributions

Formalization of Nested State Teleportation: The paper introduces a unified view where state and gate teleportation are treated as variations of the same procedure, determined by the direction of the ending process. This expands the design space for optimizing entanglement costs.
Multilevel Temporal Partitioning: The adaptation of multilevel techniques specifically for the temporal structure of quantum circuits, allowing the problem to be solved at varying granularities to improve both solution quality and runtime.
Adapted FM Heuristic: A modified Fiduccia-Mattheyses algorithm that efficiently handles the specific cost function and balance constraints of DQC, including mechanisms to avoid local minima through exploratory passes.
Open-Source Implementation: The framework is implemented in the disqco repository, providing a reproducible tool for distributed quantum circuit compilation.

Results
The framework was benchmarked against state-of-the-art methods, including Pytket-DQC (using Partition, PartitionEmbed, and EmbedSteinerDetached workflows) and the Fine-Grained Partitioning (FGP-rOEE) method.

Entanglement Reduction: Across a wide range of circuit types (CP-fraction, QFT, QAOA, Quantum Volume, and QASM benchmarks), the proposed multilevel framework (specifically the recursive variant, MLFM-R) achieved the lowest entanglement costs in most cases.
Quantitative Improvement: On average, the framework reduced entanglement requirements by 35% compared to the next best-performing method.
Scalability: The multilevel approach significantly reduced runtime compared to standard FM and allowed the partitioning of much larger circuits (hundreds of qubits) than competing methods, provided the number of partitions was not excessively large.
Trade-offs: The use of gate grouping (multi-gate teleportation) significantly reduced circuit depth but increased the demand for communication qubits. The framework allows users to tune this trade-off based on available hardware resources.

Significance and Claims
The paper claims that the proposed multilevel framework represents a significant advancement in the compilation of distributed quantum circuits. By unifying various teleportation protocols (state, gate, and nested state) within a single optimization objective and leveraging multilevel graph partitioning techniques, the authors demonstrate that it is possible to substantially minimize the entanglement overhead—the primary bottleneck in DQC.

The authors emphasize that while their current work assumes all-to-all connectivity between QPUs and focuses on networks with fewer than 20 QPUs, the core techniques are designed to be extensible. They assert that this framework provides a robust foundation for future distributed quantum computing compiler stacks, capable of handling the complexity of large-scale, noisy, and constrained quantum networks. The work highlights that optimizing for entanglement minimization is not just a theoretical exercise but a practical necessity for making distributed quantum algorithms feasible on near-term and future hardware.