PaperlayerView exact revision on arXiv

Source-linked AI summary

A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery

Daniel Litinski

arXiv:1808.02892v3quant-phcond-mat.mes-hall

TL;DR

The paper asks how arbitrary quantum circuits can be executed fault-tolerantly on surface-code architectures with limited overhead. It develops modular patch-based strategies for trading physical-qubit space against computation time, including data blocks, magic-state distillation, and T-layer parallelization. For a 10^8-T-gate, 10^6-layer computation at p=10^-4, the schemes span 4 hours with 55,400 qubits to 1 second with 330 million qubits.

  • Problem

    Executing arbitrary quantum circuits on surface-code computers requires optimizing substantial space and time overheads, and the layout problem is NP-hard.

  • Method

    The paper uses modular surface-code patch schemes, combining data blocks, magic-state distillation blocks, and parallelized T-layer units to expose space-time trade-offs.

  • Results

    For 10^8 T gates over 10^6 T layers at p=10^-4, the schemes achieve 4 hours with 55,400 physical qubits or 1 second with 330 million qubits.

  • Takeaways & Limitations

    Resource estimates require only the input circuit’s T count and T depth, while modular blocks can be optimized independently and distributed across connected quantum computers.

  • Takeaways & Limitations

    For larger computations, classical measurement, feed-forward, and decoding may become significant roadblocks, and higher T counts can make execution impractically long.

Abstract

from arXiv · show

Given a quantum gate circuit, how does one execute it in a fault-tolerant architecture with as little overhead as possible? In this paper, we discuss strategies for surface-code quantum computing on small, intermediate and large scales. They are strategies for space-time trade-offs, going from slow computations using few qubits to fast computations using many qubits. Our schemes are based on surface-code patches, which not only feature a low space cost compared to other surface-code schemes, but are also conceptually simple, simple enough that they can be described as a tile-based game with a small set of rules. Therefore, no knowledge of quantum error correction is necessary to understand the schemes in this paper, but only the concepts of qubits and measurements. As an example, assuming a physical error rate of $10^{-4}$ and a code cycle time of 1 $μ$s, a classically intractable 100-qubit quantum computation with a $T$ count of $10^8$ and a $T$ depth of $10^6$ can be executed in 4 hours using 55,000 qubits, in 22 minutes using 120,000 qubits, or in 1 second using 330,000,000 qubits.

0 Step 1

The tile-based framework manipulates surface-code patches through initialization, measurement, deformation, and movement operations with explicit time costs. These operations implement short protocols and translate to surface-code procedures whose resource costs scale with code distance.

  • 0 Step 1: Patch edges and corners can be moved to enlarge, shrink, or reshape patches, with enlargement and corner movement taking one time step while shrinking is instantaneous.Moving an edge onto a free tile increases patch size; moving it inward costs no time.
  • 0 Step 1: A Bell pair is prepared by initializing two patches in |+⟩ and measuring Z⊗Z, producing a maximally entangled state in one time step.Either measurement outcome yields a maximally entangled Bell state.
  • 0 Step 1: The framework translates to surface-code operations in which each tile represents d^2 physical data qubits and each time step roughly represents d code cycles.Two-patch and multi-patch measurements correspond to lattice surgery and require d code cycles to account for measurement errors.
  • 0 Step 1: For a protocol using s tiles for t time steps, the leading space-time cost is st·d^3, while the space cost is s·d^2 physical data qubits.Exact time costs may require accounting for state injection and classical processing.

Overview

The paper presents modular surface-code strategies for executing arbitrary circuits under an NP-hard layout problem, emphasizing space-time trade-offs across data, distillation, and parallelized T-layer blocks. For a 100-qubit, 10^8-T-gate computation at p=10^-4, the reported designs range from 4 hours with roughly 55,000 qubits to 1 second with 330 million qubits.

  • Overview: Executing an arbitrary circuit as fast as possible on a surface-code computer of fixed size is NP-hard, so the paper focuses on heuristics rather than a general solution.The framework is organized around resource-aware strategies for the input circuit.
  • Overview: The architecture separates a data block, which hosts computation qubits, from a distillation block, which generates magic states consumed by T gates.Computational speed depends on both magic-state distillation and consumption rates.
  • Overview: Compact, intermediate, and fast data blocks trade tile count against magic-state consumption time, using 1.5n+3, 2n+4, and 8n+1 tiles respectively.The fast block consumes a magic state in one time step, while compact and intermediate blocks require up to 9 and 5 time steps.
  • Overview: Up to 90% space-time cost reduction is reported for code-based distillation protocols compared with braiding-based implementations.The protocols use error-correcting codes with transversal T gates, including punctured Reed-Muller and block codes.
  • Overview: Parallelizing T layers trades additional space-time cost for execution approaching one measurement time per T layer and supports distributed computing through Bell-pair sharing.The scheme uses units that repeatedly prepare Bell states, execute post-corrected T layers, and perform Bell-basis measurements.
  • Overview: The framework also considers arbitrary-angle Clifford+ϕ circuits and higher code distances as further space-time trade-offs.These options introduce additional resources or reduce measurement fidelity while potentially speeding computation.

1 Clifford+T quantum circuits

The paper rewrites Clifford+T circuits as Pauli-product rotations and measurements, grouping π/8 rotations into commuting layers characterized by T count and T depth. Magic-state consumption implements these rotations through Pauli-product measurements, with corrections commuted into later operations or final measurements.

  • Clifford+T circuits are expressed using Pauli-product rotations Pϕ, where Clifford gates are π/4 rotations and T gates are π/8 rotations.
  • Clifford gates can be commuted to the circuit end, transforming later rotations and final Z measurements into Pauli-product measurements.
  • T count is the number of π/8 rotations, while T depth denotes the number of layers containing mutually commuting π/8 rotations.
  • A greedy procedure reduces T depth by moving each rotation into the preceding layer when it commutes with every rotation already there.
  • Magic states enable Pπ/8 rotations through a Pauli-product measurement; measurement outcomes may require corrective Pπ/4 or Pauli operations commuted to the circuit end.

2 Data blocks

Data blocks store computation qubits and consume magic states through Pauli product measurements. Compact, intermediate, and fast blocks trade tile count and magic-state consumption time for different computation scales.

  • Data blocks: Data blocks host data qubits and consume magic states via Pauli product measurements, separating computation storage from magic-state distillation.The framework partitions tiles into distillation blocks and data blocks.
  • Compact blocks: 1.5n + 3 tiles store n qubits in a compact block, but square patches make only one Pauli operator accessible at a time.Patch rotations and additional π/4 rotations address measurements involving Y operators, with consumption taking up to 9 time steps.
  • Space-time trade-offs: Compact blocks suit small computers when magic-state distillation takes longer than 9 time steps, whereas fast blocks are more favorable at large scale when distillation takes less than 5 time steps.The designs therefore expose a space-time trade-off between tile overhead and magic-state consumption speed.
  • Intermediate blocks: 2n + 4 tiles store n qubits in an intermediate block, whose single-row layout allows patch rotations to occur simultaneously.The intermediate design requires at most 5 time steps per magic state: two for π/4 rotations, two for patch rotations, and one for the Pauli product measurement.
  • Fast blocks: Two-qubit patches provide fast blocks with compact storage and access to all Pauli operators, enabling the standard protocol to consume one magic state every 1 time step.The example fast block stores 18 qubits, while the general layout uses 8n + 1 tiles as stated in the supplied passages.
  • Proof-of-principle device: Undistilled magic states allow a data block to function as a complete quantum computer, including a six-tile proof-of-principle universal two-qubit device.This device demonstrates the operations used in the framework with undistilled magic states.

3 Distillation blocks

The paper develops surface-code magic-state distillation blocks from transversal-T error-correcting codes, emphasizing compact patch implementations and space-time cost. The resulting schemes reduce resource costs relative to braiding-based implementations while exposing trade-offs between output fidelity, success probability, and throughput.

  • Motivation: Magic state distillation converts many low-fidelity magic states into fewer higher-fidelity states using Clifford operations, which are Pauli product measurements in this framework.Distillation is especially important because non-Pauli state initialization is error-prone and the procedure is repeated frequently in large-scale computation.
  • 3.1 15-to-1 distillation: The general construction applies to protocols based on error-correcting codes with transversal T gates, illustrated by 15-to-1 distillation using 15 faulty states to produce one higher-fidelity state.The 15-qubit code encodes one logical qubit at distance 3, with physical T gates implementing a logical T gate up to conjugation.
  • 3.1 15-to-1 distillation: Removing ten redundant qubits simplifies the 15-to-1 circuit to five qubits and 11 π/8 rotations.The redundant qubits begin in Z eigenstates, undergo Z-type rotations, and are finally measured in Z, always yielding +1.
  • 3.2 Triorthogonal codes: Puncturing the construction yields a 14-to-2 protocol with higher output error probability, namely 7p2, because its code distance is 2.The second output is obtained by initializing a fourth qubit in |+⟩ and leaving it unmeasured.
  • 3.3 Surface-code implementation: The 15-to-1 implementation uses 11 tiles for 11 time steps, costing 121d3, while the 20-to-4 implementation uses 14 tiles for 17 time steps, costing 238d3 at leading order.Each time step corresponds to an auto-corrected π/8 rotation implemented through selective measurements.
  • 3.4 Benchmarking: Compared with braiding-based schemes, the leading-order space-time costs decrease by 60% for 7-to-1, 84% for 15-to-1, and 90% for 20-to-4.The comparison benchmarks these lattice-surgery implementations against braiding of hole defects and other lattice-surgery optimization approaches.
  • 3.5 Higher-fidelity protocols: The output-to-input ratio is not a sufficient cost metric because protocols with higher ratios can have lower success probabilities that increase actual space-time cost.For example, the 912-to-112 protocol has approximately 40% success probability, more than doubling its effective cost, whereas 225-to-1 is barely affected by success probability.
  • 3.5 Higher-fidelity protocols: For an n-qubit code with mx X stabilizers and k logical qubits, the framework uses 1.5(mx + k) + 4 tiles and n − mx time steps, so protocol choice should minimize the cost function for the target fidelity.The protocols output k magic states with success probability (1 − p)n.

4 Trade-offs limited by T count

The paper trades space against time by combining data blocks with distillation blocks, progressing from minimal setups to faster configurations with additional distillation resources. For the example computation, these trade-offs reduce space-time cost while increasing physical-qubit requirements.

  • Minimal setup: 100 qubits fit in a compact data block using 153 tiles, while the p = 10^-4 minimal setup adds an 11-tile 15-to-1 distillation block.The 15-to-1 block outputs a magic state every 11 time steps with 99.9% success.
  • Minimal setup: 210 tiles and 9.27 · 10^8 time steps describe the p = 10^-3 minimal setup, which uses a compact data block, a 44-tile 116-to-12 block, and 13 storage tiles.The 116-to-12 block distills 12 magic states in bursts, averaging one state every 9.27 time steps.
  • Code distance: 55,400 physical qubits and roughly 4 hours are sufficient for the p = 10^-4 minimal setup at code distance d = 13 and a 1 µs code-cycle time.The final error probability is 0.2%.
  • Space-time trade-off: A factor-of-5 reduction for p = 10^-4 and a factor-of-2.8 reduction for p = 10^-3 summarize the space-time-cost improvement from adding distillation blocks and using faster data blocks.The time per T gate can be reduced to 1 time step, and the input circuit should be optimized for T count.

5 Trade-offs limited by T depth

The paper parallelizes T layers using units built from data and distillation blocks, trading additional qubits and preparation resources for computation time proportional to T depth. The construction reaches one T layer per measurement time at a finite maximum number of units.

  • T-layer parallelization: 10^8 T gates arranged in 10^6 layers of 100 T gates motivate parallelizing T layers to make computation time proportional to T depth.The scheme implements Fowler's time-optimal approach by targeting one measurement per T layer.
  • T-layer parallelization: Quantum teleportation and post-corrected π/8 rotations allow all mutually commuting π/8 rotations in a T layer to execute simultaneously.The time-optimal circuit uses Bell-pair preparation, T-gate application, and final Bell measurements, followed by correction-qubit measurements.
  • Units: 2n · nL qubits would be required by the naive circuit, so the paper groups qubits into reusable units to avoid scaling space with computation length.With nu units, nu−1 T layers can be performed at the same time.
  • Time optimality: At nmax = tu/tm + 1 units, a T layer is executed every tm; for the example, time optimality requires 1470 units at p = 10^-4 and 3052 units at p = 10^-3.The corresponding unit-preparation times are tu = 1469 µs and tu = 3051 µs.
  • Space-time trade-offs: Three units reduce computation time to 56.5% of the fast setup, while ten units reduce it to 11%, illustrating a linear space-time trade-off.Increasing the number of units improves space-time cost after the initial trade-off from the fast setup.
  • Distributed units: A circular distributed arrangement can share Bell pairs between neighboring quantum computers, allowing units to operate independently after entanglement sharing.The circular arrangement needs one fewer unit and stores nT rather than 2nT correction qubits per unit.

6 Trade-offs beyond Clifford+T

The paper extends its surface-code schemes from Clifford+T to arbitrary-angle rotations and multi-controlled Pauli gates, introducing resource-state and measurement strategies that trade space for speed. These extensions can make execution depend on rotation depth rather than T depth, but their space-time cost is not fully investigated.

  • 6.1 Clifford+ϕ circuits: Clifford+ϕ circuits replace T count and T depth with rotation count and rotation depth as their primary complexity measures.
  • 6.1 Clifford+ϕ circuits: Each ϕ rotation consumes a |ϕ⟩ resource state, with failed corrections requiring successive |2ϕ⟩, |4ϕ⟩, and higher-angle resource states.For ϕ = π/2^k, specialized distillation protocols can produce the required states; other angles can be approximated or synthesized.
  • 6.1 Clifford+ϕ circuits: Post-corrected ϕ rotations defer correction decisions, allowing resource-state measurements to be cascaded or postponed for time-optimal execution.The cascade terminates after k steps when |π/2^k⟩ states are used.
  • 6.1 Clifford+ϕ circuits: 100 rotations per layer require, on average, 8t_m to execute because all measurement cascades in the layer must terminate.
  • 6.2 Multi-controlled Pauli gates: Multi-controlled Pauli gates with n controls can be constructed from 2^n − 1 P_{π/2^n} rotations while retaining rotation depth 1.The C(P1, P2, P3) and C(P1, P2, P3, P4) examples use 7 and 15 rotations, respectively.
  • 6.3 Summary: Clifford+ϕ schemes can speed computation by several orders of magnitude, but arbitrary-angle resource-state distillation and storage require more space.

7 Conclusion

The conclusion presents modular surface-code schemes that trade additional qubits for shorter computation time without requiring prior knowledge of the input circuit. Clifford+ϕ circuits extend these trade-offs further, although their space-time cost remains unassessed.

  • Conclusion: The schemes translate complete quantum computations into surface-code architectures of different sizes using modular blocks that can be optimized independently.Resource counting requires only the input circuit’s T count and T depth, and the reported space-time cost is lower than in earlier works.
  • Big quantum computers are fast: 4 hours and 55,400 physical qubits characterize the minimal setup for a 100-qubit computation with T count 10^8 and T depth 10^6 at p = 10^-4.The minimal setup uses 164 tiles and executes one T gate every 11 code-cycle-equivalent time units.
  • Big quantum computers are fast: Parallelizing T layers enables further space-time trade-offs, reducing execution time toward one measurement per T layer.The approach increases space-time cost, especially for linear arrangements, and supports distributed computing through neighboring Bell-pair sharing.
  • Conclusion: Clifford+ϕ circuits can make execution time proportional to rotation depth rather than T depth by introducing additional resource states.
  • Conclusion: The paper does not investigate how the additional Clifford+ϕ trade-off affects space-time cost.
  • Room for optimization: Known input circuits could permit parallel T gates and shared tiles between distillation and data blocks, providing room for further optimization.
  • Beyond surface codes: Color-code patches could reduce physical-qubit space cost, but they require more elaborate hardware for higher-weight check measurements.
  • Outlook: The outlook estimates that 60,000–300,000 physical qubits for Hubbard-model simulations with T count 10^8 could become available in 7–9 years if qubit quality improves accordingly.

A Surface-code qubits and lattice-surgery operations

The appendix maps a tile-based patch framework onto physical surface-code patches and lattice-surgery operations. Patches encode logical qubits through boundaries, while initialization, measurement, deformation, and multi-patch measurement realize the computational rules.

  • Surface-code patches: Each tile becomes d^2 physical data qubits, with dashed and solid boundaries representing rough and smooth surface-code boundaries.Physical qubits occupy vertices; bright and dark faces represent Z and X stabilizers.
  • Surface-code patches: Logical X and Z operators are represented by products of physical boundary operators along the corresponding patch edges.
  • State initialization: Logical |0⟩ and |+⟩ states are initialized by preparing all physical qubits in the matching basis and measuring stabilizers.For arbitrary states, state injection has constant time cost but is non-fault-tolerant.
  • Lattice-surgery operations: Two-patch measurements implement lattice surgery and require d code cycles to account for measurement errors.Patch deformation and twist-based surgery extend this to products involving Y operators.
  • Patch measurement and Bell state preparation: Single-patch X- or Z-basis measurement measures all physical qubits in that basis and applies classical error correction without time cost scaling with d.
  • Multi-patch measurements: Multi-patch measurements initialize an ancilla region in |+⟩, introduce new check operators, and measure their product for d code cycles to obtain the desired Pauli product.
  • Patch deformation: Moving boundaries and corners are implemented by lattice-surgery-like stabilizer changes followed by physical-qubit measurements.Both operations require d code cycles to account for measurement errors.

B Extended ruleset

The extended ruleset generalizes patches beyond four or six corners and permits shortened edges, expanding the operations representable in the tile framework. These extensions reduce space or add functionality at the cost of additional error considerations.

  • Multi-corner patches: A patch with 2N + 2 corners represents N qubits, with its edges assigned the corresponding multi-qubit Pauli operators.
  • Shortened edges: Shortened edges allow patches to occupy fewer tiles but introduce a per-time-step probability p_err of errors associated with the shortened-edge Pauli operator.
  • Extended initialization and measurement rules: Multi-corner patches initialize all constituent qubits simultaneously in the same X- or Z-eigenstate at zero framework cost.
  • Extended initialization and measurement rules: The corresponding measurement rule measures all qubits in one patch simultaneously and in the same basis, removing the patch from the board.
  • Pauli product measurements: An ancilla multi-corner patch can measure products of n Pauli operators by initializing in |+⟩^n and adjoining its Z edges to the measured operators.Its surface-code implementation is identical to the multi-patch measurement implementation.
  • Extensions: The ruleset remains extensible to operations such as moving corners inside a patch and to alternative error models for non-Pauli eigenstate initialization.

C Proof-of-principle device

The paper presents a proof-of-principle universal two-qubit error-corrected device using patch operations, rotations, lattice-surgery measurements, and undistilled magic states. The construction requires 48 physical data qubits at code distance 3, with the general cost scaling as 6d^2 − 2d.

  • Device construction: (3d − 1) · 2d physical data qubits support a proof-of-principle universal two-qubit error-corrected quantum computer with undistilled magic states.The device demonstrates the operations required for large-scale quantum computing.
  • Example computation: The example computation applies π/8 rotations around Z⊗Z, Y⊗X, and Y⊗Y using magic-state consumption and patch deformations.The Y⊗Y rotation requires an explicit Clifford transformation because both Y operators cannot be made accessible simultaneously for lattice surgery.
  • Magic-state operations: Magic-state consumption implements the Z⊗Z rotation by measuring Z1 ⊗ Z2 ⊗ ZL after encoding the magic state in a three-qubit repetition code.The logical operator is ZL = Z ⊗ Z ⊗ Z.
  • Qubit cost: 48 physical data qubits implement the proof-of-principle experiment at d = 3, while the general requirement is 6d^2 − 2d qubits.The corresponding counts are 140 qubits for d = 5 and 280 qubits for d = 7; syndrome-readout measurement qubits roughly double the total.

D Implementation of the 7-to-1 protocol

The paper implements 7-to-1 |Y⟩-state distillation using a block derived from the seven-qubit Steane code. In the tile framework, the protocol uses four rotations and a seven-tile block with leading-order space-time cost 28d^3.

  • Protocol basis: The 7-to-1 distillation protocol is based on the seven-qubit Steane code and is implemented for benchmarking purposes.The Steane code’s X stabilizers are represented by faces, with a logical X operator supported on three designated qubits.
  • Circuit construction: Four qubits are initialized in the |+⟩ state, corresponding to three X stabilizers and the logical X operator.The circuit assigns π/4 rotations with Z operators according to each Steane-code qubit’s stabilizer and logical-operator participation.
  • Circuit construction: The remaining four rotations form the distillation circuit after three corner-qubit single-qubit Zπ/4 rotations are absorbed into the initial state.The absorbed rotations correspond to qubits belonging only to one stabilizer and no logical operator.
  • Resource cost: 7 tiles and four rotations give the protocol a leading-order space-time cost of 28d^3.The block uses seven tiles because consuming |Y⟩ resource states requires no Clifford correction.
Loading 1808.02892v3…