⚛️ quantum physics

SpiderLS: Leveraging Full ZX Reduction for Lattice Surgery Compilation

SpiderLS is a novel lattice surgery compiler that leverages full ZX-diagram reduction and a multi-stage translation pipeline to achieve significant reductions in spacetime volume and compilation time compared to prior ZX-based approaches.

Original authors: Hyungseok Kim, Changheon Lee, Seungjik Kim, Enhyeok Jang, Youngmin Kim, Seungwoo Choi, Hanbit Lee, Sungho Pyun, Won Woo Ro

Published 2026-09-01

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Hyungseok Kim, Changheon Lee, Seungjik Kim, Enhyeok Jang, Youngmin Kim, Seungwoo Choi, Hanbit Lee, Sungho Pyun, Won Woo Ro

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Quantum computers promise to solve problems that are impossible for today's machines, but they are incredibly fragile. To work reliably, they must be shielded from the slightest disturbance, a challenge met by a method called quantum error correction. Imagine a single piece of information spread out across a vast grid of physical components, where the system constantly checks itself to ensure nothing has gone wrong. One of the most promising ways to build this shield is a technique known as the surface code, which arranges these components in a two-dimensional pattern. To perform calculations, this grid must be manipulated in a very specific way: sections of the grid are temporarily merged together and then split apart to exchange information. This process, called lattice surgery, is the practical engine that drives these future machines, but figuring out how to schedule these merges and splits efficiently is a massive computational puzzle. If the schedule is poor, the computer becomes too large and slow to be useful.

A team of researchers at Yonsei University in Seoul has developed a new tool called SpiderLS to solve this scheduling puzzle. Their work addresses a bottleneck in how scientists translate complex quantum programs into the physical instructions needed for these error-corrected grids. Previously, compilers that handled this translation were forced to be overly cautious. They treated every interaction in a quantum program as a simple, isolated event, refusing to combine operations even when the underlying physics allowed it. This caution was based on a strict rule: a single connection point on the grid could only handle a limited number of links at once. Consequently, the compilers would break down complex tasks into many small, sequential steps, wasting valuable time and space. The researchers realized that this restriction was unnecessary. By looking at the problem through a different mathematical lens, they discovered that the grid could actually handle more complex, multi-way connections simultaneously, provided the connections were routed correctly.

The new system, SpiderLS, works by first translating a quantum program into a simplified diagram that reveals its true structure. Instead of stopping at the first level of simplification, the researchers let the system fully reduce the diagram, exposing hidden opportunities to combine multiple operations into single, larger actions. In the old approach, a computer might have to perform three separate connection steps one after another. The new method identifies that these three steps can be combined into one powerful, multi-part operation. Once these larger operations are identified, the system breaks them down into the specific measurements required by the surface code. It then acts like a traffic controller, assigning these measurements to specific locations on the grid and finding the shortest, conflict-free paths for them to travel. This process ensures that the grid is used as densely as possible without causing collisions that would force the system to wait.

The results of this approach are striking. When tested against the best existing methods, SpiderLS reduced the total amount of space and time required to run quantum programs by nearly half. In many cases, the time needed to compile the instructions was cut by almost 100 percent, meaning the tool could generate instructions almost instantly compared to the minutes or hours required by previous systems. The researchers tested their tool on a wide variety of quantum algorithms, from simple search routines to complex simulations, and found that it consistently produced more compact and efficient schedules. Crucially, this efficiency did not come at the cost of reliability; the system maintained the same level of error protection as before. By allowing the compiler to see the full potential of the grid's capabilities, SpiderLS demonstrates that we can build more powerful quantum computers without needing to build larger physical machines.

Technical Summary of "SpiderLS: Leveraging Full ZX Reduction for Lattice Surgery Compilation"

Problem Statement

Fault-tolerant quantum computing (FTQC) relies heavily on the surface code, where logical operations are implemented via lattice surgery—merging and splitting encoded qubit patches through Pauli-product measurements (PPMs). A critical bottleneck in this paradigm is the compilation of logical circuits into efficient lattice surgery realizations that minimize spacetime cost (the product of spatial area and time steps).

Recent approaches have utilized the ZX-calculus as an intermediate representation (IR) to enable semantics-preserving transformations. However, existing ZX-based compilers, such as TopoLS, restrict ZX reduction to preserve a one-to-one correspondence between ZX spiders and lattice surgery junctions. Due to the planar geometry of logical patches, a single junction supports at most four connections (two spatial, two temporal). Consequently, these compilers cannot perform "full" ZX reduction if it results in spiders with a degree greater than four, even though the underlying lattice surgery model supports higher-arity interactions via multi-patch measurements. This restriction prevents the compiler from exploiting the full optimization potential of the ZX-calculus, leading to suboptimal spacetime volumes and high compilation overhead due to complex embedding searches.

Methodology

The authors propose SpiderLS, a lattice surgery compiler that overcomes the degree-4 constraint by decoupling the ZX spider representation from the physical junction constraint. The compilation pipeline proceeds through four main stages:

Full ZX Reduction and Execution Ordering:
SpiderLS translates the input Clifford+T circuit into a ZX-diagram and applies PyZX's full_reduce() routine. Unlike prior work, this process is not restricted by the four-edge junction limit, allowing the generation of high-degree spiders. The compiler then derives an execution order directly from the reduced graph. It maintains a set of active "frontier" spiders and iteratively extracts executable interactions (CZ operations) and Hadamard moves, effectively linearizing the reduced graph into a sequence of operations.
Target Code Generation:
The execution sequence is grouped into a target program. SpiderLS exploits the observation that multiple CZ gates sharing a common control qubit can be combined into a single multi-target operation (e.g., $CZ^{(k)}(q_c; q_1, \dots, q_k)$ ). Phase operations (S and T gates) are extracted from spider phases, with T gates handled via magic state injection. This stage produces a compact target program consisting of multi-target CZs, single-qubit gates, and Hadamards.
PPM Lowering and Logical Scheduling:
The target program is lowered to a sequence of unit-time PPMs. Crucially, high-arity CZ operations are decomposed into multi-patch measurements (e.g., a 3-target CZ becomes a 4-patch $M_{ZZZX}$ measurement and a standard $M_{ZZ}$ measurement). The compiler then performs logical scheduling, packing these PPMs into logical layers. It employs a strategy to minimize the number of internal ancilla qubits required while preserving the depth of an unbounded ancilla schedule.
Layered Spacetime Routing:
Instead of using Monte Carlo Tree Search (MCTS) to solve the global embedding problem layer-by-layer (as in TopoLS), SpiderLS performs structure-aware local routing. Once the logical schedule is fixed, the compiler routes each PPM by selecting compatible Pauli boundaries and constructing paths using A* search. If a valid route cannot be found within a bounded local search, the operation is deferred to a later physical layer. This "commit-or-defer" strategy avoids the exponential search space of global layer embedding, significantly reducing compilation time.

Key Contributions

Full ZX Reduction for Lattice Surgery: The paper demonstrates that ZX spiders need not map one-to-one to bounded-degree junctions. By leveraging multi-patch measurements, SpiderLS allows full ZX reduction, enabling the consolidation of interactions that were previously fragmented to satisfy junction constraints.
Multi-Target Operation Grouping: The compiler identifies and groups shared-control interactions into single multi-target operations, reducing the total number of logical operations and enabling more efficient spacetime packing.
Structure-Aware Routing: By separating logical scheduling from geometric routing and using bounded local searches rather than global MCTS, SpiderLS achieves a dramatic reduction in compilation complexity.
Implementation and Evaluation: The authors provide a full implementation of SpiderLS and evaluate it against state-of-the-art compilers (Liblsqecc, DASCOT, and TopoLS).

Results

Evaluated across a diverse suite of algorithmic (e.g., Bernstein-Vazirani, QAOA, QFT) and random Clifford+T circuits:

Spacetime Volume: SpiderLS achieves an average reduction of 49.2% in spacetime volume compared to TopoLS. This reduction is primarily driven by a decrease in the number of time steps, achieved through the grouping of interactions and multi-patch measurements.
Compilation Time: SpiderLS reduces compilation time by 99.8% compared to TopoLS. The shift from MCTS-based embedding to bounded local routing eliminates the primary bottleneck in prior ZX-based compilers.
Scalability: SpiderLS maintains low compilation overhead comparable to circuit-based compilers (Liblsqecc, DASCOT) while outperforming them in spacetime efficiency. It scales effectively with circuit width, showing consistent volume reductions as problem sizes increase.
Magic State Demand: Despite compressing the temporal depth, SpiderLS maintains a T-port density comparable to or lower than TopoLS, indicating that the temporal compression does not concentrate magic state demand to an unmanageable degree.

Significance

The paper claims that SpiderLS demonstrates the practical benefits of leveraging the full expressive power of the ZX-calculus for lattice surgery compilation. By relaxing the artificial constraint that ZX spiders must map directly to physical junctions, the compiler can generate more compact spacetime realizations. The work establishes that high-arity interactions, previously considered difficult to map, can be efficiently realized through multi-patch measurements. Furthermore, the proposed structure-aware routing approach proves that high-quality lattice surgery compilation can be achieved without the prohibitive computational cost of global embedding searches, making efficient compilation feasible for larger quantum programs.