Entanglement model¶

Cut weight — the number of two-qubit gates whose operands land on different QPUs — is the objective every classical partitioner minimizes, and it is not the quantity a cat-entanglement machine pays. This page describes the model QuPort uses instead, the modules that implement it, and how they fit together — from a partitioning objective, through a port-constrained communication plan, down to the circuit that performs it and a proof that it does.

Module	Question it answers	When it runs
`quport.entanglement`	Which operand positions of an operation commute with `Z`?	Everywhere, as the shared correctness rule
`quport.hypergraph`	How many EPR pairs does this partition need?	Partition time, inside the search loop
`quport.aggregation`	Which EPR blocks does this mapped circuit need, under a real port budget?	Compile time, on physical qubits
`quport.schedule.estimate_entanglement_schedule`	How long does that plan take on this interconnect?	Schedule time
`quport.protocol`	What circuit actually performs the plan, and is it right?	Emission and verification
`quport.exact`	How close to optimal is the partition the heuristic found?	Offline, on small instances
`quport.temporal`	Would letting qubits move between QPUs mid-circuit be worth it?	Offline, as an analysis

Why cat-entanglement changes the objective¶

A remote two-qubit gate is not executed by moving quantum state between QPUs. One EPR pair is distributed, and QPU B builds a cat copy b of a root qubit c living on QPU A:

Distribute an EPR pair, half on each QPU.
A applies CX(c -> a), measures a in the Z basis, and sends the outcome; B applies a conditional X. The joint state is now sum_z alpha_z |z>_c |z>_b, so b carries c’s computational-basis label.
Every gate that uses c only through that label runs locally on B against b — one gate, ten gates, as many as the copy survives.
Cat-disentangler: measure b in the X basis, send the outcome back, apply a conditional Z to c.

Step 3 is the whole point, and it is correct exactly when every operation applied to c while the copy is live commutes with Z_c. Such an operation maps |z>_c |psi> to |z>_c U_z|psi>, so the label correspondence survives. An X, H, SX, or a CX that uses c as its target destroys it and the copy must be released first.

Ten gates from one control into one QPU therefore cost ten units of cut weight and one EPR pair.

Diagonality analysis¶

quport.entanglement.diagonal_positions(operation) returns the operand positions on which an operation commutes with Z, from three rules applied in order:

an explicit table for operations whose structure is not otherwise derivable (rzz on both operands, rzx on operand 0, swap/ecr/rxx on neither);
ControlledGate structure — every control operand is diagonal regardless of ctrl_state, and because C(U) = P_0 (x) I + P_1 (x) U, every operand that is diagonal for the base gate stays diagonal once controlled;
a table of diagonal single-qubit gates (z, s, t, rz, p, …).

Anything else is reported as non-diagonal on every operand. That direction of error is the safe one: it can only over-count EPR pairs, never claim a copy that would not survive. tests/test_entanglement.py checks every claim against the actual unitary of every constructible gate in Qiskit’s standard library.

Distributable packets and the λ−1 metric¶

A distributable packet rooted at qubit c is a maximal run of gates over which c stays diagonal. Diagonality is a property of the gate sequence alone, so packets do not depend on placement: build_distributable_packets runs once per circuit, and ebit_cost then evaluates any candidate partition in time linear in the number of packet incidences. That is what makes the metric affordable inside annealing.

The EPR count for partition pi is the connectivity-minus-one (λ−1) metric of hypergraph partitioning: one e-bit per packet per distinct remote QPU its partners occupy.

Two kinds of gate cannot be served by one bipartite copy: two-qubit gates with no diagonal operand, and operations on three or more qubits. A gate of either kind runs on the QPU of its first operand, and each operand sitting anywhere else is teleported there and back, so a gate with f operands off that QPU is charged 2 * f e-bits. The count is per operand: two operands on the same foreign QPU cost two round trips.

Each gate is charged to exactly one root, so the count is exact for that assignment and an upper bound over all assignments. Gates with two diagonal operands (cz, cp, crz, rzz) admit a choice, controlled by symmetric_root:

Policy	Behaviour
`"greedy"` (default)	reuse an operand that already roots an open packet; ties fall back to the lower qubit index
`"min_index"`	always the lower qubit index
`"first_operand"`	always operand 0, as written in the circuit

The `ebit` partitioning strategy¶

ebit runs the same TPCCAP-plus-annealing search as tpccap_sa, with the weighted-cut-distance term replaced by hop-scaled e-bit demand: each e-bit is charged the QPU-graph distance it has to cross, since entanglement swapping consumes a link per hop. On an all-to-all fabric every distance is 1 and the term is exactly the λ−1 count.

w_ebit defaults to 0.0 on tpccap_partition and tpccap_sa_partition, so every pre-existing objective is untouched. Passing packets with w_ebit=0 fills in the ebits and weighted_ebit_distance diagnostics without steering the search.

The other terms have to be rescaled with it¶

Replacing the volume term is not a local change, because the remaining terms were tuned against the term that was removed:

The port penalty is dropped (w_port=0.0). w_port charges squared boundary-qubit overflow, which at its old weight is about as large as an e-bit count with two comm ports per QPU and several times larger with one — a median of 0.8× and 4× on random partitions, up to 11× (examples/reproduce_readme_figures.py penalty_scale) — so with w_dist=0 it competes with the objective rather than biasing it. It also measures the wrong resource: what a cat-entanglement compiler needs a port for is a live cat copy, not every boundary qubit. And port pressure is already priced downstream, since aggregate_remote_operations converts a port shortage into evictions and fresh EPR pairs. Penalising it again double-counts a constraint in the wrong units.
Congestion is kept but re-sourced (congestion_source="ebits"). With uniform weights and gates a cat copy can serve, gate demand upper-bounds EPR demand — aggregation is exactly the business of removing transactions — so routing gate traffic reports congestion that never happens. (Teleported gates, at two EPR pairs each, and decayed weights, which count a gate as less than one, are the exceptions.) The e-bit traffic matrix comes from the same sweep that computes the e-bit cost, so the congestion term and the volume term cannot describe different plans.
Both annealing stages use the same weight. The default 4× congestion asymmetry between the TPCCAP seed and the annealer was tuned for the larger gate-traffic scale and costs e-bits at this one.

Measured over 72 instances – 9 qubits on 3 QPUs, 12 on 3, 16 on 4 and 20 on 5, across ring, switch and mesh interconnects, six depth-20 random circuits each, two comm ports per QPU – rescaling these terms moves the realised means as follows:

	Before	After
EPR pairs actually spent	54.8	52.6
Port evictions	5.82	5.74
Entanglement-aware makespan	9878	9279
Peak link busy time	3783	3464

Fewer EPR pairs, a shorter schedule and less peak link load, with evictions holding steady even though the port penalty is gone: minimising e-bits concentrates traffic into fewer, longer-lived cat copies, which need no more simultaneous ports than the many short copies a boundary-minimising partition scatters around.

It also closes most of the distance to optimal. Over 24 instances – 8 qubits on 2 QPUs, 9 on 3, and 12 on 3 and on 4, six depth-10 random circuits each, all-to-all, one comm port per QPU and every QPU filled:

Strategy	e-bit gap vs. proved optimum
`tpccap`	42.3%
`balanced`	41.0%
`cluster`	22.8%
`tpccap_sa`	15.6%
`ebit`	1.6%
`ebit` before the rescaling	12.6%
the same search on e-bits alone	0.2%

Before the rescaling the ebit search left 12.6% of the e-bits it is named for on the table; it now leaves 1.6%. The search was never the problem — given the e-bit objective alone, the annealer lands within 0.2% of the proved optimum.

Both tables come from examples/reproduce_readme_figures.py (sections rescaling and calibration), which spells out every setting above and reruns them.

Note

congestion_source defaults to "gates" everywhere, so this affects the ebit strategy only. Pass congestion_source="ebits" (with packets) to opt in from your own call to tpccap_partition or tpccap_sa_partition.

Communication aggregation¶

The λ−1 metric assumes comm ports are free. aggregate_remote_operations answers the same question on a mapped circuit where they are not:

a QPU with P ports hosts at most P cat copies at once;
opening a block also needs a free port on the root’s QPU, to run the entangler;
when a port is needed and none is free, the least recently used copy is released, and a fresh EPR pair is spent if that root comes back. The plan reports those as evictions.

The two computations are independent implementations of the same quantity, and with an unbounded port budget they agree exactly whenever the root of each cross-QPU gate is forced – that is, whenever exactly one operand is diagonal, as it is for every cx, and so for every circuit compiled into QuPort’s default basis. tests/test_aggregation.py::test_unbounded_ports_match_hypergraph_ebits pins that down on compiled random circuits.

Symmetric gates (cz, cp, crz, rzz) leave the root free to choose, and there the two part company by design: packets are built without knowing the placement, so build_distributable_packets picks a root from the gate sequence alone, while aggregate_remote_operations knows which QPU every operand sits on and prefers a root whose cat copy already reaches the partner’s QPU. Both are deterministic upper bounds on the same optimum, and either can come out lower on a given circuit.

max_block_gates caps how many gates one block may serve, which trades EPR savings against how long a port stays pinned.

Entanglement-aware scheduling¶

estimate_entanglement_schedule drops the DAG-layer abstraction. Layers impose a global barrier between successive slices and charge one transaction per cross-QPU gate; this estimator runs an as-soon-as-possible list schedule in program order over explicit resources:

one timeline per physical qubit, so QPUs sharing no qubits drift apart freely;
one timeline per classical bit, so feedforward waits for the measurement it reads even when that measurement ran on another QPU;
a pool of comm_qubits_per_qpu ports per QPU, each held for a whole block;
link_capacity channels on each link along the routed path;
hop-scaled, probabilistic distribution: heralded entanglement needs 1 / p attempts in expectation, so time scales as hops * epr_gen / epr_success_prob.

Warning

A plan and the schedule that consumes it must agree on the port budget. Passing a plan built with a larger ports_per_qpu raises rather than silently reporting the work as unschedulable.

From plan to circuit¶

build_telegate_circuit expands a plan into the circuit it stands for. Each cat block becomes, with root c, cat copy b, and EPR helper a:

entangler:     h(a); cx(a, b); cx(c, a); cx(a, b)
block gates:   every gate of the block, with c replaced by b
disentangler:  h(b); cz(b, c)

That is the deferred-measurement form: measure a plus if m: x(b) collapses to cx(a, b), and an X-basis measurement of b plus if m: z(c) collapses to h(b); cz(b, c). It is worth writing that way because a unitary circuit can be checked with a state vector.

Both ancillas provably end in |+> regardless of the data, so an h returns them to |0> and the next block reuses them. The emitted width therefore tracks how many cat copies are live at once, not how many blocks there are.

coherent=False emits the executable form instead — real mid-circuit measurement, if feedforward, and reset — which exports to OpenQASM 3.

Note

Teleport blocks show the state movement as a swap in and out of the host ancilla rather than the Bell-measurement gadget. Expanding the return trip needs a mid-circuit reset, which would make the program non-unitary and therefore unverifiable by the route below. The two e-bits it costs are still accounted for.

Verifying it¶

verify_telegate_equivalence runs the unitary form on a pseudo-random product input, traces out the ancillas, and compares the reduced state of the data qubits with the mapped circuit’s. Unit fidelity certifies both halves at once: the data are right, and the ancillas came back unentangled — leftover entanglement would leave the reduced state mixed and the fidelity below one.

This is what makes the diagonality rule a tested property rather than a stated assumption. A hand-built plan that keeps a cat copy live across an X on its root — exactly what aggregate_remote_operations refuses to emit — drives the fidelity to zero, not merely down.

The command-line examples on this page use a small architecture – four QPUs of three qubits each – saved as small.json:

{
  "n_qpus": 4,
  "compute_qubits_per_qpu": 2,
  "comm_qubits_per_qpu": 1
}

quport ebits --n-logical 4 --depth 4 --config small.json --verify --emit-qasm telegate.qasm

Verification is a state-vector simulation and is refused above 24 qubits.

Because it compares state vectors it speaks about the state a circuit prepares. Terminating measurements are dropped – they read that state out without changing it – while a measurement or reset that later operations depend on changes what the circuit computes, and is refused rather than quietly ignored. So is classical control (an if block or other control-flow operation), which has no state-vector evolution to compare.

Letting qubits move¶

Every partitioner places a logical qubit on one QPU for the whole circuit. That is a real restriction: a qubit that interacts with one neighbourhood early and a different one late pays for the mismatch on every gate of whichever half it is stranded in. A machine that can teleport a qubit between QPUs can move it once instead, for one EPR pair.

quport.temporal models that trade-off under the same accounting: cut the instruction stream into contiguous windows, give each its own assignment, and charge a teleport for each qubit whose QPU changes between neighbouring windows.

from quport import MultiQPUConfig, compile_distributed
from quport.pipeline import random_benchmark_circuit
from quport.temporal import optimize_temporal_partition, split_windows

cfg = MultiQPUConfig(n_qpus=3, compute_qubits_per_qpu=3, comm_qubits_per_qpu=1)
result = compile_distributed(random_benchmark_circuit(12, 20, 0), cfg, seed=0, strategy="ebit")

windows = split_windows(result.packets, 3)
plan = optimize_temporal_partition(
    result.packets, result.partition, cfg.n_qpus, cfg.capacity_per_qpu(), windows
)
print(plan.static_cost, plan.stationary_cost, plan.cost.total)
print(f"{plan.migration_reduction:.1%} saved by letting qubits move")

Cat copies are not cut at a boundary¶

A window boundary is not a barrier. A cat copy stays valid as long as its root stays put, so cost is counted over root epochs — maximal runs of a packet’s gates during which the root’s QPU does not change. Within an epoch, one e-bit is charged per distinct remote QPU the partners occupy at the time their own gates run, so a partner that migrates mid-packet correctly costs a second copy, and teleporting the root starts a new epoch whose copies are paid for afresh. That is conservative rather than forced – teleportation carries the root’s entanglement along, so an old copy would still be valid – and keeps the count an upper bound.

That is what makes the generalisation faithful: with one window, or with the same assignment in every window, the cost is identically ebit_cost. A saving can therefore only be reported when it is one.

Two effects, reported separately¶

The search’s neighbourhood is built on contiguous runs of windows, not single windows — a qubit relocated for one window pays two migrations against one window’s traffic and rarely earns them back, while moving it once and leaving it for several windows pays two migrations against the whole run. A single-window neighbourhood can only reach that through individually worse states, so it never does.

Because that neighbourhood includes the whole-circuit run, the search also improves the static placement. Two different things then contribute to the result, and the report keeps them apart:

Field	Meaning
`static_cost`	the seed placement’s cost
`stationary_cost`	best placement the same search reaches with migration forbidden
`cost.total`	best placement with migration allowed

The temporal phase starts from the stationary optimum, so cost.total <= stationary_cost <= static_cost holds by construction — a plan that moved qubits can never lose to one that did not. migration_reduction is the honest headline: it holds the placement search constant and varies only whether qubits may move.

Measured against the ebit strategy’s partition on six depth-20 random circuits per row, one comm port per QPU on a switch fabric, cut into 2, 3 and 4 windows; the migration column gives the range, over those window counts, of the mean saving:

Instance	Better static placement	Migration, on top
9q / 3 QPUs	0.0%	2.0% – 5.1%
12q / 3 QPUs	0.0%	3.8% – 8.1%
16q / 4 QPUs	0.0%	3.9% – 8.3%
20q / 5 QPUs	0.0%	3.5% – 5.5%

Local search finds nothing to improve in the ebit partition, so every saving here is migration, bought with between 0.7 and 7 qubit moves on average. The numbers come from examples/reproduce_readme_figures.py temporal.

Note

This is an analysis of what time-varying placement is worth. compile_distributed still emits a single static placement; the windows and their assignments are a plan a scheduler could act on, and a number a designer can use to decide whether teleport-based migration is worth building.

quport migrate --n-logical 12 --depth 20 --windows 4 --config small.json

Calibrating against the optimum¶

A heuristic without a reference is a number without a scale: “the e-bit strategy saved 30%” says nothing about how much was left behind. quport.exact solves the same two problems exactly, by branch and bound, on instances small enough for that to terminate:

from quport import MultiQPUConfig, compile_distributed
from quport.exact import optimal_partition, partition_gap
from quport.pipeline import random_benchmark_circuit

# 9 qubits on 3 QPUs of capacity 3.
cfg = MultiQPUConfig(n_qpus=3, compute_qubits_per_qpu=2, comm_qubits_per_qpu=1)
result = compile_distributed(random_benchmark_circuit(9, 10, 0), cfg, seed=0, strategy="ebit")
packets = result.packets  # built from the circuit the partitioner actually saw

best = optimal_partition(9, 3, 3, objective="ebits", packets=packets)
gap = partition_gap(result.partition, 3, 3, objective="ebits", packets=packets)

print(best.objective, best.proved_optimal, best.nodes)
print(f"{gap.relative:.1%} above optimal")

Three things keep the tree small, and none of them is a heuristic shortcut:

Canonical form. Both objectives are invariant under relabelling QPUs and the capacity is uniform, so only restricted-growth assignments are explored — a qubit joins a QPU already in use, or opens the lowest-numbered unused one. That collapses n_qpus**n candidates to set partitions of at most n_qpus blocks.
Monotone bounds. Each incremental cost counts only what the new assignment settles, so the running total is an admissible lower bound and a node that already reaches the incumbent is cut.
A seeded incumbent, so pruning bites from the first node.

max_nodes bounds the run. Exhausting it clears proved_optimal, and the returned partition is then the best one found rather than the optimum — PartitionGap reports that flag, and its absolute is a lower bound on the true gap in that case.

Warning

The tree is over set partitions, so this is for calibration on roughly a dozen qubits, not for compiling. Use it to measure what a heuristic leaves behind, then trust the heuristic at scale.

partition_gap raises rather than reporting a negative gap when a heuristic scores below a proved optimum, because one of the two implementations would then be wrong. That makes it a cross-check between two independent readings of both objectives, which is why tests/test_exact.py runs it over every shipped strategy. The branch and bound is itself checked against exhaustive enumeration over every feasible assignment — 82 cut instances and 34 e-bit instances in tests/test_exact.py — since that is the only real argument that the pruning and the canonical form do not silently lose an optimum.

quport optimal --n-logical 9 --depth 10 --config small.json --strategy ebit

Reading the numbers¶

Field	Where	Meaning
`ebits`	`EbitReport`	EPR pairs with unlimited ports — a lower bound on the plan when every remote gate’s root is forced (the default `cx` basis); symmetric gates can put either figure lower
`epr_pairs`	`AggregationPlan`	EPR pairs under the real port budget
`baseline_epr_pairs`	`AggregationPlan`	what a per-gate telegate compiler would spend
`reduction`	both	fraction saved against that baseline
`evictions`	`AggregationPlan`	copies released early because a port was needed
`peak_cat_copies`	`AggregationPlan`	most cat copies live at once per QPU, each held until its root is disturbed or it is evicted; never exceeds the port budget, by construction
`peak_cat_copies`	`EbitReport`	most port slots held at once per QPU with unlimited ports, counting each cat copy only from its first to its last gate and each teleported operand for its one gate; above the port budget, the unconstrained plan cannot run as is
`entanglement_time`	`EntanglementScheduleSummary`	total link occupancy, summed over links
`unschedulable_gates`	`EntanglementScheduleSummary`	gates no port/link budget could serve

Structured circuits gain most: a control that only picks up Rz rotations keeps its packet open across a whole ladder. Random circuits gain less, because translating to the default basis puts sx and x gates on most qubits and each one closes a packet.

Example¶

from quport import MultiQPUConfig, compile_distributed
from quport.pipeline import random_benchmark_circuit

cfg = MultiQPUConfig(
    n_qpus=4,
    compute_qubits_per_qpu=4,
    comm_qubits_per_qpu=2,
    inter_topology="switch",
    optimization_level=0,
)

result = compile_distributed(
    random_benchmark_circuit(n_logical=16, depth=20, seed=0),
    cfg,
    seed=0,
    strategy="ebit",
)

print(result.ebits.ebits)                      # port-unconstrained lower bound
print(result.aggregation.epr_pairs)            # under the real port budget
print(result.aggregation.baseline_epr_pairs)   # without aggregation
print(result.entanglement_schedule.makespan)

The same report is available from the CLI:

quport ebits --n-logical 16 --depth 20 --seed 0 --out entanglement_plan.json

Entanglement model¶

Why cat-entanglement changes the objective¶

Diagonality analysis¶

Distributable packets and the λ−1 metric¶

The ebit partitioning strategy¶

The other terms have to be rescaled with it¶

Communication aggregation¶

Entanglement-aware scheduling¶

From plan to circuit¶

Verifying it¶

Letting qubits move¶

Cat copies are not cut at a boundary¶

Two effects, reported separately¶

Calibrating against the optimum¶

Reading the numbers¶

Example¶

The `ebit` partitioning strategy¶