Fault-tolerant compilation (Clifford+T pipeline)

What it fills

• Compile a circuit to a specific device

  Turn a circuit written as arbitrary unitaries over abstract qubits into an executable instruction sequence for one machine's own gate set and connectivity graph. The result is functionally equivalent, or equivalent to within a stated approximation error.

When it applies

Applies when the target is a surface-code architecture. The compiler does not merely sit on top of error correction: it chooses the code distance and the patch layout, which is why that layer sits beneath this route as a step rather than as a precondition. The cost model inverts relative to pre-fault-tolerant compilation: Clifford gates are cheap or free because they can be commuted into the Pauli frame, and T and Toffoli gates dominate. Routing in the SWAP sense is replaced by lattice-level layout and ancilla-bus scheduling.

Requires

These do not move the route along. The method needs each of them alongside its own work, and the cost of getting them is part of what the method costs.

• Build logical qubits at a target logical error rate

  Encode physical qubits whose error rate $p$ sits below a code- and decoder-specific threshold into logical qubits meeting a target logical error rate per round, by spending qubits and time on redundancy and decoding syndromes in real time. Which code sits underneath reaches the layers above only as a physical-qubit count and a demand on connectivity.

  What the schedule asks of the code is a supply of tiles: at code distance $d$, "each tile corresponds to $d^2$ physical data qubits", and one step of the compiled schedule "roughly corresponds to $d$ code cycles". Its Pauli product measurements are executed as two-patch and multi-patch lattice surgery, which "both require $d$ code cycles to account for measurement errors", so every duration is a multiple of $d$. Litinski fixes $d$ from the computation's own operation count: for 164 logical qubits, $10^8$ $T$ gates and physical error rate $p = 10^{-4}$, the condition $164 \cdot 11 \cdot 10^8 \cdot d \cdot p_L(10^{-4},d) < 0.01$ rejects $d = 11$ at a 19.8% final error and settles on $d = 13$ at 0.2%. approximation: $p_L(p,d) = 0.1(100p)^{(d+1)/2}$ is an approximation "for circuit-level noise", taken from Fowler and Gidney. assumption: that 1% is only half the budget — it bounds a logical error on any of the 164 patches, while a separate 1% on the $T$ gates is met by the distillation protocol, for "a 2% chance that the quantum computation will yield a wrong result".

  approximationassumption

Example

given  a circuit, and a surface-code architecture as the target

decompose to Clifford+T

approximate every continuous rotation by a discrete gate word
    # hand the discrete synthesis to the layer below

optimize for T-count and T-depth
    # the cost model inverts relative to pre-fault-tolerant compilation:
    # Clifford gates are cheap or free because they can be commuted into
    # the Pauli frame, and T and Toffoli gates dominate

choose the code distance and the patch layout
    # the compiler does not merely sit on top of error correction, which is
    # why that layer sits beneath this route as a step rather than as a
    # precondition -- hand the chosen distance and layout to it

express the result as a schedule of logical operations on encoded patches
    # typically Pauli-product measurements under lattice surgery
    # routing in the SWAP sense does not appear in this pipeline: it is
    # replaced by lattice-level layout and ancilla-bus scheduling

return that schedule

# costed in T-count, T-depth, logical qubit count and lattice area rather
# than gate count

# Litinski's worked tradeoff, transcribed as the record states it: at
# p = 1e-4 with a 1 microsecond code cycle, a 100-logical-qubit computation
# with T-count 1e8 and T-depth 1e6 runs in
#     4 hours     using          55,000 qubits
#     22 minutes  using         120,000 qubits
#     1 second    using     330,000,000 qubits

Cost, as the source states it

Costed in T-count, T-depth, logical qubit count and lattice area rather than gate count. Litinski's worked tradeoff: at $p = 1e-4$ with a 1 μs code cycle, a 100-logical-qubit computation with T-count 1e8 and T-depth 1e6 runs in 4 hours using 55,000 qubits, in 22 minutes using 120,000 qubits, or in 1 second using 330,000,000 qubits.

Implementations

• Qualtran's surface-code physical cost model (`qualtran.surface_code`)

  • Expressing and Analyzing Quantum Algorithms with Qualtran

  Qualtran devotes its own Section VII to exactly the step this method names: turning architecture-agnostic logical costs into a surface-code physical estimate. Its abstract states the handoff directly — "Architecture-independent resource counts output by Qualtran can be forwarded to our implementation of cost models to estimate physical costs like wall-clock time and number of physical qubits assuming a surface-code architecture" — and names two pre-built pipelines: "we provide the gidney_fowler model based on Gidney and Fowler (2019) and related works; as well as the beverland model based on Beverland et. al. (2023), which takes heavy inspiration from Litinski (2019)" — the same Litinski and Fowler-Gidney papers this method's own citations list.

  A `PhysicalCostModel` (`qualtran/surface_code/physical_cost_model.py`) combines four components the paper names directly: `PhysicalParameters` (physical error rate and code-cycle time), `DataBlock` (how algorithm qubits are laid out in tiles), `MagicStateFactory` (how T/CCZ magic states are produced), and `QECScheme` (the logical-error-rate formula) — matching the paper's own division: "the execution protocol's description is further factored into the data block design for storing algorithm qubits, the magic state factory construction for executing gates, and the error suppression ability of the code." Two classmethods assemble complete pipelines: `PhysicalCostModel.make_gidney_fowler` pairs a `SimpleDataBlock` with a `CCZ2TFactory` and `QECScheme.make_gidney_fowler()`; `PhysicalCostModel.make_beverland_et_al` instead selects one of three data-block layouts by name — `CompactDataBlock`, `IntermediateDataBlock`, `FastDataBlock` — whose docstrings credit them respectively to "[A Game of Surface Codes], Litinski (2019). Page 7, figure 9" and "Page 9, figure 13a" / "Page 9, figure 13b", i.e. the same space-time tradeoff this method's own `error-correction` hop describes as tiles and code cycles. `QECScheme.make_gidney_fowler` sets `error_rate_scaler=0.1, error_rate_threshold=0.01` in the class's own formula $p_l(d) = a\,(p/p^*)^{(d+1)/2}$, so its `logical_error_rate(d, p)` reduces to $p_l(p,d) = 0.1\,(100p)^{(d+1)/2}$ — algebraically the same $p_L(p,d)$ this method's `error-correction` hop attributes to Fowler and Gidney — and the class's own docstring cites the identical source: "Low overhead quantum computation using lattice surgery. Fowler and Gidney (2018)... See section XV for introduction of this formula." A separate `beverland_et_al_model.py` implements the rotation-synthesis and code-distance search of Beverland et al.'s Equations D3/D4, calling a `RotationCostModel` for T-gate counts and `FastDataBlock.get_n_tiles` for the tile count entering the code-distance search.

  Verified directly against `github.com/quantumlib/Qualtran` on the `main` branch: `qualtran/surface_code/physical_cost_model.py` (class `PhysicalCostModel`), `data_block.py` (`DataBlock`, `SimpleDataBlock`, `CompactDataBlock`, `IntermediateDataBlock`, `FastDataBlock`), `qec_scheme.py` (`QECScheme`, `LogicalErrorModel`), `magic_state_factory.py` (`MagicStateFactory`), `ccz2t_factory.py` (`CCZ2TFactory`), `gidney_fowler_model.py` (`get_ccz2t_costs`, `get_ccz2t_costs_from_error_budget`, `get_ccz2t_costs_from_grid_search`), `beverland_et_al_model.py` (`minimum_time_steps`, `code_distance`, `t_states`), and `physical_parameters.py` (`PhysicalParameters`, whose `make_beverland_et_al` classmethod takes a `qubit_modality` of "superconducting", "ion", or "majorana").

• The Lattice Surgery Compiler (latticesurgery-com): a two-stage Clifford+T-to-lattice-surgery pipeline

  • A High Performance Compiler for Very Large Scale Surface Code Computations

  This is the pipeline this method's own pseudocode names, built end to end and run at scale. The paper's abstract states the target directly: "We present the first high performance compiler for very large scale quantum error correction: it translates an arbitrary quantum circuit to surface code operations based on lattice surgery." It reuses Litinski's own time-structuring concept by name: a "slice" is "a temporally discretized partition of the computation (clock timesteps in Litinski [31]... terminology, for example)" — the same Litinski paper this method cites.

  The pipeline has two stages joined by an intermediate representation the paper calls logical lattice instructions (LLI): "The two stages communicate through an intermediate representation we refer to as logical lattice instructions (LLI)... The LLI contains all the information about the logical operations happening on the lattice, but none about the physical locations of the patches." Stage one ("gate level processing") parses a restricted OpenQASM 2.0 circuit with "Qiskit, PyZX, a custom parser or a combination of the three", then reduces controlled gates to CNOTs and single-qubit rotations and approximates single-qubit rotations smaller than $\pi/4$ to Clifford+T gates. Separately, the small-angle $Z(\theta)$ rotations produced by decomposing controlled-rotation gates are approximated to Clifford+T by "the Gridsynth package" — the same Ross-Selinger implementation this capability's own `ross-selinger-synthesis` record documents — after which a `T` gate is applied as a $Z(\pi/8)$ Pauli rotation, matching this method's own theory. An alternative "Pauli rotation compression" mode instead reinterprets a whole Gridsynth output word as a sequence of Pauli-product rotations of varying angle. Stage two ("the slicer") combines LLI with a hand-written layout specification and produces a sequence of "slices", each "a snapshot of the... LLIs that are happening simultaneously on the lattice"; two slicer implementations exist, "one written in Python, geared towards the verification of small scale circuits... and a high performance one written in C++ for large scale circuits", the C++ one placing routing and distillation regions with an in-place implementation of Dijkstra's algorithm plus a cached-routes optimization. A separate resource-estimation module, built on "the Qentiana... software", computes the code distance a random circuit needs for a target success rate.

  The headline benchmark is a synthetic circuit, not experimental data: a 128-qubit Quantum Fourier Transform expressed over Clifford+T, chosen because "the fault-tolerant implementation of the QFT is challenging because of the presence of small angle controlled rotations", with Gridsynth's precision set to $10^{-41}$. The separate resource-estimation figure sweeps "random H, T and CNOT circuits" over circuit width and depth.

  Two repositories under `github.com/latticesurgery-com`: `lattice-surgery-compiler` (Python; QASM front end, the on-the-fly verified slicer, and a web API, default branch `dev`) and `liblsqecc` (C++; GitHub's own description reads "A C++ Library implementing some tools for the Lattice Surgery Compiler", default branch `main`) — this is the high-performance slicer the paper benchmarks. Verified directly against both repositories: `liblsqecc/include/lsqecc/` holds separate directories named `ls_instructions`, `pauli_rotations`, `layout`, `scheduler`, `pipelines`, `patches`, `dag` and `gates`, matching the paper's own division of the pipeline into gate-level processing, an LLI intermediate representation, and layout/routing. The Python repository's README credits the same Litinski paper this method cites, for "the idea of using Pauli rotations as an intermediate representation to get to abstract lattice surgery instructions and to remove stabilizer operations"; `liblsqecc`'s own README independently cites the same paper for its default layout generator, described in its `--layoutgenerator` option as: "compact (default): Uses Litinski's Game of Surface Code compact layout (https://arxiv.org/abs/1808.02892)".

  "We compiled within seconds 80 million logical surface code instructions, corresponding to a high precision Clifford+T implementation of the 128-qubit Quantum Fourier Transform (QFT)." More precisely: "at 128 qubits and after small angle rotation approximation, the QFT circuit has more than 80 Million LLI without gate to Pauli compression", and using the C++ slicer, "laying out the slices for the roughly 80 million LLI of the 128-qubit QFT takes less than 15 minutes on an ordinary laptop", with LLI generation itself taking "negligible time (under 10s on a laptop)". The authors call this "the largest-scale compilation of this kind" to their knowledge. The separate resource-estimation experiment (Figure 9) reports only a heatmap, with no tabulated values: "The vertical axis shows the code distance required to execute the desired circuit with a success rate of 99%. The colour scale represents the space-time volume of the computation, which relates closely with code distance."

What it needs

1. Approximate a continuous rotation in a discrete gate set 2 methods

   Given a target single-qubit unitary — typically a z-rotation by an arbitrary angle — and a precision $\varepsilon$, produce a finite word over a fixed discrete gate set such as Clifford+T whose product is within $\varepsilon$ of the target in a stated metric. The cost is charged in non-Clifford gates.

Other ways to fill the same slot

Different approaches

• NISQ transpilation (retargetable pass pipeline)

  A pass pipeline that decomposes to the device's own two-qubit gate, routes onto the coupling graph, and optimizes for two-qubit gate count and depth. Arbitrary-angle single-qubit rotations are emitted directly, because the hardware executes them.

In the Atlas

No record in the Atlas covers this yet. The catalogue is circuits and primitives; this part of the literature is not in it.

Sources

• A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery↗Daniel Litinski · 2018theory yes · simulation ? · hardware no
• Low overhead quantum computation using lattice surgery↗Austin G. Fowler, Craig Gidney · 2018theory yes · simulation ? · hardware no