Flow-Based Lattice Surgery Optimization with Runtime T Gate Scheduling

AI summary

Overview

Research area: Quantum computing — fault-tolerant quantum compilation for surface codes, specifically lattice surgery and magic state cultivation.

Technical level: Advanced. The paper assumes familiarity with surface code patches, lattice surgery merge-split operations, ZX calculus, pipe diagrams, and network flow algorithms.

Scope: FlowRouter is a lattice surgery compiler that unifies Clifford-gate routing and stochastic magic state cultivation into a single 3D topological pipe diagram, using a maximum-flow formulation at compile time and delay-based scheduling at runtime.

What This Paper Is About

Compiling a logical circuit into lattice surgery operations determines how much hardware footprint and time a fault-tolerant computation costs. Existing compilers route one gate at a time within a layer, so the result depends on gate ordering, and they assume magic states (needed for T gates) are always available and free — an assumption that magic state cultivation has made obsolete, since cultivation happens inside idle patches and takes a stochastic amount of time. The paper's goal is a compiler that routes many gates simultaneously and treats magic state preparation and Clifford routing as one shared allocation problem over the same idle patches.

Key Contributions

1. First unified 3D embedding. FlowRouter is presented as the first topological lattice surgery compiler to place Clifford routing and magic state cultivation inside the same 3D pipe diagram, rather than treating magic states as an external, free resource.

2. Layer-level maximum-flow routing. The routing of an entire circuit layer is formulated as a maximum-flow problem, embedding many gates simultaneously. This removes the dependence on gate ordering that sequential, gate-by-gate routers suffer from, and the paper argues it remains fast and scalable to large qubit counts.

3. Low-latency runtime scheduling for stochastic cultivation. FlowRouter allows cultivation in every idle patch, supports in-patch multiplexing and multi-stage post-selection, and absorbs the stochastic completion time with three delay mechanisms (commutative, fractional, full-cube) applied in order of increasing cost.

4. Evaluation across two cost settings. Benchmarks are compiled under a free-magic setting and a cultivation-aware setting that charges both Clifford routing and magic state cultivation.

Main Findings

• Free-magic setting: FlowRouter reduces spacetime volume by 2.3× and compiles 10.8× faster than the state-of-the-art static topological lattice surgery compiler (Zhou et al., 2026).

• Cultivation-aware setting: FlowRouter reduces spacetime volume by 2.3× on a distance-13 surface code compared with the state-of-the-art runtime compiler that models cultivation (Hofmeyr et al., 2025).

• Joint vs. sequential routing (d = 11): Compared with the better-performing sequential baseline on each benchmark, the maximum-flow kernel reduces spacetime volume by 23% on average and reduces circuit infidelity by 16%. The comparison covers kernel, greedy, and random embeddings of each layer; the random embedding was repeated five times while the other two were run once.

• Cultivation parameters: For d₂ ∈ {11, 13}, d₁ = 3 with a suitable complementary gap threshold G_T already meets the target error rate, so d₁ = 3 is preferred over d₁ = 5 because fewer post-selected checks mean lower expected preparation time. For d = 15, d₁ = 5 is required to bring the logical error rate down to surface-code levels.

• Expected cultivation runtimes (Table 1): d₁ = 3, d₂ = 11 gives E(C_t) = 23.2 code cycles (2.1 logical cycles); d₁ = 3, d₂ = 13 gives 26.4 code cycles (2.0 logical cycles); d₁ = 5, d₂ = 15 gives 82.5 code cycles (5.5 logical cycles).

• Runtime budget: The full delay-and-route simulation runs classically on the CPU and completes within the 15 μs budget at d = 15.

• Not reported in the supplied text: The paper content is truncated inside the Evaluation section, so the full benchmark table, per-benchmark volumes, the complete benchmark list, and the exact hardware/software platform figures are not available here. Benchmarks are sourced from MQT-Bench, FTCircuitBench, and TopoLS, with a compilation time cutoff of 4 hours, but individual circuit results beyond the d = 11 experiment are not given in the provided content.

Methodology in Plain English

Compile time — routing the Clifford part. The circuit, written in the gate set {H, S, CX, T}, is converted into a ZX diagram. The only ZX rewrite applied is spider fusion, which merges adjacent same-type spiders to increase parallelism; the authors deliberately restrict themselves to this rule to keep compilation fast. The diagram is then cut into vertical layers, and layers are processed front to back.

For each front layer, the compiler asks: within a thin time window, what is the largest set of valid, non-overlapping pipe routes that can connect the required junctions? Because gates in a layer commute, the compiler is free to choose which columns act as sources and which as sinks — this is what turns a hard multi-commodity routing problem into a solvable single-commodity maximum-flow problem, solved with repeated calls to Dinic's algorithm.

Not every flow path is a legal CX, so the compiler alternates between generating candidate paths and repairing them (inserting vertical detours at xy-junctions), committing paths in order of increasing endpoint height and stopping after three iterations. A first window three cubes tall produces a baseline routing; the compiler then extends the window downward in halving steps, accepting a trial if it places at least half as many CXs as the baseline. If a window places nothing, the search space shrinks (halving the eligible endpoint pool down to a floor of two qubit columns) and then advances one block in time.

Initial mapping. Logical qubits are assigned to fixed data patches on a sparse layout before execution and never moved. The mapping minimizes a weighted sum of Manhattan distances between interacting qubits, relaxed to a squared Euclidean objective, which is solved by the eigenvectors of the two smallest nonzero eigenvalues of the interaction graph's Laplacian. The relaxed coordinates are snapped to legal odd-integer patch sites via a linear assignment problem solved with the Hungarian algorithm in O(|V|³), then refined by a local search over all O(n²) pairwise swaps until no swap improves the objective.

Runtime — scheduling the T gates. Cultivation starts at the bottom of the pipe diagram in every empty region, with four attempts multiplexed in corner-localized regions of a single patch; survivors of injection and cultivation are forwarded to one shared escape stage. Completion times are modeled by running Markov chain Monte Carlo simulations under the SI1000 noise model, computing the expected cultivation time, fitting an exponential distribution, and drawing completion times from it. Ten microseconds (10 cycles at a 1 μs cycle time) is allocated for the complementary gap computation.

A "backup T injection cube" is reserved next to each T gate so a state can always reach it. When execution reaches a T gate, either a state is ready a cycle early and is routed by breadth-first search, or a delay is applied. The three delay mechanisms are tried in order of increasing cost: commutative (slide the T gate past idling cubes, S gates, or the control cube of a CX, adding no volume), fractional (defer by one syndrome-extraction round at a time, up to k ≤ d−1 rounds, buying time but not new routing space), and full-cube (defer by a whole cube, opening new routing space as well as time). After each increment the compiler re-checks readiness and routability, then routes the state and runs a second breadth-first search to place machinery for the conditional S correction.

Correctness checking. For the Clifford part, correlation surfaces generated by TQEC's find_correlation_surfaces are compared against an independently derived generating set built with Qiskit's evolve; both are reduced to row-reduced echelon form as 2N_q × 4N_q binary matrices and checked for equality. The check is up to Pauli sign, which the authors argue is a complete notion of correctness since any sign discrepancy is a correctable global Pauli byproduct. T gates cannot be verified this way, so each is asserted by confirming that the prepared T state is injected at a Z-type (blue) junction on the correct data qubit.

Why This Matters

Impact on research. The paper reframes lattice surgery compilation as a flow problem over a whole layer rather than a sequence of greedy path commitments, borrowing directly from a transition classical VLSI routing made decades ago. It also closes a gap between compilation and hardware reality: as cultivation replaces distillation, magic states are prepared inside the computation's own idle patches, so treating them as free perimeter resources is no longer accurate. Charging both Clifford routing and cultivation in one cost model makes reported spacetime volumes more comparable to what a machine would actually pay.

Real-world applications (general, since the paper does not evaluate specific end-use algorithms beyond its benchmark suite):

• Resource estimation for fault-tolerant implementations of quantum chemistry and optimization algorithms.
• Compiler backends for superconducting and spin-qubit hardware, where limited connectivity makes lattice surgery the natural instruction set.
• Scheduling layers for neutral-atom and other platforms that have demonstrated surface-code experiments.
• Toolchain integration with open-source surface-code tooling such as TQEC.

Industry relevance. Compilation determines qubit count and wall-clock runtime, the two quantities that decide whether a fault-tolerant machine can run a given application at all. A 2.3× volume reduction and 10.8× faster compile time directly loosen both budgets and shorten design iteration for hardware teams building surface-code processors.

Future Directions

• Richer ZX optimization. The authors restrict rewriting to spider fusion to control compile time and state that more sophisticated ZX rewrite rules could further reduce spacetime cost at substantially higher computational expense — an explicit invitation to explore that trade-off.
• Beyond two-local layers. The maximum-flow formulation depends on each multi-qubit operation being two-local; extending the approach to weight-k Pauli rotations, which currently reduce to Steiner-tree problems, is an open question.
• Correlation surfaces for T gates. The current verification certifies Clifford propagation only; T gates are checked by a structural assertion about the injection junction rather than by a surface-based proof, leaving a stronger correctness certificate open.
• Tighter cultivation modeling. The scheduling model draws completion times from an exponential fit to simulated expected cultivation time; validating against measured hardware stochasticity and refining the delay heuristics would test how much the ordering of commutative, fractional, and full-cube delays matters in practice.

Target Audience

Researchers and engineers working on fault-tolerant quantum computing: compiler developers for surface codes and lattice surgery, resource-estimation practitioners, and hardware teams planning surface-code architectures with in-place magic state cultivation. It is most useful to readers already comfortable with patch-based lattice surgery, pipe diagrams, and ZX calculus; readers new to these topics will need the background section and its cited references first.

Authors’ abstract

Lattice surgery on the surface code is a leading route to fault-tolerant quantum computation. Compiling logical circuits into lattice surgery operations is a pivotal step that determines the resource cost of a computation. Prior compilers build on idealized assumptions, and one that works in practical settings remains to be developed. Existing works are either unscalable or route one gate at a time within a layer, so the embedding depends on the order of gates and opportunities to route many gates at once are lost. In addition, they assume magic states are always available and cost-free, even though preparing one costs more than a Clifford operation. We present FlowRouter, the first topological lattice surgery compiler that places Clifford routing and stochastic magic state cultivation inside a single 3D embedding. At compile time, FlowRouter formulates the routing of an entire circuit layer as a maximum-flow problem, embedding many gates simultaneously. At runtime, it allows magic states to be cultivated at every idling patch, works with the realistic cultivation process with multiplexing and multi-stage post-selections, and absorbs the stochasticity by introducing delay mechanisms that add as little spacetime volume as possible. With magic states assumed free, FlowRouter reduces spacetime volume by 2.3x and compiles 10.8x faster than the state-of-the-art static topological lattice surgery compiler. With the cultivation-aware setting that includes both Clifford and magic state cost, FlowRouter reduces spacetime volume by 2.3x on a distance-13 surface code when compared with the state-of-the-art runtime compiler.