PaperlayerView exact revision on arXiv

Source-linked AI summary

Very low overhead fault-tolerant magic state preparation using redundant ancilla encoding and flag qubits

Christopher Chamberland, Kyungjoo Noh

arXiv:2003.03049v1quant-ph

TL;DR

Magic-state distillation remains costly, in part because its Clifford circuits are often not fault-tolerant. This paper directly prepares fault-tolerant |H⟩ magic states in a planar triangular color-code architecture, reporting comparable logical error rates to leading distillation protocols with substantially fewer qubits.

  • Problem

    Magic-state distillation remains costly, partly because its Clifford circuits are often not fault-tolerant and require large-distance encoding of Clifford operations.

    Source: §I · p. 1

  • Method

    The scheme combines flag qubits and redundant ancilla encoding to fault-tolerantly prepare |H⟩ states while measuring color-code stabilizers and a global operator using nearest-neighbor interactions.

    Source: §I · p. 2, §VI · p. 18

  • Results

    At p = 10^-4, 68 and 231 qubits yield logical error rates of 3.6 × 10^-8 and 4.9 × 10^-10, respectively; the scheme has comparable logical error rates to the best known distillation protocols with at least an order of magnitude fewer qubits.

    Source: §I · p. 2, §VI · p. 18

  • Takeaways & Limitations

    The fault-tolerant circuits allow very low logical error rates without requiring stabilizer operations to use very large-distance codes.

    Source: §I · p. 2

    For p = 10^-3 and d_f > 3, acceptance probability is very low, reaching 12% when d_f = 5.

    Source: §VI · p. 19

Abstract

from arXiv · show

The overhead cost of performing universal fault-tolerant quantum computation for large scale quantum algorithms is very high. Despite several attempts at alternative schemes, magic state distillation remains one of the most efficient schemes for simulating non-Clifford gates in a fault-tolerant way. However, since magic state distillation circuits are not fault-tolerant, all Clifford operations must be encoded in a large distance code in order to have comparable failure rates with the magic states being distilled. In this work, we introduce a new concept which we call redundant ancilla encoding. The latter combined with flag qubits allows for circuits to both measure stabilizer generators of some code, while also being able to measure global operators to fault-tolerantly prepare magic states, all using nearest neighbor interactions. In particular, we apply such schemes to a planar architecture of the triangular color code family. In addition to our scheme being suitable for experimental implementations, we show that for physical error rates near $10^{-4}$ and under a full circuit-level noise model, our scheme can produce magic states using an order of magnitude fewer qubits and space-time overhead compared to the most competitive magic state distillation schemes. Further, we can take advantage of the fault-tolerance of our circuits to produce magic states with very low logical failure rates using encoded Clifford gates with noise rates comparable to the magic states being injected. Thus, stabilizer operations are not required to be encoded in a very large distance code. Consequently, we believe our scheme to be suitable for implementing fault-tolerant universal quantum computation with hardware currently under development.

I. INTRODUCTION

Magic state distillation remains a leading approach, but its non-fault-tolerant Clifford circuits drive the need for large-distance encoding. This work proposes a nearest-neighbor, fault-tolerant preparation scheme using triangular color codes, redundant ancilla encoding, and flag qubits.

I. INTRODUCTION

  • Universal fault-tolerant computation needs a universal gate set, while the Eastin-Knill theorem rules out transversal implementation of every such gate in any stabilizer code.The introduction frames low overhead for achieving low logical error rates as a central requirement.Source: §I · p. 1
  • Magic state distillation remains a leading candidate, but its typically non-fault-tolerant Clifford circuits require large-distance encoding to keep Clifford errors negligible.The introduction notes that distillation's cost remains high even though recent results question whether it is always the dominant cost.Source: §I · p. 1
  • A prior direct-preparation scheme used the Steane code and flag-qubit circuits, but required geometrically non-local gates and concatenation.It used fewer qubits than the best known distillation schemes for p ≳10^-5 under the stated idle-qubit noise assumption.Source: §I · p. 1
  • Redundant ancilla encoding and flag qubits let one planar layout measure color-code stabilizers and global operators fault-tolerantly using nearest-neighbor interactions.Extra ancillas used for stabilizer measurements become flag qubits when preparing a GHZ state to measure H⊗n.Source: §I · p. 2
  • The proposed architecture also targets very low logical failure rates without encoding stabilizer operations in very large-distance codes.The authors state that encoded Clifford gates can have logical error rates comparable to the injected magic states.Source: §I · p. 2
  • At p ≳10^-4 under full circuit-level depolarizing noise, the scheme matches the logical error rates of leading distillation protocols with at least tenfold fewer qubits.At p = 10^-4, approximately 5 × 10^-8 logical error requires 64 qubits, with Clifford operations performed at the physical level.Source: §I · p. 2

II. PRELIMINARY MATERIAL

The preliminary material introduces |H⟩ magic states and triangular color codes as the resource and code family used in the preparation scheme. It also motivates fault-tolerant measurement of the Hadamard operator to detect errors in noisy injected states.

A. |H⟩-type magic states

  • An |H⟩ state is a +1 eigenstate of H and can serve as a resource for simulating non-Clifford gates using stabilizer operations.The paper focuses on |H⟩-type magic states.Source: A. |H⟩-type magic states · p. 3
  • A non-destructive Hadamard measurement detects a Y error on |H⟩ through a −1 outcome, while X or Z errors yield random outcomes.The controlled-Hadamard gate in the measurement circuit is decomposed into T, T†, and controlled-Z gates.Source: A. |H⟩-type magic states · p. 3, Figure 2 · p. 3

B. Triangular color code family

  • Triangular color codes support transversal logical Clifford gates, including logical H = H⊗n.Their lattice uses weight-four and weight-six X- and Z-type stabilizers.Source: Figure 3 · p. 3

A. |H⟩-type magic states

  • The scheme aims to make the Hadamard measurement fault-tolerant with a triangular color code, redundant ancilla encoding, and flag qubits.The stated goal is low-resource preparation of encoded |H⟩ states with very low logical failure rates on realistic hardware.Source: A. |H⟩-type magic states · p. 3

B. Triangular color code family

The triangular color code is a two-dimensional self-dual CSS code with boundaries, and its logical Clifford gates can be transversal. The section also specifies the full circuit-level noise model used in the simulations.

B. Triangular color code family

  • Triangular color codes have parameters [[n = (3d^2 + 1)/4, 1, d]] and use weight-four and weight-six X- and Z-type stabilizers.The lattice is 3-colorable, with logical X and Z given by tensor products along a triangle boundary.Source: B. Triangular color code family · p. 3
  • The Lift decoder incorporates flag-qubit outcomes and was reported to give triangular color codes a 0.2% threshold under full circuit-level depolarizing noise.The passage describes its extension to color codes with boundaries.Source: B. Triangular color code family · p. 4
  • The protocol measures the logical Hadamard transversally across ancillas and data, with the paper focusing on a nearest-neighbor fault-tolerant implementation.It then uses the encoded |H⟩ state preparation scheme to target low qubit and space-time overhead.Source: B. Triangular color code family · p. 4
  • The simulation noise model applies independent Pauli faults to single-qubit gates, two-qubit gates, idle locations, and state preparation, and flips measurement outcomes.The supplied passages specify probability p for gate and idle faults and 2p/3 for the listed preparation and measurement faults.Source: B. Triangular color code family · p. 4

III. FAULT-TOLERANT |H⟩STATE PREPARATION SCHEME

The protocol grows a physical |H⟩ state into a triangular color-code encoding, then applies flagged Hadamard measurement and error correction with postselection. Redundant ancillas support both stabilizer and global-operator measurements in the same nearest-neighbor layout.

III. FAULT-TOLERANT |H⟩STATE PREPARATION SCHEME

  • Magic states with very high fidelity are important for long computations, with stated target error probabilities ranging from 10^-7 to below 10^-15.The text notes that distillation circuits are typically not fault-tolerant, motivating encoded Clifford operations under a full circuit-level noise model.Source: §III · p. 4
  • The protocol is designed for nearest-neighbor interactions and uses flag qubits alongside redundant ancilla encoding.The described flagged measurement and error-correction circuits are provided for d ∈ {3, 5, 7}.Source: §III · pp. 4–5
  • A t-flag circuit flags whenever at most t faults produce a data error whose weight exceeds the number of faults.This property is the stated criterion for the measurement circuits used by the scheme.Source: §III · p. 4
  • The protocol first grows a physical |H⟩ state into a distance-d encoded state, then measures H⊗n with a t-flag circuit and applies flagged error correction.Here t = (d − 1)/2; the protocol aborts if flags trigger or specified ancilla-measurement parities are odd, and repeats the measurement and correction pair (d − 1)/2 times.Source: §III · p. 5
  • For p ≳10^-4, the scheme prepares encoded |H⟩ states with similar logical failure rates but orders of magnitude fewer qubits than state-of-the-art distillation schemes.The comparison is stated for code distances up to 7; the cited examples include Ref..Source: §III · p. 5
  • The initial growth step prepares a stabilizer state and measures boundary X- and Z-type generators to obtain the encoded |H⟩ state.Because these measurements are random, negative outcomes require Pauli-frame updates; matching graphs and MWPM determine weight-two corrections.Source: §III · pp. 5–6
  • The growth operation is not fault-tolerant, so the scheme relies on later checks to detect errors arising during preparation.The text describes the growth output as potentially containing a detectable error and a logical error after fewer than (d − 1)/2 faults.Source: §III · pp. 4, 6

B. Performing error correction (EC(d)) using redundant ancilla encoding

The stabilizer-measurement layout deliberately uses extra ancillas that become flags for logical Hadamard measurement, enabling fault-tolerant circuits on the same planar layout. The constructions provide flag circuits for triangular color codes of distances 3, 5, and 7.

B. Performing error correction (EC(d)) using redundant ancilla encoding

  • Each error-correction circuit must be at least one-flag; otherwise, faults in separate stabilizer measurements can create errors that the code may not correct.For d=5, two unflagged faults in separate Z-stabilizer measurements can produce a weight-two data error.Source: B. Performing error correction (EC(d))… · p. 6
  • Weight-six stabilizer measurements use three ancillas and three flags; the ancilla outcomes have odd parity when an error anticommutes with the stabilizer.Exhaustive search verifies that both weight-four and weight-six circuits are two-flag circuits.Source: B. Performing error correction (EC(d))… · p. 6, Figure 6 · p. 7
  • Redundant ancillas become flags for logical Hadamard measurement, making the circuit t-flag with t=(d−1)/2 and requiring at least (d+1)/2 faults for logical failure.The construction is for triangular color codes with d=3, 5, and 7.Source: B. Performing error correction (EC(d))… · pp. 8, 10
  • For d=3, six ancillas form a repetition-code GHZ state, couple to the data through controlled-Hadamard gates, and are measured in logical X; flags check the GHZ parity.The stabilizer and Hadamard circuits use the same layout with ancilla and flag roles reversed.Source: B. Performing error correction (EC(d))… · p. 8, Figure 7 · p. 8
  • The d=3 logical Hadamard circuit is verified as 1-flag: a single fault causing a data error with min(wt(E), wt(EH⊗7))>1 triggers a flag.The verification uses an exhaustive numerical search over single-fault locations.Source: B. Performing error correction (EC(d))… · p. 9
  • For d=5 and d=7, the logical Hadamard circuits use 21 and 45 ancillas, respectively, and are verified as two-flag and three-flag circuits.The d=5 circuit uses 15 flags to check 15 of 20 repetition-code stabilizers; d=7 uses 36 flags to check 36 of 44.Source: B. Performing error correction (EC(d))… · p. 9

IV. RESOURCE OVERHEAD FOR PREPARING ENCODED |H⟩STATES WITH PHYSICAL CLIFFORD GATES

The paper estimates the logical failure rates and resource costs of directly preparing encoded |H⟩ states using physical Clifford gates. At p=10^-4, it reports low-failure-rate preparations with substantially fewer resources than the cited distillation scheme, while noting that the space-time overhead comparison requires adjustment.

IV. RESOURCE OVERHEAD FOR PREPARING ENCODED |H⟩STATES WITH PHYSICAL CLIFFORD GATES

  • The logical-failure estimate counts accepted combinations of (d−1)/2 faults that produce logical errors; higher-order terms have negligible impact for p≤10^-3.The authors state that the inequality is strict because many circuit fault locations are benign.Source: §IV · p. 11
  • Space-time overhead counts the time steps for each measurement cycle, and the estimate pessimistically assumes all steps are used even when verification rejects a state early.Additional qubits are included in the overhead scheme to minimize time cost.Source: §IV · p. 11
  • Because controlled-Hadamard circuits contain T gates, the authors use a simulation approximation rather than Gottesman-Knill propagation and do not propose applying twirling operations.The approximation is used to enable classical simulation; the authors note twirling could reduce performance.Source: §IV · pp. 11–13
  • At p=10^-4, the d=5 protocol uses 68 qubits on average for pL=3.6×10^-8, while d=7 uses 231 for pL=4.9×10^-10.The table reports logical error rate and average qubit count; the d=7 data use extrapolation from five points at p∈[3×10^-4,4×10^-4].Source: Table I · p. 12, §IV · pp. 12–13
  • The resource estimates use 10^9 Monte Carlo simulations, and very low logical failure rates are obtained by extrapolating a best-fit curve.The reported sweep spans p∈[10^-4,5×10^-4].Source: §IV · pp. 12–13
  • For pL=3.6×10^-8, the reported space-time overhead is at least an order of magnitude lower than Ref. after accounting for its six stabilizer-measurement time steps.The authors caution that the space-time values cannot be compared directly without this adjustment.Source: §IV · p. 13

V. PREPARING |H⟩WITH ENCODED STABILIZER OPERATIONS

The scheme prepares |H⟩ states using stabilizer operations encoded in a distance-d2 triangular color code, growing initially prepared |H⟩d1 states when d1 < d2. The authors report low logical failure rates with quantified qubit and space-time costs, while noting assumptions and limits in the estimates.

V. PREPARING |H⟩WITH ENCODED STABILIZER OPERATIONS

  • The protocol selects d1 so |H⟩d1 has a lower logical error rate than distance-d2 encoded stabilizer operations, then grows the states to d2 when d1 < d2.The grown states are used with stabilizer operations encoded in the distance-d2 triangular color code.Source: §V · pp. 13–14
  • Growing measures operators on intervening white plaquettes and repeats distance-d2 plaquette measurements d1 times to correct errors and distinguish measurement errors from random outcomes.The described G(d1→d2) procedure prepares a stabilizer state and measures white-plaquette operators that anticommute with weight-two generators.Source: §V · p. 14, Figure 13 · p. 15
  • The average-qubit estimate assumes the |H⟩d1 preparation qubits can be reused for T gates and that preparing |H⟩d2 takes no longer than prior encoded operations.For fixed p, mdf is chosen to minimize the overhead expression.Source: §V · p. 16
  • The simulations pessimistically add a failure at each logical Clifford gate location, making the reported Table II logical failure rates upper bounds on full-cycle values.The paper describes Pauli-frame updates over a full distance-d2 color-code cycle.Source: §V · p. 17
  • The surface-code alternative assumes lattice surgery does not change the quality of grown color-code states, and a careful overhead analysis is left for future work.The required surface-code distance depends on df; for p = 10^-3 and pL(df) ≤ 10^-15, the stated distances are 15, 13, and 11 for df = 3, 5, and 7, respectively.Source: §V · p. 17
  • At p = 10^-4, the d1 = 7, d2 = 11, df = 3 scheme averages 10,917 qubits and 3.91×10^6 space-time overhead for pL(df) < 4×10^-15.The table reports overhead for schemes using encoded Clifford gates.Source: §V · p. 17, Table II · p. 18
  • 6,288 qubits is the minimum reported for pL(df) < 4×10^-15; Ref. required 16,400 qubits for a 2.4 × 10^-15 logical failure rate.The paper presents the comparison as qubit counts at different logical failure rates.Source: §V · p. 17, Table II · p. 18

VI. CONCLUSION AND OUTLOOK

The paper presents a nearest-neighbor triangular color-code scheme for fault-tolerant |H⟩-state preparation, using flag qubits and redundant ancilla encoding. It reports low-qubit preparation under circuit-level noise and identifies acceptance rates and larger-distance flag circuits as open trade-offs.

VI. CONCLUSION AND OUTLOOK

  • The scheme uses flag qubits and redundant ancilla encoding to measure local color-code stabilizers and a global operator without changing the qubit layout.The authors describe the architecture as fault-tolerant and requiring nearest-neighbor interactions.Source: §VI · p. 18
  • At p = 10^-4, 68 and 231 qubits yield encoded |H⟩ states with logical error rates of 3.6 × 10^-8 and 4.9 × 10^-10, respectively, under full circuit-level depolarizing noise.The scheme uses two-dimensional color codes and nearest-neighbor interactions.Source: §VI · p. 18
  • Encoded stabilizer operations can have error rates commensurate with injected magic states, unlike distillation’s assumption that code distances are chosen for successive rounds to improve fidelity.The authors characterize their circuit-prioritized approach as bottom-up, in contrast with distillation’s top-down approach.Source: §VI · p. 18
  • The study uses triangular color codes; the authors identify the 4.8.8 color-code family as a possible alternative for potentially better performance.Their encoded Clifford stabilizers use two ancillas for weight-four and three for weight-six stabilizers; edge-weight renormalization could reduce ancilla requirements while maintaining full effective code distance.Source: §VI · pp. 18–19
  • For encoded stabilizer operations with the surface code, the distance-7 scheme was optimal at p = 10^-4 and p = 10^-3; a fault-tolerant v-flag circuit with v ≥ 4 could support distance-9-or-greater schemes.The authors identify developing such a circuit as future work that could potentially reduce overhead further.Source: §VI · p. 19
  • The preparation schemes are error-detection schemes, and at p = 10^-3 with df > 3, acceptance can be low, reaching 12% for df = 5.The authors discuss bosonic-code concatenation or color-code error correction as possible alternatives; the latter would avoid postselection but may have higher logical error rates.Source: §VI · p. 19
  • The authors conclude that hardware constraints built into the schemes make them a potential route toward low-overhead universal computation on near- and long-term devices.This is presented as the authors’ outlook.Source: §VI · p. 19

Appendix A: Non fault-tolerant |H⟩state preparation scheme

The appendix analyzes two non-fault-tolerant growing schemes that convert physical or encoded inputs into larger triangular color-code encodings. Measuring the specified stabilizers and applying outcome-dependent corrections yields the intended encoded state.

Appendix A: Non fault-tolerant |H⟩state preparation scheme

  • For distance 5, the initial stabilizer state is stabilized by 14 of the code’s 18 generators, and the scheme measures the four missing generators.The missing generators are represented by the white plaquettes in Fig. 15a.Source: Appendix A · p. 19
  • The distance-5 scheme grows a physical input α|0⟩ + β|1⟩ into the corresponding encoded state, while the distance-7 scheme grows a distance-3 encoded input into distance 7.Figure 15 depicts both layouts; the distance-5 and distance-7 outputs are supported by the corresponding derivations.Source: Appendix A · pp. 19, 21, Figure 15 · p. 20
  • After the distance-5 measurements, outcome-dependent corrections are determined by minimum-weight perfect matching on the matching graph, leaving the intended encoded state.The derivation identifies the product X1X3X5X11X15 as the distance-5 code’s logical X operator.Source: Appendix A · pp. 20–21
  • For distance 7, the prepared stabilizer state is stabilized by 24 of 36 code generators and six weight-2 stabilizers before the growing measurements.The scheme measures six distance-7 stabilizers, including three X-type and then three Z-type stabilizers, with outcome-dependent corrections.Source: Appendix A · p. 21
  • For the distance-7 growth, minimum-weight perfect matching on the distance-7 graph determines corrections, and the derivation concludes with the desired encoded state.The input is encoded at distance 3 and the output at distance 7.Source: Appendix A · pp. 21–22

Appendix B: Proof of fault-tolerance for the |H⟩ state preparation scheme in Section III.

Appendix B argues that pairing the H(d)_m and EC(d) circuits makes the |H⟩ preparation fault-tolerant. It establishes the guarantee for triangular color codes up to distance seven.

Appendix B: Proof of fault-tolerance for the |H⟩ state preparation scheme in Section III.

  • The protocol’s t-fault-tolerance conditions require output errors of weight at most s and ideal decoding to reproduce the fault-free preparation result when s ≤ t.Ideal decoding is defined as a round of fault-free error correction.Source: Appendix B · p. 22
  • The proof applies to triangular color-code distances no greater than seven, since H(d)_m circuits are valid for d ∈ {3, 5, 7}.Source: Appendix B · p. 22
  • For an input X error, the ancilla outcomes yield either the desired |H⟩ state or an error branch, each with 50% probability; an input Y error forces −1 and yields Y|H⟩.The X-error branch is conditioned on the X-basis ancilla measurement.Source: Appendix B · pp. 22–23
  • Repeating H(d)_m and EC(d) in pairs at least (d − 1)/2 times ensures a fault-free pair when the total fault count is at most (d − 1)/2.The pairing matters because an error may otherwise yield a trivial syndrome with 50% probability during error correction.Source: Appendix B · p. 23
  • With at most t faults, accepted +1 outcomes from fault-free circuit pairs cannot produce an uncorrectable error, and the final error has weight at most s and is correctable.Here t = (d − 1)/2; the paired H(d)_m and EC(d) rounds are t-flag circuits.Source: Appendix B · pp. 22–23

Appendix C: Twirling approximation

Appendix C uses noise twirling to justify the simulations’ treatment of non-Pauli errors after T and T† gates. It does not propose twirling as a physical protocol step.

Appendix C: Twirling approximation

  • Noise twirling converts a non-Pauli error after T or T† into an incoherent mixture of Pauli errors, justifying the simulation approximation rather than adding a protocol operation.The authors note that physically twirling after these gates can reduce scheme performance.Source: Appendix C · p. 23, Figure 17 · p. 24
  • An input Z error through T becomes the coherent Hadamard error H = (X + Z)/2.Source: Appendix C · p. 23, Figure 17 · p. 24
  • Randomly chosen Y(θ) and Y(−θ) rotations around a noisy T gate, with θ uniform on [0, 2π], make that error an incoherent Pauli mixture.Source: Appendix C · p. 23, Figure 17 · p. 24
Loading 2003.03049v1…