⚛️ quantum physics

Distributed Quantum Computing via Adaptive Circuit Knitting

This paper introduces Adaptive Circuit Knitting (ACK), a method that optimizes the partitioning of large quantum circuits across multiple QPUs by identifying low-entanglement regions, thereby reducing sampling overheads by up to four orders of magnitude and enabling efficient distributed quantum simulations for both near-term and fault-tolerant architectures.

Original authors: K. Grace Johnson, Aniello Esposito, Gaurav Gyawali, Xin Zhan, Rohit Ganti, Namit Anand, Raymond G. Beausoleil, Masoud Mohseni

Published 2026-03-16

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: K. Grace Johnson, Aniello Esposito, Gaurav Gyawali, Xin Zhan, Rohit Ganti, Namit Anand, Raymond G. Beausoleil, Masoud Mohseni

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. The puzzle represents a quantum system (like a new material or a chemical reaction) that is too big for any single computer to handle.

In the world of quantum computing, we have these powerful puzzle-solvers called Quantum Processing Units (QPUs). But right now, they are like small, specialized jigsaw boxes. They can only hold a few hundred pieces at a time. If you want to solve a puzzle with thousands of pieces, you can't just put it all in one box. You have to split the puzzle up.

This is where the paper comes in. It introduces a clever new method called Adaptive Circuit Knitting (ACK) to solve this problem.

Here is the breakdown using simple analogies:

1. The Problem: The "Too Big to Fit" Puzzle

Quantum computers are amazing, but they are currently limited in size. To solve big problems, we need to split a giant quantum calculation into smaller chunks and run them on different small quantum computers at the same time.

However, quantum computers are weird. In the quantum world, pieces of a puzzle are often "entangled." This means they are magically connected; if you change one piece, it instantly affects another, even if they are far apart.

The Analogy: Imagine two dancers who are holding hands. If you try to separate them into different rooms to dance alone, you break the connection. To make them dance together again later, you have to send a messenger back and forth to tell them what to do.
The Cost: In quantum computing, this "messenger" process is called Circuit Knitting. The problem is that if the dancers were holding hands very tightly (high entanglement), the messenger has to run back and forth millions of times to reconstruct the dance. This is called the sampling overhead, and it's incredibly expensive and slow.

2. The Old Way: Cutting in the Middle

Previously, if you had to split a quantum circuit, you might just cut it right down the middle, like slicing a cake.

The Flaw: If the cake is full of sticky chocolate (high entanglement) right in the middle, you get a huge mess. You have to do a massive amount of work to clean it up and put it back together. This leads to exponential delays.

3. The New Way: Adaptive Circuit Knitting (ACK)

The authors of this paper say: "Don't just cut the cake in the middle. Look for the dry spots."

They developed an algorithm that acts like a smart map reader. Before it cuts the puzzle, it scans the entire system to find the "weak links"—the places where the quantum pieces are least connected to each other.

The Analogy: Imagine you are cutting a giant, tangled ball of yarn. If you cut it where the yarn is tightly knotted, you ruin the ball. But if you find the loose, untangled loops and cut there, the ball falls apart easily, and you can reassemble it with very little effort.
The Magic: The ACK method finds these "loose loops" (low-entanglement regions) automatically. It cuts the quantum circuit exactly where the connection is weakest.

4. The Result: A Massive Speedup

By cutting in these smart, low-entanglement spots, the "messenger" (the classical computer) doesn't have to run back and forth nearly as much.

The Numbers: The paper shows that for certain complex quantum systems (specifically disordered magnetic models), this method reduces the work required by up to 10,000 times (four orders of magnitude).
Real-world impact: Instead of waiting years to get an answer, you might get it in minutes or hours.

5. How They Tested It

Since we don't have giant quantum computers yet, the researchers used super-fast classical supercomputers (with powerful GPUs) to simulate what would happen.

They simulated a "disordered" system (like a messy, random magnetic field).
They showed that their "smart cutter" (ACK) found the best places to split the work, while a "random cutter" (load-balanced) struggled.
They even showed that by using both CPUs and GPUs together, they could simulate these splits incredibly fast.

Summary

Think of Adaptive Circuit Knitting as a smart strategy for a group of friends trying to build a giant Lego castle.

Without ACK: They try to build the whole thing on one table, but the table is too small. They try to split it randomly, but the walls keep falling over because the pieces are glued together. They spend all their time fixing the glue.
With ACK: They look at the blueprints first. They find the parts of the castle that are built with loose bricks. They split the building task exactly at those loose spots. Now, each friend can build their section independently, and when they put the sections together, it snaps perfectly into place with almost no glue needed.

This paper proves that by being smart about where we split the work, we can make quantum computers much more powerful today, even before we have the massive, perfect machines of the future.

1. Problem Statement

The primary challenge in scaling quantum computing toward practical utility is the physical limitation of single Quantum Processing Units (QPUs). Current and near-future hardware (NISQ era) and even future fault-tolerant architectures are constrained by qubit counts (tens to hundreds) and connectivity.

The Scaling Bottleneck: To simulate large quantum systems (e.g., 60+ qubits), workloads must be distributed across multiple QPUs.
The Interconnect Limitation: High-fidelity quantum interconnects (quantum links between QPUs) are not yet mature. Relying on them introduces significant error and latency.
The Circuit Knitting Overhead: "Circuit knitting" offers a solution by partitioning a large circuit into smaller sub-circuits executed on separate QPUs, reconstructing the global result using only classical communication. However, standard circuit knitting relies on Quasi-Probability Decomposition (QPD), which incurs an exponential sampling overhead ( $O(\gamma^{2n})$ ) relative to the number of gates cut. This overhead is driven by the loss of entanglement between partitions; the more entangled the cut, the higher the sampling cost.
The Core Issue: Existing partitioning strategies often use static or load-balanced cuts, failing to account for the dynamic, heterogeneous entanglement structure of specific quantum states. This leads to suboptimal cuts with unnecessarily high sampling costs.

2. Methodology: Adaptive Circuit Knitting (ACK)

The authors propose Adaptive Circuit Knitting (ACK), a method that dynamically identifies optimal cut locations by minimizing the entanglement between circuit partitions.

Theoretical Foundation

Entanglement as a Proxy for Cost: The paper establishes a direct mathematical link between the circuit knitting sampling overhead (quantified by the $\gamma$ factor) and the robustness of entanglement ( $R$ ). For pure states, $\gamma = 1 + 2R$ .
Relation to Entropy: The $\gamma$ factor is shown to be closely related to the Rényi entropy of order 1/2 ( $S_{1/2}$ ), which serves as an upper bound for the von Neumann entropy. Minimizing entanglement entropy at the cut boundaries directly minimizes the sampling overhead.
Tensor Network Representation: The algorithm utilizes Quantum Circuit Tensor Networks. A large quantum state (represented as a Matrix Product State, MPS) is mapped to a quantum circuit with a ladder structure. This allows for variational optimization of the circuit parameters to best represent the state on each partition.

The ACK Algorithm

The algorithm operates in two nested loops (illustrated in Fig. 2 of the paper):

Inner Loop (Variational Optimization):
- The system is partitioned based on a current set of cut locations ( $K$ ).
- For each partition, a variational optimizer finds the parameters ( $\theta$ ) for two-qubit unitary gates in a specific circuit ansatz (staircase circuits of order $M=3$ ) that maximize the fidelity with the target MPS partition.
- This step is trivially parallelizable across different partitions.
Outer Loop (Adaptive Partitioning):
- Using the optimized partitions, the algorithm computes partial entanglement entropy heatmaps.
- It iteratively adjusts the cut locations ( $K$ ) to find boundaries where the entanglement between partitions is minimized.
- Once the optimal cuts are identified, the final sub-circuits and the "knitting" gates (gates crossing the cuts) are passed to the QPD subroutine for execution and observable reconstruction.

Implementation

Hardware: The authors implemented a parallel, GPU-accelerated simulation framework.
Stack: Used MPI (via mpi4py) for distributed memory parallelism across nodes and CuPy for GPU acceleration (replacing NumPy).
Simulation: Simulations were run on HPE-Cray EX systems with NVIDIA GH200 superchips. The circuit knitting execution utilized the qiskit-addon-cutting toolkit.

3. Key Contributions

Adaptive Partitioning Strategy: Introduced a method to dynamically discover low-entanglement boundaries in quantum circuits, rather than relying on static or load-balanced cuts.
Theoretical Link: Formalized the relationship between circuit knitting overhead and entanglement measures (Robustness of Entanglement and Rényi entropy), proving that low-entanglement cuts yield compressed quasi-probability decompositions.
Scalable Simulation Framework: Developed a high-performance, hybrid CPU/GPU implementation capable of simulating distributed quantum workloads, demonstrating that classical simulation can effectively model distributed quantum algorithms.
Disordered System Testbed: Validated the approach on disordered mixed-field Ising models (1D and 2D), which naturally exhibit heterogeneous entanglement structures ideal for this technique.

4. Results

The authors simulated 1D and 2D disordered mixed-field Ising models (up to 60 qubits) and compared the Adaptive (ACK) strategy against Load-Balanced (static) cuts.

Sampling Overhead Reduction:
- For 40-qubit systems, the adaptive strategy reduced sampling overheads by a median factor of 17 and up to 459x for the 90th percentile compared to load-balanced cuts.
- For 60-qubit systems (requiring multiple cuts), the reduction was even more significant: a median factor of 51 and up to 10,167x (approx. 4 orders of magnitude) for the 90th percentile.
- In 2D systems (32 qubits mapped to 1D), the adaptive strategy achieved a median improvement of 46x.
Accuracy: The adaptive approach produced more accurate energy density observables for a fixed number of samples (fixed QPU resources) compared to static cuts.
Scalability: The gap in performance between adaptive and load-balanced strategies widened as the number of cuts increased, suggesting ACK becomes increasingly advantageous for larger, more complex systems.
Performance: The hybrid GPU-CPU implementation showed a 15–30% speedup over GPU-only execution for mixed-width sub-circuits, validating the efficiency of the simulation infrastructure.

5. Significance and Future Outlook

Enabling Large-Scale Simulation: ACK provides a viable path to simulate quantum systems significantly larger than the physical qubits available on a single device, without requiring high-fidelity quantum interconnects.
HPC-QC Integration: The work bridges High-Performance Computing (HPC) and Quantum Computing (QC). It demonstrates how classical HPC resources (GPUs, MPI) can orchestrate distributed quantum workloads, a critical step for the "HPC-QC convergence."
Applicability: While tested on disordered systems (where entanglement is naturally heterogeneous), the authors note the method is applicable to other algorithms with low-entanglement regions, such as the Quantum Fourier Transform (QFT).
Roadmap to Utility: As quantum hardware scales, entanglement-aware distributed approaches like ACK will be essential for managing sampling costs and resource allocation in hybrid quantum-classical architectures, moving the field closer to "utility-scale" quantum computing.

In summary, this paper demonstrates that by intelligently adapting circuit partitions to the underlying entanglement structure of a quantum state, the exponential cost of distributed quantum computing can be drastically reduced, making the simulation of large, complex quantum systems feasible on near-term hardware.