RushHour: A Dynamically Reconfigurable Lattice-Surgery Architecture

AI summary

Overview

Research area: Quantum physics and quantum computing, specifically fault-tolerant quantum computing (FTQC) architecture, surface-code lattice surgery, and quantum compilation.

Technical level: Advanced. The paper assumes familiarity with surface codes, lattice surgery, and compiler design, though the core ideas can be understood at a conceptual level.

Scope: The paper presents RushHour, a hardware–compiler co-designed architecture that makes the lattice-surgery ancilla space a dynamic, runtime-managed resource rather than a statically pre-allocated one, and evaluates it against six state-of-the-art compilers and two resource models on 35 benchmarks.

What This Paper Is About

Fault-tolerant quantum computers built on the surface code need lattice surgery to perform logical gates, and the amount and arrangement of ancilla space around data qubits determines whether a program fits on a chip and how fast it runs. Existing lattice-surgery architectures fix qubits, routing space, and resource states before execution, which makes them unable to run on small chips and forces a rigid choice between space efficiency and time efficiency. RushHour's goal is a single architecture that reconfigures the lattice during execution, so a few ancilla tiles can be reused across operations and additional chip area can be converted into parallelism on demand.

Key Contributions

1. Dynamic lattice surgery as an execution model. The lattice becomes mutable machine state: a staircase-shaped ancilla corridor is described by two interlocking arrays, any valid configuration is one round of parallel patch slides away from any other, resource states are allocated just in time, and qubit orientations become a tracked property rather than a fixed layout decision.

2. The RushHour ISA and the Lattice Management Unit (LMU). The ISA formalizes legal configurations, transitions, and gate realizations as a compilation target, with instruction costs given in logical rounds (for example, a reconfiguration costs 1 round, a rotation 3 rounds, a standard CX 2 rounds, a teleported CX 1 round). The LMU abstracts lattice management through four functions (alloc, try_access, reshape, commit) and includes a corridor solver that finds a valid corridor for a requested set of ancilla demands in O(n+m) time.

3. The RushHour compiler. It schedules gates, reconfigurations, and state preparations while pipelining their overhead off the critical path, using three placement strategies (locality-first, density-first, spreading) and a candidate sweep that prices region and placement choices at every code distance the chip affords and returns Pareto-dominant operating points.

4. A full implementation and comparative evaluation. RushHour is implemented in approximately 9,300 lines of Rust and evaluated on 35 Clifford+T circuits from FTCircuitBench and MQT Bench at 12–100 qubits and up to 186k T gates, against LSQCA, DASCOT, liblsqecc, O3LS, PureMagic, and TACO, plus the FLASQ bound and Litinski's analytic model.

Main Findings

• Small-chip feasibility: At RushHour's minimum feasible chip, 86% of benchmarks run only with RushHour, while existing approaches require 1.2–3.5× larger chips.

• Speed on space-constrained chips: On space-constrained early-FTQC chips, RushHour runs a median 2.3–7.2× faster than the best feasible alternative, and reaches a successful shot up to a median 7.2× sooner than the best feasible alternative.

• Advantage at 2× the physical minimum: At twice the physical minimum chip size, RushHour delivers the outright best result on 94% of benchmarks.

• Parity on large chips: RushHour matches the state of the art on very large chips.

• Total space–time cost: In total space–time resource cost, RushHour runs 2.8–13× cheaper than every design except the spacious-chips-only PureMagic, with which it is on par.

• Gap to an idealized limit: RushHour's constructive results run 4.8× from an idealized-machine resource limit.

• The cost of static density: The paper reports that the densest existing approach uses 1.1 tiles per qubit but runs a median 24× slower than the fastest approach, which in turn requires over 3× the space, illustrating that prior designs each occupy only a small, suboptimal region of the space–time trade-off.

• Robustness to the walking-qubit rate: The evaluation assumes one patch width per logical round, while a two-round schedule is the established rate; re-reporting every aggregate at the two-round rate moves no result by more than 2.2%.

• Table-level comparison: A reported comparison table lists baseline gaps relative to RushHour across minimum chip size, T_succ, qubit count, logical volume, qubit-seconds, and distance to the FLASQ bound — for example, liblsqecc at 55.0× bound gap, LSQCA at 40.2×, O3LS at 31.1×, TACO at 13.7×, and Litinski at 13.1×, with PureMagic shown as the exception that is cheap in total cost because it assumes spacious chips.

Methodology in Plain English

The authors start from the observation that static lattice-surgery layouts must reserve ancilla space up front so that any future gate remains routable, which wastes area and forces serialization. They instead arrange the free ancilla tiles as a single connected "staircase corridor" winding between data patches, described by two interlocking index arrays. Because every patch is displaced by at most one tile from its home position, any legal corridor shape can be converted into any other by sliding each patch at most one tile in a single round. That makes reconfiguration both fast and rare.

They then define an instruction set in which configurations, reconfigurations, allocations, and gate realizations are explicit machine state and operations, with each instruction priced in logical rounds. A hardware-style unit, the LMU, sits between the compiler and the lattice. Its access engine searches for ways to realize a ready gate on the current lattice; if a gate cannot be realized, its reconfiguration engine pins the required ancilla positions, solves for a complete valid corridor, greedily batches other blocked gates into the same reshape, and emits one reconfiguration instruction.

The compiler runs a scheduling loop over a frontier of ready gates ordered by criticality, commits the earliest-finishing realization, and reshapes only when nothing in the frontier can be served. Because instructions begin as soon as their tiles are free, independent operations overlap automatically. Around this loop, a sweep enumerates candidate data-region shapes and placements, compiles each once per magic-state cultivation occupancy class, prices each compiled stream at every code distance the chip allows under the FLASQ cost model, and keeps the Pareto-dominant feasible points. Speedups are then measured as time to a successful shot, accounting for logical error budgets and magic-state cultivation costs.

Why This Matters

Impact on research: The paper reframes lattice surgery layout from a static floor-planning problem into a runtime management problem, and provides a concrete ISA and microarchitecture (the LMU) that other compilers can target. It also supplies a direct comparison across six existing compilers and two analytic resource models under a shared cost model, which is useful for calibrating future architecture proposals.

Potential real-world applications (as implications of the work, not demonstrations reported in the paper):

• Planning early fault-tolerant superconducting devices, where physical qubit counts are the binding constraint and circuits must fit on small chips.
• Compiler toolchains for surface-code hardware that need to trade area for runtime automatically per device.
• Resource estimation for large algorithms such as quantum chemistry and materials simulation, where both qubit counts and logical runtime determine feasibility.
• Scheduling and control-stack design for quantum hardware, since the LMU resembles a hardware controller that reconfigures patch positions between rounds.

Industry relevance: The results target the regime where fault-tolerant machines are just becoming available and are severely space-constrained. A 1.2–3.5× reduction in required chip size and median 2.3–7.2× faster execution on constrained chips directly affect how large an algorithm a given device can run, which is relevant to hardware vendors, compiler teams, and groups deciding what device sizes are worth building.

Future Directions

• Hardware validation of one-round walking: The one-patch-width-per-round slide is assumed throughout and is described as conjectured but not yet demonstrated as a fault-tolerant protocol; experimental demonstration would remove the need for the two-round sensitivity arm.
• Extending beyond Clifford+T and the surface code: The ISA and lattice model are defined for surface-code patches and Clifford+T circuits; whether the corridor abstraction generalizes to other codes or to richer instruction sets is open.
• Scaling the compiler and search: Compilation is cheap per candidate, but the sweep over regions, placements, code distances, and cultivation occupancy classes grows with chip size and circuit size, leaving room for smarter pruning or learned search.
• Co-designing the LMU with real control electronics: The LMU is presented as an architectural abstraction with efficient solvers; how it maps onto actual cryogenic or room-temperature control hardware and real-time decoding is not reported.

Target Audience

This paper is most valuable to researchers and engineers working on fault-tolerant quantum architectures, surface-code compilers, and quantum resource estimation, as well as hardware teams designing early fault-tolerant devices under tight qubit budgets. It is also relevant to graduate students and advanced practitioners who already understand lattice surgery and want to see how dynamic lattice management changes the space–time trade-off; readers new to surface codes will need the background sections or external references to follow the technical detail.

Authors’ abstract

Practical fault-tolerant quantum computing (FTQC) requires efficient lattice surgery (LS), so that large algorithms fit on resource-constrained quantum chips. Existing approaches, however, are rigid: qubits, routing space, and resource states are allocated ahead of execution, which prevents running on small chips, leaves statically scheduled executions with large time overheads, and fixes each design at a single area of the space-time trade-off. We present dynamic LS, which enables efficient reconfiguration of the ancilla space, just-in-time allocation of resource states, and dynamic rotations of logical qubits, thereby spanning the entire space-time trade-off with a single, unified approach. We realize dynamic LS with RushHour through a hardware-compiler co-design: the RushHour ISA formalizes and programs our dynamic lattice model, the Lattice Management Unit abstracts dynamic lattice management and performs efficient lattice reconfiguration, and the RushHour Compiler compiles logical circuits for physical chips into optimized ISA programs while pipelining instructions. We evaluate RushHour against six state-of-the-art compilers and two resource models. On the smallest chips, 86% of benchmarks run only with RushHour, while existing approaches require 1.2-3.5$\times$ larger chips. On space-constrained early-FTQC chips, RushHour runs a median 2.3-7.2$\times$ faster than the best feasible alternative, while achieving results comparable to the state of the art on very large chips. RushHour's constructive results run 4.8$\times$ from an idealized-machine resource limit.