Quantum computation with realistic magic state factories

Joe O'Gorman; Earl T. Campbell

Source-linked AI summary

Quantum computation with realistic magic state factories

Joe O'Gorman, Earl T. Campbell

arXiv:1605.07197v2May 23, 2016quant-ph

TL;DR

Magic-state factories consume substantial fault-tolerant quantum-computing resources, so realistic and efficient designs are needed. The paper combines correlation-aware analytic and numerical error tracking with a constant-time subsystem-code realisation of Bravyi–Haah protocols. Module checking uses up to four times fewer raw magic states in some regimes, while the resource analysis identifies surface-code-limited costs and assumptions that may overestimate implementation overhead.

Problem
Realistic resource costs for implementing multiround magic-state distillation protocols in surface-code quantum computers remain insufficiently characterized.
Method
The paper realizes Bravyi–Haah protocols with gauge-MSD and analyzes correlated errors using module checking, analytic tracking, and Monte Carlo simulation with rare-events preselection.
Results
Module checking can use up to four times fewer raw magic states than block checking in some target-error regimes, while factory costs remain tied to surface-code costs up to constant factors.
Takeaways & Limitations
Correlations can make module-level quality control materially more efficient than block checking, although its advantage depends on the target-error regime and distillation-round transitions.
Takeaways & Limitations
The spacetime overhead may be overestimated because the analysis assumes d rounds of surface-code measurements after every two-qubit gate.

Abstract

from arXiv · show

Leading approaches to fault-tolerant quantum computation dedicate a significant portion of the hardware to computational factories that churn out high-fidelity ancillas called magic states. Consequently, efficient and realistic factory design is of paramount importance. Here we present the most detailed resource assessment to date of magic state factories within a surface code quantum computer, along the way introducing a number of new techniques. We show that the block codes of Bravyi and Haah [Phys. Rev. A 86, 052329 (2012)] have been systematically undervalued; we track correlated errors both numerically and analytically, providing fidelity estimates without appeal to the union bound. We also introduce a subsystem code realisation of these protocols with constant time and low ancilla cost. Additionally, we confirm that magic state factories have space-time costs that scale as a constant factor of surface code costs. We find that the magic state factory required for post-classical factoring can be as small as 6.3 million data qubits, ignoring ancilla qubits, assuming $10^{-4}$ error gates, and the availability of long range interactions.

I. Realising block protocols

The paper gives a low-level realisation of Bravyi–Haah block distillation protocols using constant-weight measurements, gauge-MSD, and explicit resource accounting.

I. Realising block protocols: The protocol is specified as elementary preparations, two-qubit gates, measurements, and corrections acting on n noisy |T⟩ states.Its four steps measure Z-type operators, apply outcome-dependent corrections, measure X-type operators with postselection, and localise outputs.
I. Realising block protocols: Increasing k leaves the number of protocol time steps unchanged while increasing the number of qubits in a block.The explicit circuit is given for Bravyi–Haah (3k + 8) →k protocols.
I. Realising block protocols: Each multi-qubit measurement uses four entangling gates, giving constant measurement weight and constant time cost.The construction replaces potentially high-weight X measurements with simpler measurements.
I. Realising block protocols: Gauge-MSD uses gauge fixing and a cat-state ancilla to create a circuit of depth 4 for both X- and Z-measurement sets.The realisation avoids the monolithic braiding architecture used in an earlier constant-time construction.
I. Realising block protocols: (6k + 14)d^2 logical physical-qubit units and approximately (48k + 112)d^3 space-time units are required for the realisation.The total includes 3k + 6 ancillas in addition to the 8 + 3k distilled qubits, under distance-d toric-code encoding.

A. Blocks, branches and modules

The paper organizes multilevel distillation as a tree of branches and modules, then uses module-level checks to exploit correlations among errors.

A. Blocks, branches and modules: An n →k block consumes n noisy |T⟩ states and probabilistically outputs k states with higher fidelity.Higher n-to-k ratios generally offer greater efficiency, while requiring more complex circuits.
A. Blocks, branches and modules: Distillation levels form a treelike structure in which branches merge at modules containing multiple independent block instances.Branch widths grow across rounds according to the block input and output sizes.
A. Blocks, branches and modules: At a module implementing n_l →k_l blocks, B_l n_l inputs become B_l k_l outputs, so the next branch has width B_{l+1} = B_l k_l.Each qubit in an incoming branch is routed to a different block to avoid correlated inputs.
A. Blocks, branches and modules: Module checking discards the whole module whenever any constituent block fails, unlike block checking, which evaluates blocks individually.This quality check is designed to respond to correlations spread across blocks in a module.
A. Blocks, branches and modules: A detected error in one block can signal correlated errors in other blocks, while a block receiving an error pair may fail to detect it.The paper illustrates this with two damaged branches whose errors overlap in one block.

III. The G-matrix formalism

The G-matrix formalism represents Bravyi–Haah protocols as black boxes mapping noisy input error patterns to accepted output patterns and success probabilities.

III. The G-matrix formalism: The G-matrix splits into G0, which specifies postselection criteria, and G1, which relates input qubits to output qubits.For |T0⟩ distillation, the matrix must satisfy triorthogonality.
III. The G-matrix formalism: Given an input error pattern x, the protocol produces output pattern y = G1x when G0x = 0 and no error is detected.Noisy inputs are treated as a probabilistic ensemble over x.
III. The G-matrix formalism: The normalized accepted-output distribution is Prout(y) = Prunnorm(y)/Psuc, completing the black-box description of protocol performance.The total success probability sums over all possible output states.
III. The G-matrix formalism: The generalized G-matrix framework includes protocols that convert noisy T states into resources for implementing Toffoli gates.The paper considers a G-matrix-based variant of error-suppressed Toffoli protocols.
III. The G-matrix formalism: Module checking can improve error suppression for the Toffoli variants even though the variants perform identically under block checking.The technique applies beyond the Bravyi–Haah protocol family.

IV. Analysis of module checking

The paper analyzes module checking by combining correlation-aware error propagation with numerical simulation, finding substantial resource savings across many target-error regimes but not universally.

IV. Analysis of module checking: The theorem composes η-functions across multiple module-checked distillation levels to estimate success probabilities and global infidelity.The leading-order approximation ϵ_g^(l) ∼ C_lϵ^(2l) was found too coarse for later numerical investigations.
IV. Analysis of module checking: The function η counts lowest-weight undetected input errors that produce each output error pattern y.It counts inputs satisfying |x| = 2, G0x = 0, and G1x = y.
IV. Analysis of module checking: Monte Carlo simulations track raw-state error configurations through the factory, using rare-events preselection when three or more rounds make failures too rare for brute force.The preselection focuses on cases with at least two corrupt input branches.
IV. Analysis of module checking: Module checking uses up to four times fewer raw magic states than block checking in some target-error regimes.It is superior across a large proportion of target error rates, but can lose its advantage near transitions between distillation-round counts.
IV. Analysis of module checking: Near transitions or with low-k codes, lower success probabilities can outweigh module checking’s stronger error suppression.Between transitions, module checking can instead enable higher-k protocols to reach error rates associated with lower-k block checking.

V. Factory overhead analysis

The analysis evaluates magic state factories using physical footprint and production rate rather than distillation cost alone. It sets target global error rates from algorithm success requirements and tests whether candidate factories meet them.

Spacetime overhead captures both the physical qubits occupied by a factory and the rate at which it produces magic states.The analysis treats these as key determinants of quantum-computer size and algorithm runtime.
Balanced investment, clock-rate zoning, and surface-code assumptions are included in the footprint estimate.The study uses smaller codes and faster cycling in early rounds, assumes ϵin = 0.4pg, and assigns d^2 data qubits to a distance-d rotated-lattice code.
A factory must achieve a target global error rate determined by the desired probability that all required non-Clifford gates succeed.The target depends on the algorithm's magic-state demand and the desired whole-algorithm success probability.
A three-round 10-10-10 Bravyi-Haah factory produces 10^15 |T⟩ states after 10^12 successful iterations.For a 90% whole-algorithm success probability, the target is 1.05 × 10^-13; module checking gives ϵglo = 2.3 × 10^-16, while block checking gives approximately 10^-11.

A. Balanced investment

Balanced investment reduces resources by matching surface-code distance to the fidelity required at each distillation round. Its treatment differs for module-checked and block-checked factories because correlated errors constrain lower-level encoding choices.

The cost comparison finds block checking only slightly preferable near transitions to an additional Bravyi-Haah distillation level.Elsewhere, the figure compares block- and module-checked protocols using their respective cost estimates.
Balanced investment uses smaller surface codes for low-fidelity states and larger codes for high-fidelity states.Each logical surface is assigned the distance corresponding to that qubit's round-specific target error rate.
Module checking constrains lower-level balanced investment because encoding noise can become comparable to correlated error.The analysis estimates total output error as ϵtot ∼ ϵglo + kϵenc and chooses intermediate encoding error ϵenc = 0.1 · ϵglo/k.
Block-checked factories can determine code distances by working backward from a local target error without protecting correlated errors.For ptop = 10^-14, the top level requires vPL(d, ϵenc) < 0.1 × 10^-14.
Distillation-round time depends on the protocol and the number of attempts before abandoning the round.The stated examples assign 12tsc × d to Toffoli rounds and 13tsc × d to Reed-Muller rounds.

B. Clock-rate zoning

Clock-rate zoning exploits the fact that surface-code operation time scales with code distance, allowing early distillation rounds to run faster than later rounds.

A distance-d surface code requires d rounds of stabilizer measurements, so balanced investment makes early distillation rounds shorter.If a round squares the input error, the next round may require twice the code distance, allowing the first round to be repeated twice in the same time.
Faster early rounds increase the chance that enough magic states are ready for the next round without reducing the factory's rate.

C. Numerical simulations

The simulations search across protocols, checking methods, repetition counts, and factory sizes to compare spacetime overhead and production rate. They find that module checking can substantially reduce overhead in some regimes, while factory size trades against speed.

The simulations calculate factory volume from code distances, round durations, logical-qubit counts, success probabilities, and protocol choices.The search covers one to three distillation rounds using Bravyi-Haah, Reed-Muller, and Toffoli protocols with block or module checking.
A time-optimal factory must produce 10 magic states every tsc when tsc = 10tmeas/ff.The figure considers factories producing 10^16 T states and compares feasible rates against qubit counts.
A larger factory can more than double production rate when it enables higher-k block codes.This effect is clearest in panel (a); with only two distillation rounds, higher-k codes are not necessarily optimal.
Module checking improves spacetime overhead by a factor of 3 in certain parameter regimes.It can also be slightly detrimental near transitions from i to i + 1 Bravyi-Haah rounds.
A factory for time-optimal factorisation of a 1000-bit number can use 5.6 million data qubits at physical error rate 10^-4.Including syndrome-extraction ancillas raises the physical-qubit estimate to approximately 11 million.
The T-gate to CNOT spacetime-cost ratio is approximately 150–310 for 10^10 < N < 10^30.This supports a constant-factor relationship between magic-state-factory and surface-code overheads in the studied range.

VI. Conclusions

The paper finds that gauge-MSD and module checking improve fully costed magic-state-factory designs, while surface-code error-correction costs remain the dominant constraint. The reported overhead may also be overestimated because the analysis assumes error correction after every two-qubit gate.

Module checking provides an additional factor ∼3 reduction in some parameter regimes.
Balanced investment makes the factory entirely limited by surface-code cost, so distillation refinements offer only constant-factor improvements.
The spacetime overhead may be overestimated because the analysis assumes d rounds of surface-code measurements after every two-qubit gate.Performing error correction only after each of the four protocol steps could reduce the time overhead from 11tscd to 4tscd.
Compared with 3D gauge color codes, surface-code factories have similar asymptotic resource scaling, while current evidence indicates an order of magnitude worse phenomenological threshold for color codes.

A. Comparison with braiding

The paper compares gauge-MSD with braiding-based realisations and develops a subsystem-code construction for Bravyi-Haah protocols. Its design relies on sparse measurements, gauge fixing, and assumptions about available interactions and hardware.

Comparison with braiding: Braiding can realise Bravyi-Haah in constant time when the architecture supports constant-time multi-target CNOT gates.
Comparison with braiding: Gauge-MSD offers a modest spacetime saving over braiding in a distributed architecture.
Hardware assumptions: The implementation assumes long-range entangling gates can be performed in parallel, although hardware platforms differ substantially in gate times and qubit expense.
Subsystem-code construction: The subsystem construction uses stabilizer and gauge groups satisfying ˜S ⊂S ⊂Sg, with the gauge group no longer abelian.
Subsystem-code construction: Gauge-MSD preserves logical qubits while changing gauge degrees of freedom through additional gauge-operator projections.
Sparse measurements: A sparse G⊥ construction has all but one row of weight 4, with the exception having weight k + 2.

F. Proof of error tracking

The proof tracks leading-order errors through module-checked distillation by identifying which correlated branch errors evade detection and recursively propagating their output distributions. The analysis focuses on the smallest undetected error weights and renormalizes by module success probability.

At each distillation level, a function η summarizes tolerance to leading-order errors, while modules map input probability distributions to output distributions.
For quadratically suppressing protocols, 2^l is the smallest number of errors that can evade detection at level l.
Two erroneous branches contribute at leading order only when their error patterns match and their branch indicators satisfy the undetected-error condition.
Relevant undetected errors take the form x = u⊗f, with u of weight 2, and produce outputs y = (G1u) ⊗f.
Higher-level error counts are obtained recursively until reaching C1, where the one-round expression terminates the recursion.
The final error probability is normalized by the success probability of the module and all events feeding into it.

1. Brute Force method

The brute-force method simulates factories by randomly generating input error strings, testing modules, and composing successful outputs across rounds. Its computational cost becomes prohibitive for sufficiently deep factories.

Brute-force simulation randomly generates Boolean input strings and evaluates stabilizer checks and logical outputs for each factory module.
Successful module outputs are stored until enough are available to feed the next distillation round.
For raw magic-state error rate ϵ = 0.001, simulating a round 3 module would require ≫10^21 attempts.
Two-round brute-force factories are achievable for 2 < k < 50, but three-round factories require a different simulation method.

2. Rare Events method

The Rare Events method estimates rare undetected factory errors by conditioning simulations on error configurations capable of causing logical failure, rather than sampling the full factory indiscriminately. This reduced simulation tracks correlated errors and supports calculation of round-three success and global error rates, with analytic and numerical results closely corresponding.

Rare Events simulation: Rare Events simulation conditions on at least two erroneous input branches entering a round-three module, avoiding infeasible postselection of rare configurations.The method first selects the number of error-containing branches conditioned on that number being at least two.
Rare Events simulation: Correlated errors are traced backward through round-three, round-two, and round-one modules to simulate only the affected subsection of the factory.This reduces both the simulated factory size and the number of required iterations.
Rare Events simulation: The reduced simulation discards trials when stabilizer checks pass but the required logical error is absent, eliminating most irrelevant input error strings.The approach also stores smaller Boolean vectors until the final round-three module is simulated.
Probability estimation: The key input probability pnum is the probability that at least two branches leaving round two contain errors.The round-two branch error probability is obtained from numerical simulations of the two-round factory.
Probability estimation: The method uses pnum and the round-two undetected-error probability to determine round-three success probability and global output error.Figure 10 compares the analytic treatment with numerical simulations for Bravyi-Haah protocols and related Toffoli combinations.