Source-linked AI summary
Efficient magic state factories with a catalyzed |CCZ> to 2|T> transformation
Craig Gidney, Austin G. Fowler
TL;DR
Magic-state distillation is a major cost in surface-code quantum computation, motivating more efficient factories. The paper constructs lattice-surgery |CCZ⟩ and catalyzed |T⟩ factories, obtaining faster production and improved resource efficiency, while identifying catalyst-noise and single-factory scope limitations.
Problem
Magic-state distillation is costly in surface-code quantum computation, motivating more efficient factories for non-Clifford resources.
Method
The paper applies lattice surgery to fault-tolerant Toffoli distillation and uses a catalyst |T⟩ state to transform |CCZ⟩ states into pairs of |T⟩ states.
Results
The constructions provide improved factory resource estimates and enable fivefold faster Toffoli-dominated algorithms relative to the cited |T⟩ factory.
Takeaways & Limitations
The |CCZ⟩ factory supports classically intractable chemistry computations, while increasing level 1 code distance enables factoring 4096-bit numbers.
Takeaways & Limitations
Catalyst noise grows as Θ(nϵ), and the study restricts optimization to the single-factory regime.
Abstract
from arXiv · showhide
We present magic state factory constructions for producing $|CCZ\rangle$ states and $|T\rangle$ states. For the $|CCZ\rangle$ factory we apply the surface code lattice surgery construction techniques described by Fowler et al. to the fault-tolerant Toffoli. The resulting factory has a footprint of $12d \times 6d$ (where $d$ is the code distance) and produces one $|CCZ\rangle$ every $5.5d$ surface code cycles. Our $|T\rangle$ state factory uses the $|CCZ\rangle$ factory's output and a catalyst $|T\rangle$ state to exactly transform one $|CCZ\rangle$ state into two $|T\rangle$ states. It has a footprint 25% smaller than the factory of Fowler et al. but outputs $|T\rangle$ states twice as quickly. We show how to generalize the catalyzed transformation to arbitrary phase angles, and note that the case $θ=22.5^\circ$ produces a particularly efficient circuit for producing $|\sqrt{T}\rangle$ states. Compared to using the $12d \times 8d \times 6.5d$ $|T\rangle$ factory of Fowler et al., our $|CCZ\rangle$ factory can quintuple the speed of algorithms that are dominated by the cost of applying Toffoli gates, including Shor's algorithm and the chemistry algorithm of Babbush et al.. Assuming a physical gate error rate of $10^{-3}$, our CCZ factory can produce $\sim 10^{10}$ states on average before an error occurs. This is sufficient for classically intractable instantiations of the chemistry algorithm, but for more demanding algorithms such as Shor's algorithm the mean number of states until failure can be increased to $\sim 10^{12}$ by increasing the factory footprint ~20%.
1 Introduction
The paper targets the high cost of non-Clifford operations and magic-state distillation in surface-code quantum computation. It develops more efficient single-factory constructions using lattice surgery and catalyzed phasing, with applications to faster Toffoli-dominated algorithms.
- Motivation: Non-Clifford operations approximate quantum-algorithm cost because they require magic states, whose distillation can be substantially more expensive than adjacent-qubit CNOTs.The cited T-state factory has a spacetime volume two orders of magnitude larger than an adjacent-qubit CNOT.
- Motivation: The paper adds catalyzed phasing to existing techniques for reducing magic-state distillation cost.The authors frame this as continuing efforts to reduce the assumption that magic states dominate error-corrected quantum-computation cost.
- Scope: The work focuses on optimizing distillation in the single-factory regime to estimate minimum physical-qubit requirements for classically intractable algorithms.It does not investigate whether block-code factories can use catalyzation.
- Contributions: The constructions combine a lattice-surgery |CCZ⟩ factory with a |T⟩-catalyzed circuit that transforms one |CCZ⟩ state into two |T⟩ states.The CCZ construction applies surface-code techniques to fault-tolerant Toffoli distillation, while the catalyzed circuit uses a catalyst |T⟩ state.
- Results and scope: The authors report smaller footprints, faster output, and sufficient error suppression for proposed algorithms beyond the classically simulable regime.The catalyzed T factory has correlated errors because an error can poison its catalyst and cause many subsequent output errors.
2 Lattice surgery construction of the 8|T⟩28ϵ2 →|CCZ⟩factory
The factory translates an error-detecting Toffoli distillation circuit into lattice surgery, using interleaving to produce |CCZ⟩ states efficiently. Its performance is constrained by routing and error regimes, but increased code distance supports demanding computations.
- Construction: A single-layer arbitrary-qubit stabilizer measurement enables rapid measurement of the four stabilizers in the error-detecting Toffoli protocol.The circuit is selected to translate directly into lattice surgery, with time-slice and 3D topological representations of the construction.
- Throughput: 5.5d effective depth results from partially overlapping the factory’s naive 8.5-depth execution.The naive depth comprises stabilizer measurements, T-state injections, basis measurement, and error detection.
- Throughput: 2 interleaved states double the single-state lattice-surgery throughput shown in the time slices.The interleaved construction is depicted through concurrent red and blue qubit activity.
- Routing constraints: Routing can become the algorithmic bottleneck because each |CCZ⟩ production occupies a narrow one-qubit entrance for 3d of every 5.5d cycles.Classically controlled CZ and CNOT operations can consume the remaining 2.5d cycles when they also block the entrance.
- Error performance: ∼5.3 · 10^-11 is the final |CCZ⟩ error rate when the factory operates in the distillation-limited regime.The stated physical gate error assumption is 10^-3, and the factory’s code distance is large enough that topological errors do not dominate.
- Error performance: A roughly 20% footprint increase, raising level 1 code distance from 15 to 19, enables factoring 4096-bit numbers instead of suffering errors in more than 50% of 1024-bit runs.The minimal-distance factory remains suitable for classically intractable chemistry algorithms.
3 The |T⟩-catalyzed |CCZ⟩→2|T⟩ factory
The paper rewrites a fault-tolerant Toffoli construction so that one |CCZ⟩ state and a catalytic |T⟩ state produce two consumed |T⟩ states while preserving the catalyst across iterations. The construction is translated into lattice surgery, with correlated catalyst noise requiring the factory to be used as the final distillation step.
- Circuit construction: Four T gates in the fault-tolerant Toffoli can be rewritten as a circuit transforming three |+⟩ states into one |CCZ⟩ state.Diagonalizing the stabilizer table exposes three T gates acting directly on inputs, which can be replaced by three |T⟩ states.
- Catalyzed transformation: One |CCZ⟩ state and one catalyst |T⟩ state produce three |T⟩ states, with one output feeding the next iteration so two are effectively produced per iteration.The third output is an ancillary catalyst that enables the transformation without being consumed.
- Error behavior: The catalyst accumulates noise over n iterations, with poisoning probability Θ(nϵ) when each incoming |CCZ⟩ has error probability ϵ.The catalyst is not consumed, but it can eventually cause bad outputs.
- Error behavior: Correlated errors produce Θ(nϵ), rather than Θ(n^2ϵ), probability of any catalyst error because every catalyst error traces back to an incoming |CCZ⟩ error.This correlation yields fewer whole-algorithm failures than a naive uncorrelated-error calculation would predict.
- Lattice-surgery implementation: The equivalent lattice-surgery circuit uses a product-of-Paulis measurement, classical control, and ancilla states to implement the catalyzed transformation.Time-slice and topological diagrams show the corresponding surface-code operations and error-suppression choices.
4 Arbitrary-Angle Phase Catalysis
The paper generalizes phase catalysis beyond the T gate by using a catalyst to implement two phase rotations through stabilizer operations, an AND computation, a Toffoli, and a doubled-angle rotation. The θ = 22.5° specialization gives an efficient route to producing |√T⟩ states.
- Generalized phase catalysis: For arbitrary θ, a Zθ|+⟩ catalyst enables two Zθ operations using stabilizer gates, one Toffoli gate, and one Z2θ operation.Unlike gate teleportation, the catalyst is not consumed to perform the two rotations.
- Generalized phase catalysis: The generalized circuit can be derived from phase-gradient-via-addition by adding a carry bit, truncating after the first ripple-carry step, and applying the correct fixup operation.The resulting construction directly supports θ = π/2^k and can be generalized to arbitrary angles.
- |√T⟩ production: At θ = 22.5°, the specialized circuit creates two |√T⟩ states using one Toffoli operation and one T gate.The paper reports this as significantly more efficient than the adapted prior techniques it compares against.
- Prior techniques: Repeat-until-success circuits require approximately 45 T gates to approximate a phase operation to precision ϵ = 10^-10.This is one comparison used to motivate the efficiency of the specialized phase-catalysis circuit.
- Prior techniques: Direct synthesis of |T⟩ states uses approximately 25 times more volume than direct synthesis of |T⟩ states in the cited comparison.The cited passage distinguishes the compared state-synthesis procedures but does not identify them completely in the supplied text.
- Prior techniques: Phase-gradient-via-addition is the closest competing technique, while the other compared techniques require an order of magnitude more spacetime volume.The paper characterizes phase catalysis as an optimized form of phase-gradient-via-addition.
5 Lattice surgery construction of the 8|T⟩28ϵ2 →2|T⟩factory
The combined factory uses a |CCZ⟩ factory and the catalyzed transformation to convert eight noisy |T⟩ states into two lower-noise |T⟩ states. Its output rate is bottlenecked by four level-1 |T⟩ factories, and operation requires an initially prepared catalyst.
- Combined factory: Eight noisy |T⟩ states are transformed into two |T⟩ states with quadratically less noise.The resulting 4:1 input-to-output ratio is competitive with the 3:1 ratio of block codes.
- Combined factory: The combined construction reorders stabilizer measurements and relocates output qubits so the |CCZ⟩ factory fits into the C2T factory.It also omits interleaving because the combined design has four factories rather than the five needed for the interleaved rate.
- Catalyst management: The factory must be bootstrapped with an initial catalyst |T⟩ state whose error rate is no higher than that of the |CCZ⟩ factory.Bootstrapping recurs when the catalyst is lost because the |CCZ⟩ state is consumed before distillation-error detection.
- Output rate: Four level-1 |T⟩ factories are assumed, each producing a pair of noisy |T1⟩ states every 6.5d cycles when functioning perfectly.These factories supply the inputs that determine the combined factory’s output rate.
- Output rate: Level-1 factories discard outputs roughly 3% of the time after detecting an error, so their production rate must increase by more than 3% to sustain 6.5d-cycle operation.The paper notes that several small-rate improvements could provide the needed margin.
6 Conclusions
The paper presents CCZ and catalyzed T factories, extends phase catalysis to arbitrary angles, and identifies practical speed and volume improvements. It also outlines further optimizations and boundaries, including routing-volume trade-offs, single-factory focus, and unexplored catalyzed block factories.
- Contributions: The constructions include a |CCZ⟩ factory, a catalyzed |T⟩ factory, and a generalization of phase catalysis to arbitrary angles.The angle θ = 22.5° is highlighted as particularly efficient for producing |√T⟩ states.
- Applications: Fivefold faster Toffoli-dominated algorithms are expected when using the |CCZ⟩ factory instead of Fowler et al.'s |T⟩ factory.The comparison includes Shor’s algorithm and the chemistry algorithm in [1], while T-dominated algorithms receive a more modest 2× speedup.
- Further optimizations: A possible 1d depth reduction from merging level 1 T-state injection with final stabilizer measurement remains unclaimed pending simulation of its topological error effects.The authors state that the optimization's impact on topological error rates is difficult to predict.
- Further optimizations: Over 20% footprint reduction is possible by eagerly routing |CCZ⟩ outputs, but this reclassifies volume as routing volume rather than truly reducing it.The optimization routes outputs to their final destination before verification instead of holding them beside the factory.
- Scope and open questions: The study focuses on low-volume factories in the single-factory regime rather than tiny-footprint or high-footprint multi-factory designs.The paper notes that block-code factories may outperform its efficiency when enough states are distilled in parallel, but whether catalyzed block factories are possible remains unknown.
- Open questions: The authors view a general framework for discovering catalyzed circuits as an important open direction because such circuits can be surprisingly efficient.They also speculate that related techniques may reflect different rewritings of a small set of underlying circuit identities.