PaperlayerView exact revision on arXiv

Source-linked AI summary

Codes and Protocols for Distilling $T$, controlled-$S$, and Toffoli Gates

Jeongwan Haah, Matthew B. Hastings

arXiv:1709.02832v3quant-ph

TL;DR

Magic-state distillation can consume far more resources than the algorithms that use its outputs, motivating more efficient protocols. The paper develops generalized triorthogonal codes and stabilizer-check methods for distilling T, controlled-S, and Toffoli states. Its examples include an asymptotically efficient randomized construction and a distance-8 code that distills 512 T gates into 10 CCZ states.

  • Problem

    Magic-state distillation can require far more space, Clifford operations, and noisy non-Clifford operations than implementing most algorithms that use the states.

    Source: §1 · p. 2

  • Method

    The paper develops generalized triorthogonal codes for logical T, controlled-S, and CCZ gates and stabilizer-check protocols using code-based transversal gates.

    Source: §1 · p. 2

  • Results

    The randomized construction reaches asymptotic distillation efficiency γ→1, and a Reed-Muller code distills 512 T gates into 10 CCZ states with distance 8.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Some Reed-Muller and stabilizer-check examples use lower input-to-output gate ratios than known protocols at the same error-reduction order and code size.

    Source: §1 · p. 2

    Bootstrapping the check protocols to large α requires a large batch of qubits to ensure independence, and using further enlarges the batch.

    Source: §6 · p. 27

Abstract

from arXiv · show

We present several different codes and protocols to distill $T$, controlled-$S$, and Toffoli (or $CCZ$) gates. One construction is based on codes that generalize the triorthogonal codes, allowing any of these gates to be induced at the logical level by transversal $T$. We present a randomized construction of generalized triorthogonal codes obtaining an asymptotic distillation efficiency $\gamma\rightarrow 1$. We also present a Reed-Muller based construction of these codes which obtains a worse $\gamma$ but performs well at small sizes. Additionally, we present protocols based on checking the stabilizers of $CCZ$ magic states at the logical level by transversal gates applied to codes; these protocols generalize the protocols of 1703.07847. Several examples, including a Reed-Muller code for $T$-to-Toffoli distillation, punctured Reed-Muller codes for $T$-gate distillation, and some of the check based protocols, require a lower ratio of input gates to output gates than other known protocols at the given order of error correction for the given code size. In particular, we find a $512$ T-gate to $10$ Toffoli gate code with distance $8$ as well as triorthogonal codes with parameters $[[887,137,5]],[[912,112,6]],[[937,87,7]]$ with very low prefactors in front of the leading order error terms in those codes.

1 Introduction

The paper develops distillation approaches for T, controlled-S, and Toffoli gates, motivated by the high resource cost of magic-state distillation. It generalizes triorthogonal codes and introduces other code and stabilizer-check protocols, including examples with improved input-to-output ratios.

1 Introduction

  • Distillation can require far more space, Clifford operations, and noisy non-Clifford operations than implementing most algorithms that use the resulting magic states.This makes improvements in distillation efficiency consequential for total resource cost.Source: §1 · p. 2
  • Generalized triorthogonal codes induce T, controlled-S, or CCZ gates logically through transversal T, while the paper also presents stabilizer-check protocols for Toffoli states.The check protocols use hyperbolic or normal inner codes to measure magic-state stabilizers.Source: §1 · p. 2
  • The randomized generalized-code construction achieves asymptotic distillation efficiency γ→1, and a Reed-Muller construction gives a 512-T-gate-to-10-CCZ code with distance 8.The 512-to-10 code obtains eight orders of error reduction.Source: §1 · p. 2
  • Punctured Reed-Muller codes yield T-gate protocols with better input-to-output ratios than known protocols at certain orders of error reduction.A separate method reduces space for triorthogonal-code protocols at the cost of increased depth.Source: §1 · p. 2

2 Triorthogonal Matrices: Definitions and Generalizations

The section defines triorthogonal codes and connects them to protocols that prepare magic states using transversal gates and measurement. It generalizes the code framework to T, controlled-S, and CCZ gates, and describes a space-time tradeoff for triorthogonal-code protocols.

2.1 Definitions

  • A triorthogonal matrix defines a CSS code whose even-weight row span supplies X stabilizers and whose distance is the minimum weight of a nontrivial Z-logical operator.The section also defines binary vectors, code duals, and triorthogonal spaces through parity and inner-product operations.Source: §2.1 · pp. 2–3, §2.2 · p. 3

2.2 Triorthogonal Spaces and Punctured Triorthogonal Matrices

  • Padding a triorthogonal code enables a Bell-pair protocol: apply transversal T to the encoded half, measure its logical X, and post-select on +1 stabilizers to prepare a magic state.For punctured codes, prepare the pre-puncture code state, apply T on unpunctured coordinates, then measure those coordinates; the punctured coordinates hold the output magic state after accepted post-selection.Source: §2.2 · pp. 4–5

2.3 Generalized Triorthogonal Matrices: T-to-CCZ Distillation

  • Generalized triorthogonal codes implement logical T, controlled-S, and CCZ gates through transversal T, up to an overall logical Clifford operation.The framework encodes the different gates in designated row groups and defines distance by the minimum weight of an undetected input error.Source: §2.3 · pp. 5–6

2.4 Space-Time Tradeoff For Triorthogonal Codes

  • Triorthogonal-code protocols can use k+nX qubits by reducing or eliminating Z ancillas, with additional Clifford and T-gate rounds trading space for depth.When only T gates suffer Z errors, the space-time tradeoff protocol has the same output-error and success probabilities as the usual protocol.Source: §2.4 · pp. 6–7

3 Randomized Constructon of Triorthogonal and Generalized Triorthogonal Matrix

The section develops randomized constructions of triorthogonal and generalized triorthogonal matrices by choosing rows subject to linear constraints. For triorthogonal matrices, the analysis establishes high-probability success and distillation efficiency γ → 1 in the stated asymptotic regime.

3.1 Randomized Construction of Triorthogonal Matrices

  • Rows are chosen iteratively and uniformly at random subject to linear constraints from earlier rows, with failure declared if those constraints cannot be satisfied.The constraints are represented through Mj, formed from earlier rows, pairwise products, and the all-ones vector.Source: §3.1 · p. 8
  • The randomized algorithm succeeds with probability 1 −o(1) for m ≤θ√n when θ is sufficiently small.The analysis also bounds the probability of low-weight vectors in G and establishes linear distance for Mm under suitable choices of parameters.Source: §3.1 · pp. 9–11
  • γ → 1 as n →∞ when m = Θ(√n) and kT = Θ(√n), the asymptotic distillation-efficiency regime established for the randomized construction.The theorem states that the algorithm succeeds with high probability in this regime; its distance statement is incomplete in the supplied passage.Source: §3.1 · p. 11

3.2 Randomized Construction of Generalized Triorthogonal Matrices

  • The generalized construction changes the fixed right-hand sides of the row constraints to match the generalized-code definition and still succeeds with high probability in the considered regime.It uses the same Mj as the triorthogonal construction.Source: §3.2 · pp. 11–12

4 Reed-Muller Code Based Distillation

This section develops Reed–Muller-based triorthogonal codes and distillation protocols, including CCZ and punctured-code constructions. It also discusses a large-m construction bound, quantitative performance estimates, and unpuncturing and stabilizer-state preparation.

4.1 Review of classical Reed-Muller codes

  • RM(r,m) is triorthogonal when 3r<m, enabling the Reed–Muller codes used in the section’s distillation constructions.Source: §4.1 · p. 13

4.2 Triorthogonal codes for CCZ

  • For m=6, the 64-T-to-2-CCZ code has distance 4 and leading output-error coefficient 2944; for m=9, a [[512,30,8]] code yields kCCZ=10.The m=9 construction was found by numerical search after an initial construction with kCCZ=6.Source: §4.2 · p. 15

4.3 Lovasz Local Lemma

  • For large m, the Lovasz local lemma guarantees codes [[2m,3kCCZ,2m/3]] when kCCZ=ntriple≲2^0.58...m, though it does not guarantee a solution in the m=9 regime studied numerically.Source: §4.3 · pp. 16–17

4.4 Error Probabilities and Quantitative Values

  • At ϵin=10^-3, the m=9, kCCZ=10 protocol estimates ϵout≈3.0×10^-17 and 85.5 input T gates per output CCZ, with per-output error ≈5.1×10^-18.The estimated success probability is at least 0.599, yielding an average of about 5.99 output CCZ states.Source: §4.4 · p. 18
  • With m=1 error correction, the acceptance probability at ϵin=10^-3 is about 0.906, while at most 8Ad weight-seven error patterns can cause a logical error.Source: §4.4 · p. 18

4.5 Punctured Reed-Muller Codes

  • Puncturing RM(2,7) produces a unique distance-5 code, [[125,3,5]], and the numerically found punctured codes have fairly small output-error coefficients for their lengths.Source: §4.5 · p. 19
  • Unpuncturing reverses puncturing by adding stabilizers and qubits, and the resulting code has no Z-logical operator of weight at most d.If a low-weight Z-logical has a nonzero substring on the original-code columns, that substring must have weight at least d; cancellation of its odd overlap requires additional weight on the identity columns.Source: §4.5 · p. 19
  • For small distances, the construction enumerates minimum-weight Z-logicals and chooses X-logicals that anticommute with as many as possible, then unpunctures to obtain distance-4 and distance-5 codes.The [[937, 87, 7]] code uses an upper bound on its weight-7 Z-logical count, derived from the computed X-stabilizer weight enumerator of [[887, 137, 5]].Source: §4.5 · pp. 19–20
  • At εin = 10^-3, [[912, 112, 6]] gives pacc = 0.401, εout ≈ 1.07 × 10^-17 per output state, and 20.28 T-gates per output CCZ magic state.Correcting a single error raises pacc to approximately 0.768, with output error approximately 3.35 × 10^-14 per output logical qubit and approximately 10.60 input states per output state. The authors say these ratios are better than known protocols at the given input and output error rates, and expect improved performance at lower input errors.Source: §4.5 · pp. 20, 22
  • For these punctured codes, transversal T requires no Clifford correction because RM(r, 3r + 1) is triply even; Clifford cost remains for preparing the stabilizer state.A coherent Reed–Muller encoding circuit prepares that state in depth m using (m/2)2^m CNOTs, and is described as the polar-code encoding circuit up to input-state choices.Source: §4.5 · p. 22

5 T-to-CCZ protocols using hyperbolic weakly self-dual CSS codes

Hyperbolic weakly self-dual CSS codes use transversal gates to implement logical operations that check CCZ-state stabilizers. The section presents quadratic and quartic error-reduction protocols, with quartic variants trading T count against code size and space.

5 T-to-CCZ protocols using hyperbolic weakly self-dual CSS codes

  • A signed transversal S on a hyperbolic code acts as logical CZ on hyperbolic pairs; controlled-S can therefore measure products of CZ operators.The logical basis is chosen as a hyperbolic basis of S⊥/S, and transversal S need not be logical without qubit-dependent exponents.Source: §5 · pp. 22–23

5.1 Quadratic error reduction

  • 8 T gates produce one CCZ state with output error probability 28p^2 + O(p^3), and the routine detects any single error.The authors note little reason to use a hyperbolic code of distance greater than 2 for this routine, because a pair of T gates on the same qubit can contaminate its control ancilla.Source: §5.1 · p. 24

5.2 Quartic error reduction

  • The quartic routine embeds quadratic-protocol CCZ states into a distance-4 hyperbolic inner code and checks the three CCZ stabilizers using controlled logical operations.The check is run three times, once per stabilizer; the resulting input count is 8k + 6n_inner T gates for k outputs.Source: §5.2 · pp. 24–25
  • Quartic output errors can arise from weight-4 logical errors in the inner code, whose contribution is bounded using the number of weight-4 Z logical operators.The bound is likely an overestimate because a later check may detect a logical error from an earlier check; acceptance probability is ignored in the reported analysis.Source: §5.2 · p. 25
  • 40 T gates per output CCZ and leading error at most 9744p^4 are reported for the [[16, 6, 4]] inner code, with a space footprint below 25 qubits.This protocol uses more T gates than the generalized triorthogonal code,, or a composition of T-to-T and T-to-CCZ protocols.Source: §5.2 · p. 25
  • At large code length, the hyperbolic quartic protocol's input T count approaches 20 per output CCZ.For the [[32, 20, 4]] and [[64, 50, 4]] Reed-Muller codes, the reported counts are 27.2 and 23.4 T gates per output CCZ, respectively.Source: §5.2 · p. 25

6 Clifford stabilizer measurements using normal weakly self-dual CSS codes

Normal weakly self-dual CSS codes support transversal measurements of CCZ-state stabilizers. The section develops a quartic protocol and higher-order bootstrapping, balancing T count against space and batch size.

6 Clifford stabilizer measurements using normal weakly self-dual CSS codes

  • Three copies of a normal code allow transversal controlled-(CZ)X operations to measure the three CCZ-state stabilizers using independent ancillas.The CCZ gate in the controlled operation can be injected using 4 T gates.Source: §6 · p. 26
  • The protocol has quartic error reduction because faulty outputs require paired input-state faults, missed checks, or a distance-4 inner-code logical error.Its total T-gate count is 8k_inner + 8n_inner.Source: §6 · p. 27
  • At high encoding rate, the quartic protocol uses 16 T gates per output CCZ and is reported to beat prior T-to-CCZ protocols at quartic error-reduction order.It checks stabilizers without repeating the three checks three times, but uses roughly three times the space overhead of the hyperbolic-code method.Source: §6 · pp. 26–27
  • Bootstrapping combines protocols of orders 2^α and 2^(α−1), giving n_(α+1) ≃ n_α + 2n_(α−1) when the inner code has sufficiently high encoding rate.The protocol uses an inner code of distance 4 and injects CCZ gates from the lower-order protocol.Source: §6 · p. 27
  • Combining the construction with reduces the asymptotic T count to at most 3.33d + 0.67 for d a power of 2, at the expense of larger batches.The reported counts are 14 at d = 4 and 26 at d = 8, versus 16 and 32 without that combination.Source: §6 · p. 27
  • For large α, bootstrapping requires very large batches to ensure independence of the input CCZ states and inner-code CCZ gates.Using further increases the necessary batch size.Source: §6 · p. 27

Related papers

Loading 1709.02832v3…