arXiv:2609.23756
Flow-Based Lattice Surgery Optimization with Runtime T Gate Scheduling
Raymond Iacobacci, Tianyi Hao, Neer Patel, Siyuan Niu
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.
AI Summary
Lattice-surgery compilation must allocate spacetime to both logical routing and stochastic magic-state preparation. FlowRouter addresses this using a three-dimensional pipe-diagram compiler with offline Clifford routing and online scheduling of magic-state cultivation and injection. The compiler translates Clifford+$T$ circuits into ZX diagrams, applies spider fusion, and embeds layers using repeated maximum-flow solves. Candidate routes undergo legality checks and heuristic repairs; the procedure is not an exact volume optimizer. Initial placement combines spectral embedding, assignment, and local swaps. At runtime, idle patches cultivate magic states with in-patch multiplexing. Unavailable or unreachable states trigger commutation-based, fractional-cycle, or full-cube delays. On 19 benchmark circuits, assuming free boundary-supplied magic states, FlowRouter achieves geometric-mean bounding-volume reductions of $2.3\times$ versus TopoLS, $2.1\times$ versus PureMagic, and $2.0\times$ versus DASCOT. Compilation is $10.8\times$ faster than TopoLS on mutually completed benchmarks, but slower than DASCOT. Cultivation-aware simulations on 12 circuits reduce volume versus PureMagic by $2.2\times$, $2.3\times$, and $1.6\times$ at distances $11$, $13$, and $15$, respectively. The active-volume-based infidelity estimate improves by 12–16% at the lower distances but worsens by 8% at distance 15. Evaluation uses a four-hour compilation cutoff and sampled cultivation times from an exponential distribution fitted to modeled mean latency. Longer cultivation at distance 15 reduces the advantage because delays propagate through the 3D embedding. Correctness checks certify Clifford propagation up to Pauli signs; $T$-gate checks are local structural assertions. Explicitly shaping Clifford routing around cultivation demand remains future work.
Central claim may not hold: The claimed exact whole-layer routing reduction is implemented through flow generation, repair, rejection, and restricted searches without a proof of optimality for legal routes. The cultivation evaluation samples an exponential completion-time surrogate, which does not establish preservation of the multistage protocol's readiness and interruption statistics. The stated single-commodity flow construction does not preserve prescribed CX operand pairings, leaving its central correctness claim unsupported.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.