COMPAS: A Distributed Multi-Party SWAP Test for Parallel Quantum Algorithms

Brayden Goldstein-Gelb, Kun Liu, John M. Martyn, Hengyun (Harry) Zhou, Yongshan Ding and Yuan Liu

A single quantum chip can only hold so many qubits, so people connect several quantum processors (QPUs) into one distributed machine — but running an algorithm across them cheaply is hard, because remote operations between chips are slow, noisy, and consume scarce shared entanglement; this paper (Brown, Yale, Harvard, PNNL, QuEra, and NC State — Brayden Goldstein-Gelb, Kun Liu, and colleagues) presents COMPAS, a co-designed hardware and software architecture that runs the multi-party SWAP test (a core routine that compares many quantum states) across many QPUs at constant circuit depth while consuming pre-shared entangled Bell pairs at a rate that grows only linearly with the width of the data.

The argument in one glance

Problem

One chip holds too few qubits, so we must spread a computation across many

A quantum computer stores information in qubits, and the number of qubits you can pack onto a single chip is sharply limited by control wiring, power, and engineering complexity. To scale up, people build distributed machines: several smaller quantum processing units (QPUs) wired together by quantum communication links. But a quantum algorithm that runs comfortably on one chip does not automatically run well when its data is split across chips, because operations that act on qubits sitting in different modules — remote operations — are the expensive part. Unlike classical computers, quantum machines cannot simply copy data from one node to another (the no-cloning rule forbids it). Instead, two chips interact by consuming a pre-shared entangled resource called a Bell pair, together with ordinary classical messages. Bell pairs are scarce and noisy: state-of-the-art links between atom or ion qubits generate them only a few hundred times per second, with imperfect fidelity. So the central challenge of distributed quantum computing is to run a useful algorithm across modules while keeping the circuit shallow (short in depth, so it finishes before errors pile up) and frugal with Bell pairs.
What people did

Distribute the multi-party SWAP test with existing constant-depth recipes

A key routine worth distributing is the multi-party SWAP test: it compares many quantum states at once by extracting the trace of their product, a number that reveals how much the states overlap and how entangled they are. It underlies useful tasks like estimating Renyi entropies and mitigating errors. Recent work found ways to run this test at constant circuit depth on a single machine, by first preparing a special shared control state (a GHZ state) and then using it to steer a cyclic-shift operation over the states being compared.
Why it fell short

Existing schemes must choose between shallow depth and a narrow control state

When you try to spread these recipes across modules, they force an uncomfortable trade-off. One version keeps the shared GHZ control state narrow but pays for it with circuit depth that grows with the width of each state (the number of qubits per state), so deeper data means a slower circuit. Another version keeps the depth constant but blows up the width of the GHZ control state instead, demanding far more control qubits. A third, naive approach simply teleports each state to wherever it is needed, but that consumes Bell pairs at a rate that grows quadratically with the data width — roughly the width squared — which is ruinous when Bell pairs are the scarcest resource. In short, prior distributed implementations were optimal in circuit depth or in GHZ width, but never in both simultaneously, and the naive alternative wasted entanglement. What was missing was a distributed architecture that stayed constant-depth and kept entanglement consumption low at the same time.
This paper's idea

One state per module, a shared GHZ control, and parallel remote gates via Fanout

COMPAS is a co-designed hardware and software architecture that runs the multi-party SWAP test across a network of QPUs while achieving both constant depth and low entanglement use. Its structure maps the algorithm naturally onto modules: each QPU holds a single state, so state preparation happens locally and in parallel, and the modules only need to communicate during the test itself. A shared GHZ control state is spread across the modules using telegate operations (remote gates driven by pre-shared Bell pairs). The heart of the test is a controlled cyclic shift built from two-party controlled-SWAP (CSWAP) operations between neighboring modules, and COMPAS gives two ways to realize each remote CSWAP — a telegate design and a teledata design (which teleports a neighbor state over, swaps locally, and teleports it back). A key move keeps the depth constant: the many shared-control Toffoli gates inside each CSWAP would normally run one after another, but COMPAS parallelizes them using a constant-depth Fanout construction, and reuses a small pool of ancilla qubits across rounds. The result adds only a constant depth overhead and consumes Bell pairs at a rate linear in the data width, order n times k for k modules of width n — the first scheme to be optimal in both depth and GHZ width at once.

Why this problem is worth solving

Scaling a quantum computer by connecting many small ones only pays off if running an algorithm across the connections is not itself the bottleneck.

There is a hard ceiling on how many qubits fit on one quantum chip: adding qubits means more control wiring, more power, and more ways for things to go wrong, so a single monolithic device cannot grow indefinitely. The natural answer, borrowed from classical computing, is to build a distributed machine out of several modular processors linked together. But quantum links are far more demanding than classical wires. You cannot copy a qubit to another module, so the only way two modules can jointly operate on their qubits is to consume a shared entangled resource — a Bell pair — plus classical communication. Generating Bell pairs between separate quantum modules is slow (hundreds per second on leading hardware) and imperfect, and each remote operation adds latency and error. So the whole promise of distributed quantum computing hinges on algorithms that touch the links as little as possible: shallow circuits that finish before noise accumulates, and thrifty use of the precious Bell-pair supply. An algorithm that needs many deep rounds of remote gates, or a quadratic pile of Bell pairs, would erase the benefit of distributing it in the first place.

The specific routine this paper distributes is one that shows up across quantum algorithms, so making it cheap has broad payoff.

Many quantum tasks boil down to comparing quantum states — measuring how much two states overlap, how mixed or pure a state is, or how entangled its parts are. The multi-party SWAP test is the standard tool for this: given several states, it extracts the trace of their product, a single number in a fixed range that encodes those comparisons. It is the engine behind estimating Renyi entropies (a measure of entanglement and disorder), behind virtual cooling and distillation (techniques that clean up noisy states), and behind certain quantum signal-processing applications. Because the test is so widely reused, an efficient distributed implementation immediately makes all of these algorithms feasible on modular hardware. And unlike a generic quantum circuit, the multi-party SWAP test has a very regular internal structure — a shared control state steering a fixed pattern of swaps — which is exactly the kind of structure a compiler and architecture can exploit to minimize remote communication. That combination, broad usefulness plus exploitable structure, is what makes it the right target.

What people did before, and where it broke

Apply the standard test directly, with depth that grows with data width. Keep the shared GHZ control state narrow and implement the multi-qubit test with a deeper circuit. Where it broke. The circuit depth grows with the width of each state, so comparing states of many qubits makes the circuit slow, and depth is what lets noise accumulate.
Keep depth constant by widening the GHZ control state. Trade depth for width: hold the depth fixed but expand the shared control state so it has far more qubits. Where it broke. The control state balloons in width, demanding many more control qubits — you have simply moved the cost from depth to a different scarce resource.
Naively teleport states to wherever they are needed. Distribute by teleporting each state across the line of modules on demand. Where it broke. Teleporting qubits across the network consumes Bell pairs at a rate that grows quadratically with the data width (roughly the width squared), and Bell pairs are the scarcest, noisiest resource.
Ignore the algorithm structure when compiling to modules. Treat the distributed test like a generic circuit and route remote gates without co-design. Where it broke. Without exploiting the test’s regular structure, remote operations and long-range entanglement pile up, and the resource overhead quickly negates the theoretical advantage of parallel execution.
The gap. No distributed implementation of the multi-party SWAP test was optimal in both circuit depth and GHZ control width at once while keeping Bell-pair use linear — every scheme sacrificed one to get the other.

How COMPAS works

The idea

Split one computation across many separate quantum processors. COMPAS’s premise is distributed quantum computing: rather than demanding one impossibly large chip, it spreads the states being compared across a network of modular QPUs and stitches them together with quantum links. Taking a single quantum computation and partitioning it across many interconnected modules, so that no one device has to hold everything, is the same undertaking the work on a fault-tolerant million-qubit-scale distributed quantum computer covered elsewhere on this site pursues, scaling by interconnection rather than by an ever-bigger monolith. COMPAS does this for the multi-party SWAP test, placing one state per module so preparation stays local and only the test itself crosses the links.

Reuse a small pool of ancilla qubits across the rounds of the test. Qubits are the scarcest resource on a quantum machine, so COMPAS is careful not to allocate fresh helper (ancilla) qubits for every step; instead the Fanout gates in successive rounds share the same small set of ancillas, resetting and reusing them between mid-circuit measurements. Squeezing a computation into far fewer qubits by reusing them across time, rather than laying every operation out on its own dedicated qubits, is the same principle the work on qubit reuse through dynamic circuit cutting (CaQR) covered elsewhere on this site is built on, trading a little extra measurement and reset for a much smaller qubit footprint. COMPAS applies it so that the number of ancilla qubits per module stays linear in the data width even though many Fanout gates are used.

Co-design the algorithmic primitive together with the modular hardware. COMPAS’s efficiency does not come from the algorithm or the hardware alone but from shaping them to each other: the regular structure of the multi-party SWAP test is matched to a module layout and a remote-gate scheme so that communication is minimized and depth stays constant. Designing the computational primitive and the modular hardware in tandem, so the two fit together instead of paying a translation tax, is the same idea the work on co-designing quantum error-correcting codes and modular chiplets covered elsewhere on this site develops, tailoring the hardware organization to the routine it must run. COMPAS co-designs the SWAP-test primitive with a QPU network and a Bell-pair-driven remote-gate implementation, which is why it can be optimal in both depth and control width at once.

Following one SWAP test through COMPAS

Comparing states across modules at constant depth

A trace, drawn from the paper, of how COMPAS runs one distributed multi-party SWAP test.

Step 1 of 5

Each module prepares its own state locally

COMPAS puts one of the states to be compared on each QPU. Every module prepares its state independently and in parallel, so no network communication is needed during input preparation.

Local, parallel preparation keeps the scarce links free until the test begins.

Why it works

Regular structure lets the architecture minimize communication. A generic circuit gives a compiler little to exploit → but the multi-party SWAP test has a fixed control-plus-cyclic-shift shape → so COMPAS can lay states out and route remote gates so only neighboring modules ever communicate.
One state per module keeps preparation off the network. Remote links are the scarce, noisy resource → but assigning one state per QPU lets every module prepare its input locally and in parallel → so the links are spent only during the test, not while building its inputs.
Fanout keeps the depth constant no matter the width. The shared-control Toffoli gates inside each CSWAP would run one after another → but a constant-depth Fanout construction executes them in parallel → so circuit depth stays fixed even as the states get wider, and depth is what limits noise accumulation.
Pre-shared Bell pairs replace moving quantum data at runtime. Qubits cannot be copied between modules → but pre-distributing Bell pairs lets teledata and telegate operations act remotely without transmitting the data during the run → so entanglement is consumed at a rate linear in the width, order n times k, instead of the quadratic cost of naive teleportation.
Reusing ancilla qubits keeps the qubit footprint small. Every Fanout gate needs helper qubits → but the gates operate at different time steps and share one pool of ancillas via reset → so the ancilla count per module stays linear in the width rather than multiplying with the number of gates.

What it costs (trade-offs and scope)

It depends on a supply of pre-shared, distilled Bell pairs. COMPAS consumes Bell pairs as its communication fuel, and because raw Bell pairs are noisy they must be distilled first — the paper estimates roughly three physical Bell pairs are needed to distill one usable one — so the real entanglement budget is several times the nominal count.
It targets one primitive, not arbitrary circuits. The design is built around the multi-party SWAP test and the multivariate trace estimation it supports; the constant-depth, low-entanglement guarantees come from that routine’s regular structure and do not automatically extend to general distributed quantum programs.
Two designs, with a memory-versus-ancilla trade-off. The telegate and teledata constructions have similar error rates and depth, but differ in resource profile: telegate uses fewer ancilla qubits while teledata has a smaller overall memory footprint. The paper recommends teledata for its lower memory cost, but the right choice can depend on the hardware.
Fidelity still degrades with size and link noise. The overall state fidelity falls off roughly as one minus a small multiple of the link error rate, raised to a power that grows with the data width times the number of modules — so for a fixed target error, the number of modules you can chain is bounded, and adding width or noisy links lowers fidelity.
The results are analysis and simulation, not a hardware demonstration. COMPAS is evaluated through resource accounting and circuit- and network-level noise simulation (using Clifford and shot-based simulators), not by running on a real distributed quantum machine; a full experimental validation is left to future work.

The evaluation

Distributing the multi-party SWAP test across k modules of width n

Property	Naive teleportation	Telegate design	Teledata design
Bell pairs consumed per module
Circuit depth (vs number of modules)
Estimated memory per module
Relative fidelity (simulated)
Optimal in depth and control width at once

A comparison of ways to distribute the multi-party SWAP test across k modules, each holding a state of width n. Naive teleportation stays constant-depth but consumes Bell pairs quadratically in the width; COMPAS's telegate and teledata designs both keep depth constant and entanglement linear in the width, achieving optimality in depth and control width simultaneously. The paper recommends the teledata design for its lower memory footprint, with fidelity from circuit- and network-level noise simulation.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

This explainer is based on the paper’s full text (the authors’ arXiv copy of the ASPLOS 2026 paper). The architecture described is the paper’s: COMPAS realizes multivariate trace estimation — specifically the multi-party SWAP test — across a network of modular, distributed QPUs by consuming pre-shared entangled Bell pairs as a resource. It adapts a constant-depth single-machine construction to the distributed setting by putting one state per module (so preparation is local and parallel), spreading a shared GHZ control state across modules with telegates, and implementing the controlled cyclic shift as two-party controlled-SWAPs between neighbors, via either a telegate or a teledata design. A constant-depth Fanout construction parallelizes the shared-control Toffoli gates, and ancilla qubits are reused across rounds. The paper reports that COMPAS adds only constant depth overhead and consumes Bell pairs at a rate linear in the circuit width (order n times k), making it, to the authors’ knowledge, the first distributed multi-party SWAP test optimal in both circuit depth and GHZ control width at once. Resource costs (ancilla, Bell pairs, depth, memory) come from the paper’s accounting, and fidelities from circuit- and network-level noise simulation. Exact circuit constructions, resource tables, noise models, and application details should be read from the paper.

Background

Why connecting quantum modules is where the hard engineering lives

It helps to see COMPAS within the broader push toward modular quantum computers. Because a single chip can hold only so many qubits, the field increasingly expects large machines to be built from many smaller modules wired together — but the wiring is the hard part. A classical computer copies bits between nodes freely; a quantum computer cannot copy a qubit at all, so two modules can only act jointly by spending shared entanglement, and generating high-fidelity entanglement between separate quantum chips remains slow and error-prone. The whole difficulty of distributed quantum computing therefore concentrates at the interconnect: how to move quantum influence between modules with the fewest, shallowest, and least noisy remote operations. Progress has come from two directions at once — building better physical links between chips, and designing algorithms and compilers that lean on the links as lightly as possible. The effort to build fast, high-bandwidth communication pathways between quantum modules is the same terrain the work on a multi-entry communication highway for superconducting quantum chips (MeCH) covered elsewhere on this site occupies, attacking the interconnect from the hardware side. COMPAS attacks it from the algorithm-and-architecture side, showing that for a structured, widely-used routine like the multi-party SWAP test, careful co-design can keep the circuit shallow and the entanglement bill linear even as the computation is spread across many chips.

If you remember only three things

1. A single quantum chip holds only so many qubits, so scaling means building distributed machines from many modular QPUs — but the modules can only act jointly by consuming scarce, noisy pre-shared Bell pairs, so a good distributed algorithm must stay shallow (constant depth) and frugal with entanglement. For the multi-party SWAP test (a core routine that compares many quantum states), prior distributed schemes were optimal in circuit depth or in the width of a shared GHZ control state, but never both, and a naive teleportation approach wasted Bell pairs quadratically in the data width.
2. COMPAS is a co-designed architecture that runs the test across a QPU network with both properties at once. It puts one state on each module (so preparation is local and parallel), spreads a shared GHZ control state with telegates, and builds the controlled cyclic shift from two-party controlled-SWAPs between neighboring modules using a teledata or telegate design over Bell pairs. A constant-depth Fanout construction runs the many shared-control Toffoli gates in parallel, and a small pool of ancilla qubits is reused across rounds, so depth stays fixed and Bell-pair use stays linear in the width (order n times k).
3. The result is, to the authors' knowledge, the first distributed multi-party SWAP test optimal in both depth and GHZ width simultaneously, with the recommended teledata design using the least memory. The costs: it needs a supply of distilled Bell pairs (about three physical per usable one), it targets this one structured primitive rather than general circuits, and fidelity still falls off as the width and module count grow, bounding how many modules can be chained for a given target error. The evaluation is resource analysis plus circuit- and network-level noise simulation, not a hardware demonstration.

Check yourself

Check your understanding

1. Why is running a quantum algorithm across several connected QPUs harder than running it on one chip?
2. What is the multi-party SWAP test used for, and why is it worth distributing efficiently?
3. How does COMPAS keep the circuit depth constant regardless of how many modules take part?
4. Predict: an experimenter wants to chain more and more modules together for a fixed target error. Why does COMPAS not let them add modules without limit?

Sources

The paper is “COMPAS: A Distributed Multi-Party SWAP Test for Parallel Quantum Algorithms” by Brayden Goldstein-Gelb, Kun Liu, John M. Martyn, Hengyun (Harry) Zhou, Yongshan Ding, and Yuan Liu (Brown University, Yale University, Harvard University, Pacific Northwest National Laboratory, QuEra Computing, and North Carolina State University), published at ASPLOS 2026, DOI 10.1145/3779212.3790143. It is licensed CC BY, with an author copy available at arXiv:2511.23434 and code at github.com/kunliu7/Distributed-Q-Algo.

This explainer is written from the paper’s full text (the authors’ arXiv copy). The limited number of qubits per chip motivates distributed architectures that interconnect multiple QPUs, but executing algorithms across them requires co-designing algorithmic primitives with hardware to manage circuit depth and entanglement overhead. The paper identifies multivariate trace estimation — realized as the multi-party SWAP test — as a subroutine naturally suited to distribution and broadly useful for tasks such as estimating Renyi entropies, virtual cooling and distillation, and quantum signal processing. COMPAS realizes it across a multi-party network of modular, distributed QPUs by leveraging pre-shared entangled Bell pairs: it puts one state per module, spreads a shared GHZ control state with telegates, and implements the controlled cyclic shift as two-party controlled-SWAPs between neighbors via a telegate or teledata design, using a constant-depth Fanout construction to parallelize the shared-control Toffoli gates and reusing ancilla qubits across rounds. COMPAS adds only constant depth overhead and consumes Bell pairs at a rate linear in circuit width (order n times k), which the authors state makes it the first scheme optimal in both circuit depth and GHZ width at once; they also analyze network-level errors and simulate circuit-level noise. Resource counts and fidelities are the paper’s own; exact constructions, tables, and application details should be confirmed in the paper.