Magic state cultivation: growing T states as cheap as CNOT gates

Craig Gidney; Noah Shutty; Cody Jones

Source-linked AI summary

Magic state cultivation: growing T states as cheap as CNOT gates

Craig Gidney, Noah Shutty, Cody Jones

arXiv:2409.17595v1Sep 26, 2024quant-ph

TL;DR

Preparing high-quality magic states remains a major cost in fault-tolerant quantum computing. The paper introduces magic state cultivation, which incrementally grows a state’s reliability and host code while refining cross-checking, postselection, and code growth. It reports order-of-magnitude lower spacetime costs than prior work for practical error rates, with strong improvements as physical noise decreases.

Problem
Magic state preparation remains substantially costly because distillation relies on large logical operations, influencing quantum-computer architectures and algorithm design.
Method
Magic state cultivation combines controlled postselection, incremental reliability and code growth, streamlined double-checks, superdense stabilizer cycles, and grafting to prepare T states.
Results
Cultivation reaches error rates from 10^-4 to 10^-9 with spacetime costs an order of magnitude lower than prior work; reducing noise from 10^-3 to 5 · 10^-4 improves logical error from 2 · 10^-9 to 4 · 10^-11 and cuts cost tenfold.
Takeaways & Limitations
The efficiency and noise responsiveness of cultivation suggest it could outpace practical quantum-computing needs and obsolete magic state distillation in practice.
Takeaways & Limitations
The simulations extrapolate T-gate behavior from S-gate behavior under Assumption 3.1, use a digitized noise model, and require experiments for validation.

Abstract

from arXiv · show

We refine ideas from Knill 1996, Jones 2016, Chamberland 2020, Gidney 2023+2024, Bombin 2024, and Hirano 2024 to efficiently prepare good $|T\rangle$ states. We call our construction "magic state cultivation" because it gradually grows the size and reliability of one state. Cultivation fits inside a surface code patch and uses roughly the same number of physical gates as a lattice surgery CNOT gate of equivalent reliability. We estimate the infidelity of cultivation (from injection to idling at distance 15) using a mix of state vector simulation, stabilizer simulation, error enumeration, and Monte Carlo sampling. Compared to prior work, cultivation uses an order of magnitude fewer qubit-rounds to reach logical error rates as low as $2 \cdot 10^{-9}$ when subjected to $10^{-3}$ uniform depolarizing circuit noise. Halving the circuit noise to $5 \cdot 10^{-4}$ improves the achievable logical error rate to $4 \cdot 10^{-11}$. Cultivation's efficiency and strong response to improvements in physical noise suggest that further magic state distillation may never be needed in practice.

1 Introduction

Magic state cultivation addresses the substantial cost of preparing non-Clifford magic states by refining code-based preparation into a practical, incrementally growing construction. Its improvements combine selective postselection, reliability and code growth, streamlined checks, faster stabilizer measurement, and grafting, with simulations indicating large practical gains.

Motivation: Magic state distillation remains costly because it uses large logical operations, making magic-state preparation a major contributor to fault-tolerant quantum-computation cost.This cost has influenced architecture and algorithm choices, including routing overheads and efforts to reduce T counts.
Related work: The paper refines earlier physical-operation approaches, including Chamberland and Noh’s color-code cross-checks and Itogawa et al.’s square-grid construction under 10^-3 noise [Ito+24].The earlier cross-check idea uses GHZ-controlled transversal HXY operations and works well at small code distances.
First, third, and fourth improvements: The construction improves efficiency by balancing early error detection against retry rates, using paired time-reversed checks, and measuring color-code stabilizers with the superdense cycle.Too much detection harms retries, while too little harms the error rate; the superdense cycle uses fewer layers under square-grid connectivity and permits postselection of difficult cases.
Second improvement: Cultivation incrementally increases both state reliability and code size, reducing postselection enough to target fault distance 5 under 10^-3 uniform depolarizing circuit noise.This gradual growth motivates the name “cultivation” and avoids keeping the code size fixed.
Fifth improvement: Grafting rapidly enlarges the code hosting the prepared state, correcting a previously neglected and surprisingly costly step that is crucial for accurate estimates.Prior work often ignored the need to grow the state to large distances.
Motivation: Magic state cultivation targets practical error rates of 10^-6 to 10^-9, where simulations indicate substantially lower costs and possible eventual replacement of magic state distillation.The construction is explicitly practical rather than asymptotic, with benefits expected for quantum computations using these error rates.

2 Construction

The construction prepares a |T⟩ state through injection, cultivation, and escape, combining repeated checks with code growth and decoding strategies. Its central practical challenge is transferring a highly reliable state into a larger matchable code without sacrificing fault distance.

2.1 Stages: Cultivation uses three stages— injection, cultivation, and escape—ending with a rapidly enlarged code that protects the prepared |T⟩ state.Injection creates the initial encoded state; cultivation increases its fault distance; escape moves it into a safer matchable code.
2.2 Injection Stage: Unitary injection performed best among three considered injection designs, although teleport and Bell injection had surprisingly similar performance.The comparison used brute-force enumeration of error mechanisms, with estimates shown for cultivation without an escape stage.
2.3 Cultivation Stage: The cultivation cycle checks the logical state, grows the color code, and stabilizes new checks to increase reliability while limiting correlated errors.Growth initializes added data qubits into Bell pairs, and stabilization uses repeated superdense color-code cycles; three cycles were selected as the practical compromise.
2.3 Cultivation Stage: Time-reversed double-checks streamline logical-state checking by restoring helper qubits and turning them into flag checks.At d = 3, each check spans 15 qubits and 6 layers, making it faster and more compact than both and [HIF24].
2.4 Escape Stage: The escape stage was by far the hardest component, because the cultivated state must be moved quickly into a larger code before unpostselected rounds damage it.Direct color-code growth was blocked by decoder limitations, while prior transformation and lattice-surgery approaches were insufficiently efficient or failed to preserve the required distance.
2.4 Escape Stage: Grafting grows a large surface code from a small color code through a partially folded intermediate whose distance is set by the surface code.After stabilization, selected color-code stabilizers are dropped, retained, or decomposed to transition into a fully matchable code.
2.5 Decoding: Escape decoding converts selected color-code detection patterns into a matching problem using postselection and doublet nodes, then keeps states according to the decoder’s complementary gap.Early injection and cultivation use full postselection, while escape postselection is limited to stabilizers whose removal preserves code distance; matching remains suboptimal without postselecting one color.
2.6 Errata: An erratum identifies sign-entangling problems for 6-body stabilizers that were missed by d = 3 state-vector simulations and d = 5 stabilizer simulations.The authors propose two fixes and expect them not to affect final results, but updated circuits and resampling were deferred.

3 Results

The simulations quantify cultivation under uniform depolarizing noise, using proxy-state assumptions and end-to-end stabilizer simulations to assess error rates, retries, spacetime cost, and escape-stage idling. Results show strong sensitivity to physical noise, while the final grafted code introduces a reliability and retry trade-off.

3.2 Assumptions: The T-state logical error rate is estimated as twice the S-state rate because distance-3 simulations found T|+⟩ cultivation roughly twice as error-prone as S|+⟩ cultivation.This proxy is applied to convert simulation outputs into the reported estimates.
3.2 Assumptions: The proxy assumption becomes less reliable as physical noise decreases and may fail at higher fault distance, including the unverified distance-5 case.The authors retain it because they lack a better alternative.
3.3 Simulations: End-to-end simulations start at injection and finish in a distance-15 matchable code, but do not simulate consuming the state for gate teleportation.The construction is evaluated under uniform depolarizing noise using stabilizer simulations.
3.3 Simulations: Four or five orders of magnitude better performance is observed for d1 = 5 than d1 = 3 at p = 10^-3/2, with 10 versus 2 attempts per kept shot.At p = 10^-3, d1 = 5 is three orders of magnitude better using 100 attempts per kept shot, versus 4 for d1 = 3.
3.3 Simulations: Cultivation is extremely sensitive to physical noise strength p, which changes the optimal target distance d1.At p = 2 · 10^-3, d1 = 5 requires 1000 attempts per kept shot to break even with d1 = 3 at 20 attempts.
3.3 Simulations: Spacetime cost is estimated by integrating surviving shots times activated qubits, with slightly more pessimistic volume assumptions to account for packing constraints.The construction gradually activates qubits while postselection continuously removes failing shots.
3.3 Simulations: At d2 = 15, the grafted matchable code is comparable to a d = 11 surface code, and maintaining 10^-9 error per round requires about a 10^-4 retry chance per round.The result motivates growing to a larger final code distance for unconditional use, while expected cultivation cost is projected to remain similar.

4 Conclusion

Magic state cultivation substantially reduces the cost of preparing T states across practical error rates, while remaining an early construction with important simulation and implementation limitations.

10^-4 to 10^-9 target error rates require an order of magnitude less spacetime cost than prior work.
A 2x noise-strength improvement from 10^-3 to 5 · 10^-4 yields a 50x logical error-rate improvement and a 10x cost reduction.
The construction remains rough, with low qubit utilization, a complicated escape stage, and several opportunities for circuit, decoder, code, and connectivity improvements.
The study simulates T-state production rather than complete logical T gates, which would also require retries, lattice surgery, and Clifford correction.
The simulations extrapolate T-gate behavior from S-gate behavior under Assumption 3.1 and use a digitized noise model, motivating direct simulation and experimental benchmarking.
Cheaper T states could make T-hungry carry-lookahead adders preferable to low-T-count ripple-carry adders, altering algorithmic spacetime trade-offs.

5 Contributions

The paper’s construction and simulations were led by Craig Gidney, with Cody Jones supervising and Noah Shutty identifying a decoder-related bottleneck.

Craig Gidney built the construction, simulated its performance, and wrote the paper.
Cody Jones suggested construction improvements and supervised the project.
Noah Shutty showed that discouraging escape-stage simulations reflected decoder limitations rather than an inherent stage bottleneck.

A Noise Model

The paper uses a uniform depolarizing noise model for all circuit simulations, with its channel definitions and composition convention specified by Figures 17 and 18.

All circuits are simulated with a uniform depolarizing noise model to enable comparison with prior work.
Figure 17 defines the noise channels used by Figure 18.
Figure 18 specifies the uniform depolarizing circuit noise model and notes that B ·A means B is applied after A.

B Chunked Circuit Construction

The construction is assembled from verified stabilizer-circuit chunks whose explicit flows support composition, detector generation, flexible creation, and controlled decoding structures.

Workflow: The construction creates, iterates, and optimizes each cycle in chunks using a process similar to [Gid24b].
Chunk representation: A chunk is a stabilizer circuit annotated with stabilizer flows that summarize and verify its input-output behavior and measurement parities.
Composition: Concatenating chunks verifies matching stabilizers and converts internal flows with deterministic measurement parity into detector annotations.
Design benefits: The chunked approach provides decoupling, contracts, artistic freedom, and micro-management as its four main benefits.
Decoupling: Decoupling lets surrounding chunks vary without changing a chunk’s internal details, enabling different color-code-cycle approaches to be mixed.
Contracts: Contracts specify expected chunk behavior and support verification, including tests that required code stabilizers have corresponding flows.
Artistic freedom: Artistic freedom allows each chunk to use visual editing, code generation, or different automation strategies suited to its structure.
Micro-management: Micro-management guarantees detector-basis control, which can satisfy decoder-specific comparison structures and avoid circuit-interpretation ambiguity.

C Bonus Figures

The bonus figures document cultivation’s injection, decoding, error-model, idling, noise-scaling, and code-transition behavior, alongside comparisons with lattice-surgery CNOT costs.

Decoder confidence: Cultivation transitions from color-code storage toward full-code storage as the uncertainty region moves toward the patch center over time.Decoder confidence is shown for individual detection events; postselected detectors bypass confidence computation.
Injection designs: Bell injection grows a distance-1 color code to distance 3 using Bell-pair initialization, stabilizer measurements, and fast feedback.Replacing S with T prepares |T⟩ rather than |i⟩.
Injection designs: Teleport injection prepares a four-tile color code, then leaves a [[7, 1, 3]] color code storing T^k|+⟩ after applying T^k and measuring X.The resulting state is subject to deferrable Pauli Z feedback.
Error model: The detector error model separates matchable errors, logical-observable flips, and hyper errors, with a dense hyper-error region marking color-code postselection costs.Black, red, blue, and magenta structures distinguish error classes and their logical effects.
Idling calibration: Complementary-gap distributions have similar shapes for surface and grafted matchable codes, while the gap strongly predicts logical error rates in both.The main distinction in the distributions is an offset of the peaks.
Cost comparison: Cultivation’s spacetime volume is nearly four times that of a distance-15 lattice-surgery CNOT at the same code distance, although equal reliability requires a larger CNOT distance.The comparison rearranges cultivation components into stacks against the CNOT spacetime diagram.