SpiderLS: Leveraging Full ZX Reduction for Lattice Surgery Compilation

AI summary

Overview

Research area: Fault-tolerant quantum computing — specifically compilers that translate logical quantum circuits into surface-code lattice surgery schedules, using the ZX-calculus as an intermediate representation.

Technical level: Advanced. The paper assumes familiarity with surface code stabilizers, logical patches and boundary types, Pauli-product measurements (PPMs), and ZX-diagram rewrite rules.

Scope (one sentence): The paper presents SpiderLS, a lattice surgery compiler that removes the degree-four restriction on ZX spiders imposed by prior ZX-based compilation, lowers the resulting high-arity interactions to multi-patch Pauli-product measurements, and routes them layer by layer — reporting average reductions of 49.2% in spacetime volume and 99.8% in compilation time versus the prior ZX-based compiler, TopoLS.

What This Paper Is About

Lattice surgery compilers must turn a logical circuit into a schedule of patch merges and splits, and the total cost is measured as spacetime volume (area × time steps). Recent work (TopoLS) showed that ZX-diagrams make a good intermediate representation, but it only applied spider fusion and deliberately kept every spider at degree ≤ 4 so each spider could be embedded as a single physical lattice surgery junction with at most four ports. SpiderLS asks what happens if that restriction is dropped: it performs full ZX reduction, then handles the resulting high-degree spiders by compiling them into multi-patch Pauli-product measurements instead of single junctions.

Key Contributions

1. Removing the degree-four junction bottleneck. The paper formalizes why prior ZX-based compilation is limited: a single junction has ports drawn from one boundary pair (E/W for X, N/S for Z) plus one incoming and one outgoing temporal direction, giving |ports(v)| ≤ 4 and hence deg(v) ≤ 4 for every spider. SpiderLS shows this bound constrains only the representation, not what lattice surgery can execute.

2. A lowering path for high-arity interactions via multi-patch measurements. A single-control, k-target CZ fuses into a control spider of degree k+2, which exceeds the bound once k > 2. SpiderLS instead decomposes CZ^(k)(q_c; q_1…q_k) into M_{Z^k X}(q_1,…,q_k,q_A); M_{ZZ}(q_c,q_A), so extra targets increase the arity of the first measurement rather than the number of ancilla patches or measurement stages. The three-target case becomes the four-patch measurement M_{ZZZX}(q_1,q_2,q_3,q_A).

3. A complete compilation pipeline. Circuit → ZX translation with PyZX → full_reduce() → execution-order extraction on the reduced graph (Algorithm 1) → grouping of compatible interactions into multi-target operations → lowering to PPMs with explicit patches and Pauli boundaries → logical scheduling → layer-wise, structure-aware spacetime routing.

4. A bounded, commit-or-defer router. Instead of Monte Carlo tree search over an entire layer's joint design space, routing solves each measurement locally against already-fixed geometry, with candidate work bounded by ν·s for s measurements; if no compatible route exists, the measurement is deferred to a later physical layer while independent ready measurements proceed.

5. Evaluation against three compilers. SpiderLS is compared with circuit-based compilers Liblsqecc and DASCOT and the ZX-based compiler TopoLS on algorithmic and randomly generated circuits, reporting average reductions of 49.2% in spacetime volume and 99.8% in compilation time versus TopoLS, plus comparable or lower T-port density on Clifford+T workloads.

Main Findings

• Spacetime volume: SpiderLS achieves an average 49.2% reduction in spacetime volume compared with the prior ZX-based compiler, TopoLS, across representative algorithmic and random workloads.
• Compilation time: SpiderLS achieves an average 99.8% reduction in compilation time compared with TopoLS.
• T-port density: On Clifford+T workloads, SpiderLS reports comparable or lower T-port density than the baselines (the provided content gives no numeric values for this metric).
• Worked four-qubit example: The prior approach needs five time steps for the example circuit. SpiderLS fully reduces the diagram to a graph containing a degree-five Z spider, groups three CZs sharing control q_2 into the single operation CZ^(3)(q_2; q_0,q_1,q_3) plus the remaining CZ(q_0,q_1), reducing four operations to two, and produces a two-step spacetime realization.
• Executable vs. representable: deg(v) > 4 does not mean "unimplementable by lattice surgery"; it means the interaction cannot be drawn as one four-port junction. This is the conceptual core of the paper.
• Reduced-graph example structure: The running circuit's fully reduced diagram contains six Z spiders connected by nine H edges; the ordering pass walks the active frontier through three H moves, emitting the CZ interactions in stages.
• Scalability: The authors report strong scalability, attributed to replacing joint layer-level optimization with bounded local searches (candidate work ≤ ν·s rather than a search tree over all routing combinations).
• Not reported in the provided content: individual benchmark circuit names, circuit counts and sizes, absolute spacetime volumes, T-counts, hardware or runtime parameters, and the full experimental tables. The supplied text truncates partway through Section 4.2 (target code generation), so the results section is absent.

Methodology in Plain English

The pipeline works in four stages.

1. Reduce hard, then recover an order. The input Clifford+T circuit is translated into a ZX-diagram with PyZX, then passed through PyZX's full_reduce(), which puts the diagram in graph-like normal form (Z spiders plus H edges), eliminates Clifford structure, fuses remaining Pauli structure into phase gadgets, and repeats. Full reduction destroys the circuit's sequential order, so SpiderLS re-derives one directly from the reduced graph using four local rules: emit CZs for edges whose two endpoints are both "active"; measure and retire active non-output spiders that have no edges left; let an active spider with exactly one remaining edge move to its neighbor (an H operation, migrating the live data patch); and, if work is blocked, activate the inactive spider adjacent to the most unprocessed edges, initializing a new data patch in |+⟩. A maximal matching over executable edges batches CZs whenever possible.

2. Rebuild a target program. Phases of the reduced spiders are multiples of π/4 (κ_v π/4 with κ_v in Z_8), and the nonzero cases are grouped into gates. Compatible interactions sharing a logical qubit — e.g. several CZs on the same control — are collapsed into one single-control multi-target operation.

3. Lower to measurements. Each grouped operation is decomposed into Pauli-product measurements using an ancilla prepared in |0⟩, for instance CZ(q_0,q_1) → M_{ZX}(q_1,q_A); M_{ZZ}(q_0,q_A). Corrections are tracked in a Pauli frame rather than applied physically. Because the PPMs name their participating qubits and Pauli types, both the patches involved and the boundary types required at each terminal are explicit.

4. Schedule and route. Measurements become logical layers based on dependencies; the first-stage measurements in the example run concurrently, the dependent ones follow. Routing then places and connects each measurement against the geometry already committed, searching only a bounded local candidate set. A route that fits is committed; one that does not is pushed to a later physical layer — using time as a spill resource for spatial conflicts instead of solving the whole layer jointly.

Why This Matters

Impact on research. The paper reframes a constraint that looked physical as a representational artifact. Once you accept that a high-degree ZX spider is a multi-patch measurement rather than an over-subscribed junction, the ZX IR can be reduced much more aggressively, and the aggressive reduction translates directly into smaller spacetime volume and vastly cheaper compilation. The 99.8% compilation-time drop is notable because it comes from architectural choices (bounded local routing plus commit-or-defer) rather than from tuning a search.

Real-world applications (as motivating context for fault-tolerant compilation):

• Compiling chemistry and materials-simulation circuits, where logical qubit counts and T-gate counts are dominated by arithmetic and phase rotations.
• Compiling cryptographic circuits, such as modular-exponentiation workloads for Shor-style factoring.
• Compiling optimization and sampling workloads (QAOA-style and related near-term-to-fault-tolerant hybrids) where circuit structure varies widely and compiler overhead matters as much as circuit depth.
• Design-space exploration for fault-tolerant hardware, where the compiler's patch footprint and time-step count set the physical qubit budget of a machine.

Industry relevance. Spacetime volume and compile time are the two quantities that determine whether a fault-tolerant machine's resource estimate is feasible and whether a compiler can be run in a practical design loop. A compiler that reduces measured spacetime volume by roughly half while cutting compile time by nearly three orders of magnitude makes iterative, workload-driven architecture planning tractable, and targets the surface-code/lattice-surgery stack that major quantum hardware efforts have converged on.

Future Directions

• Optimality of the ordering pass. The execution order is derived from the reduced graph by a greedy frontier expansion that activates the spider with the most blocked edges; how close this heuristic comes to a minimum-depth schedule, and whether better orderings exist, is left open.
• The cost of commit-or-defer. The paper explicitly states that its routing is not globally optimal and deliberately trades joint layer-level optimization for bounded conditional searches. Characterizing when deferral inflates time steps, and how large ν should be, is a natural follow-up.
• Beyond Clifford+T. Non-Clifford structure is handled through the phase-gadget machinery inherited from full_reduce(); extending the multi-target grouping and PPM lowering to denser non-Clifford workloads, and quantifying T-port density rather than reporting it qualitatively, is untested in the provided content.
• Coupling router feedback back into ordering and grouping. Routing, scheduling, and ordering are currently sequential passes; whether measurements that fail to route should inform the earlier grouping or frontier decisions is an open design question.

Target Audience

Researchers and graduate students working on fault-tolerant quantum architectures and quantum compiler design, particularly those using ZX-calculus as an IR or modeling surface-code lattice surgery. It is also relevant to quantum architecture and resource-estimation teams who need to know how much of a spacetime-volume estimate is a genuine hardware requirement versus an artifact of the compiler's intermediate representation. Readers without a background in stabilizer codes, logical patch boundaries, and PPM decomposition will find the paper hard going; the background section covers the needed surface-code and ZX material but assumes comfort with the underlying formal notation.

Authors’ abstract

Lattice surgery compilation plays a central role in translating fault-tolerant quantum programs into efficient surface code realizations, where both spatial and temporal resources directly determine the cost of execution. Recent work has demonstrated the benefits of using ZX-diagrams as an intermediate representation for lattice surgery compilation, enabling semantics-preserving transformations that reduce spacetime cost. However, existing compilation restricts ZX reduction to preserve diagram structures that can be directly embedded as lattice surgery junctions. We present SpiderLS, which extends prior approach by leveraging full ZX reduction. To translate the resulting diagram into executable lattice surgery operations, SpiderLS applies a sequence of compiler passes that derives an execution order, generates target code by grouping compatible interactions into multi-target operations, and lowers the target code to Pauli-product measurements. The resulting explicit patch and Pauli-boundary requirements guide logical scheduling and structure-aware spacetime routing. Across representative algorithmic and random workloads, SpiderLS achieves average reductions of 49.2% in spacetime volume and 99.8% in compilation time compared with the prior ZX-based compiler.