PaperlayerView exact revision on arXiv

Source-linked AI summary

Universal fault-tolerant gates on concatenated stabilizer codes

Theodore J. Yoder, Ryuji Takagi, Isaac L. Chuang

arXiv:1603.03948v2quant-ph

TL;DR

Universal transversal logical gates are ruled out, and magic-state approaches can carry substantial overhead. This paper uses intermediate error-correction to construct fault-tolerant non-transversal gates on stabilizer codes. The constructions yield universal gate sets for small codes and sufficient conditions for extending pieceable universality to larger codes.

  • Problem

    No quantum code supports universal transversal logical circuits, while magic-state distillation can incur large time and qubit overheads.

    Source: §I · p. 1

  • Method

    The paper breaks non-transversal logical circuits into pieces and uses intermediate error-correction to control error propagation.

    Source: §I · p. 1

  • Results

    Pieceable constructions give universal gate sets on the 5-qubit and 7-qubit codes without functional ancillas, and nondegenerate codes with fault-tolerant local Clifford gates can be promoted to universality.

    Source: §I · p. 2

  • Takeaways & Limitations

    Pieceable fault-tolerance also supports gates between different codes, providing a method of code switching.

    Source: §I · p. 2

    The analysis is restricted to concatenated codes; for non-concatenated families, circuit-depth scaling and accumulation of noncontagious errors suggest a threshold may not exist.

    Source: §VI · p. 17

Abstract

from arXiv · show

It is an oft-cited fact that no quantum code can support a set of fault-tolerant logical gates that is both universal and transversal. This no-go theorem is generally responsible for the interest in alternative universality constructions including magic state distillation. Widely overlooked, however, is the possibility of non-transversal, yet still fault-tolerant, gates that work directly on small quantum codes. Here we demonstrate precisely the existence of such gates. In particular, we show how the limits of non-transversality can be overcome by performing rounds of intermediate error-correction to create logical gates on stabilizer codes that use no ancillas other than those required for syndrome measurement. Moreover, the logical gates we construct, the most prominent examples being Toffoli and controlled-controlled-Z, often complete universal gate sets on their codes. We detail such universal constructions for the smallest quantum codes, the 5-qubit and 7-qubit codes, and then proceed to generalize the approach. One remarkable result of this generalization is that any nondegenerate stabilizer code with a complete set of fault-tolerant single-qubit Clifford gates has a universal set of fault-tolerant gates. Another is the interaction of logical qubits across different stabilizer codes, which, for instance, implies a broadly applicable method of code switching.

I. INTRODUCTION

The introduction frames universal fault-tolerant computation as a challenge because transversal gates cannot be universal, while magic-state methods incur substantial overhead. The paper introduces pieceable fault-tolerance and previews constructions for small codes and general conditions for extending them.

I. INTRODUCTION

  • Fault-tolerant logical circuits perform operations directly on encoded data, avoiding the risky procedure of decoding, operating, and re-encoding.A circuit is fault-tolerant when one faulty component never causes an uncorrectable encoded-data error.Source: §I · p. 1
  • No quantum code has a universal set of transversal logical circuits, and magic-state distillation is one commonly used alternative with large time and qubit overheads.Other approaches include code switching, gauge-based methods, and concatenated codes.Source: §I · p. 1
  • Rounds of intermediate error-correction let non-transversal logical circuits remain fault-tolerant, forming the paper’s pieceable approach.The approach generalizes an earlier controlled-S construction and is developed for other codes.Source: §I · pp. 1–2
  • The 5-qubit and 7-qubit codes obtain universal gate sets including pieceable CCZ gates, without functional ancillas or magic states.The paper reports that the 7-qubit construction compares favorably with magic-state injection in resources; its circuits are 1-fault-tolerant, and concatenation yields a threshold.Source: §I · p. 2
  • For larger codes, nondegeneracy is sufficient for pieceably fault-tolerant gates, and nondegenerate codes with fault-tolerant local Clifford gates can achieve universality.The paper also extends this result to nondegenerate CSS codes and describes gates between different codes as a method of code switching.Source: §I · p. 2

B. Circuits, faults, and fault-tolerance

This section motivates pieceable fault-tolerance as a way to control error spread in circuits that are not fault-tolerant as a whole. It defines the method as dividing a logical circuit into pieces with error-correction between them, while distinguishing functional from error-correction ancillas.

B. Circuits, faults, and fault-tolerance

  • Fault-tolerant circuit design limits how many qubits a single fault can affect within a code block, with t-transversality sufficient when t < d/2.For distance-three codes, 1-transversality is the essential design condition described here.Source: B. Circuits, faults, and fault-tolerance · p. 4

C. Pieceable fault-tolerance

  • Intermediate correction can limit error propagation enough to make some non-Clifford circuits fault-tolerant, even when the full circuit is not.The approach generalizes an idea used in fault-tolerant code switching.Source: C. Pieceable fault-tolerance · p. 4
  • Pieceable fault-tolerance divides a logical circuit into pieces and inserts code-state-preserving error-correction between them, requiring the modified circuit to be fault-tolerant.The constructions use no functional ancillas, though additional pieces can require more error-correction ancillas.Source: C. Pieceable fault-tolerance · p. 4
  • When intermediate stabilizers are non-Pauli, correction requires care because the quantum error-correcting conditions alone do not guarantee suitable circuitry.The correction must remove needed errors without introducing errors that cannot be corrected in the next round.Source: C. Pieceable fault-tolerance · p. 4
  • Intermediate error-correction need not fix every error immediately, provided errors passed onward remain correctable in a later round.The final error-correction is included before judging fault-tolerance against the ideal code correction.Source: C. Pieceable fault-tolerance · pp. 4–5
  • Pieceable circuits provide a simpler two-piece CZ for the 5-qubit code and support CCZ constructions that complete universal gate sets on both small codes.The 5-qubit code already has transversal single-qubit Cliffords; the 7-qubit construction is developed in the next section.Source: C. Pieceable fault-tolerance · p. 5

D. Additional pieceable concepts

Intermediate correction must control errors that can spread through later circuit pieces, including when stabilizers become non-Pauli. The section develops constant-stabilizer-based safeguards, adaptive correction, and round-robin circuit design.

D. Additional pieceable concepts

  • Intermediate correction aims to remove contagious errors while allowing only noncontagious and single-qubit errors into the next circuit piece.The constant stabilizer supports this goal because its members remain Pauli throughout the circuit and can be measured fault-tolerantly with CAT states.Source: D. Additional pieceable concepts · p. 5
  • When constant stabilizers detect a fault, adaptive correction measures nonconstant stabilizers to identify and correct the error; without detection, errors pass through uncorrected.This uses the constant stabilizers to provide a reliability guarantee for measuring nonconstant stabilizers.Source: D. Additional pieceable concepts · p. 5
  • A fault in the CCZ-based measurement of a non-Pauli operator can cause two code-qubit errors, generally uncorrectable for distance-three codes.This is why measurement of non-Pauli operators requires particular care.Source: D. Additional pieceable concepts · p. 6
  • PARSEC measures constant stabilizers, partially corrects errors to establish commutation guarantees, measures nonconstant stabilizers, then completes recovery.The procedure’s name is Procedure for Adaptive, Reliable Stabilizer Error-Correction.Source: D. Additional pieceable concepts · p. 6
  • Round-robin design applies a gate across disjoint qubit sets, and the paper uses this design for its new pieceable logical constructions.The construction assumes the gates in the product commute; participating qubits are active and other non-ancilla qubits are idle.Source: D. Additional pieceable concepts · p. 6

III. THE 5-QUBIT CODE

The section turns to concrete logical-gate design on the smallest distance-3 quantum code. It establishes the 5-qubit code’s transversal Clifford baseline, including octahedral gates and a permuted Hadamard.

III. THE 5-QUBIT CODE

  • The 5-qubit code is the smallest distance-3 quantum code and serves as the setting for these concrete pieceable-gate examples.The section introduces examples including contagious errors, constant stabilizers, PARSEC, and round-robin circuits.Source: §III · p. 6, A. Transversal gates · p. 6

A. Transversal gates

  • All eight single-qubit octahedral gates are transversal on the 5-qubit code, including K = SH.The paper identifies K = SH as a special case of the octahedral-gate family.Source: A. Transversal gates · p. 7
  • A logical Hadamard is implemented as H = PπH^⊗5, with Pπ realized by relabeling qubit lines.The paper notes that permutations alone do not bypass the universality-transversality no-go theorem for stabilizer codes.Source: A. Transversal gates · p. 7
  • Gottesman’s route completes fault-tolerant Clifford operations using a transversal three-qubit Clifford gate T3, measurement, and single-qubit Clifford gates.Implementing logical CX this way requires a third 5-qubit code block of five functional ancilla qubits, which is measured and discarded.Source: A. Transversal gates · p. 7

B. Pieceably fault-tolerant CZ

The 5-qubit-code CZ construction splits a non-transversal circuit into pieces separated by error correction. Its round-robin design supports correction of single-component faults, and the section also gives a four-piece logical CCZ construction.

B. Pieceably fault-tolerant CZ

  • The 5-qubit logical CZ uses a two-piece circuit with no functional ancillas and intermediate error correction between its pieces.The circuit is shown as Ca followed by Cb, with correction after Ca.Source: B. Pieceably fault-tolerant CZ · p. 7, Figure 3 · p. 8
  • The design also yields a four-piece fault-tolerant logical CCZ on the 5-qubit code.Source: B. Pieceably fault-tolerant CZ · p. 7
  • Local Clifford gates map both blocks to equivalent 5′-qubit codes, then a nine-CZ round-robin circuit preserves their combined stabilizer.The round-robin circuit acts on the active qubits of each block.Source: B. Pieceably fault-tolerant CZ · p. 7
  • Breaking the round-robin circuit after six CZ gates with no qubit touched more than twice makes its pieces 2-transversal and limits propagation to at most two known locations per block.Errors restricted to two known locations are correctable in the 5-qubit code.Source: B. Pieceably fault-tolerant CZ · p. 7
  • Intermediate syndromes distinguish contagious errors in both blocks, one block, or neither, enabling correction of the resulting errors, including two located errors per block.The procedure measures stabilizers of the intermediate code after the first circuit piece.Source: B. Pieceably fault-tolerant CZ · pp. 7–8
  • The intermediate procedure uses 84 non-trivial syndromes out of 255 possible.The unused syndromes do not correspond to errors from one faulty component in the standard model, though some can correct errors from two faulty components.Source: B. Pieceably fault-tolerant CZ · p. 8
  • After the second piece, final error correction can use two copies of canonical 5-qubit error correction because that piece is 1-transversal.Source: B. Pieceably fault-tolerant CZ · p. 8

C. T will always require functional ancillas

A fault-tolerant T gate cannot be implemented on the 5-qubit code without functional ancillas, even using intermediate error correction. By contrast, pieceable CCZ completes a universal gate set on that code without functional ancillas, using four pieces and adaptive intermediate correction.

C. T will always require functional ancillas

  • A fault-tolerant T gate on the 5-qubit code requires functional ancillas because its final multi-qubit gate can introduce uncorrectable errors.The argument uses the code’s perfect-code property; the same conclusion is stated for the 7-qubit code.Source: C. T will always require functional… · p. 9

D. Pieceably fault-tolerant CCZ

  • Four 2-transversal pieces with intermediate error correction implement pieceably fault-tolerant CCZ on the 5-qubit code, completing its universal gate set without functional ancillas.The construction uses adaptive PARSEC correction because the intermediate code space is no longer a stabilizer code.Source: D. Pieceably fault-tolerant CCZ · pp. 9–10
  • PARSEC corrects contagious errors by measuring constant stabilizers, then uses triggered syndromes to identify and correct errors in affected blocks.When constant stabilizers do not trigger, nonconstant stabilizers are not measured; possible Z errors can be left for final correction because they do not propagate further.Source: D. Pieceably fault-tolerant CCZ · pp. 10–11
  • The 5-qubit CCZ circuit recovers from one faulty component, and concatenating it k times is proposed to tolerate up to 2k −1 faults.Its physical components can be implemented logically on the 5-qubit code without first compiling CCZ into one- and two-qubit gates.Source: D. Pieceably fault-tolerant CCZ · p. 11
  • For the 7-qubit code, the same PARSEC approach can be simplified because the code is CSS.The section identifies this as a generalization of the 5-qubit construction.Source: D. Pieceably fault-tolerant CCZ · p. 11

A. Transversal gates

The 7-qubit code has transversal H, S, and CNOT gates. A round-robin CCZ construction completes a universal gate set, with CSS-specific intermediate correction that avoids measuring non-Pauli stabilizers.

A. Transversal gates

  • The 7-qubit code has transversal H, S, and CNOT gates, giving it a complete set of transversal Clifford gates.Each gate is applied qubitwise across the seven physical qubits.Source: A. Transversal gates · p. 12

B. Pieceably fault-tolerant CCZ

  • A pieceable round-robin CCZ construction completes a universal gate set on the 7-qubit code.The construction follows the general framework used for the 5-qubit code and is optimized in the following section.Source: B. Pieceably fault-tolerant CCZ · p. 12
  • Intermediate correction uses constant stabilizers to locate contagious X errors, while noncontagious Z errors commute through to final correction.The CSS structure permits correction of one X error per block using only the first three stabilizers.Source: B. Pieceably fault-tolerant CCZ · p. 12
  • The 7-qubit construction corrects a single component failure without measuring non-Pauli stabilizers, using a procedure called CSS PARSEC.The paper identifies avoiding nonconstant-stabilizer measurements as a feature of its round-robin constructions on CSS codes.Source: B. Pieceably fault-tolerant CCZ · p. 12

C. A resource comparison against magic states

For logical CCZ on the 7-qubit code, the pieceable construction nearly halves resources relative to magic-state injection. The paper also gives sufficient conditions for pieceable gates on broader classes of stabilizer codes, including conditions that yield universality and code switching.

C. A resource comparison against magic states

  • The resource comparison evaluates ancillas consumed, multi-qubit gate counts, and circuit volume for pieceable CCZ and postselected magic-state injection.Circuit volume is defined as timesteps times active qubits.Source: C. A resource comparison against magic… · p. 12, Table I · p. 13
  • A 21-physical-CCZ design uses one intermediate correction, reducing the earlier 27-CCZ construction.The resource comparison uses the two-piece, 21-CCZ circuit, with Steane-state error correction assumed to succeed by postselection.Source: C. A resource comparison against magic… · p. 13
  • Pieceable CCZ on the 7-qubit code nearly halves required resources compared with magic-state injection.The comparison assumes postselections always succeed, which generally favors the magic-state method because failed postselection requires recomputing a large circuit volume.Source: C. A resource comparison against magic… · p. 13

V. CONDITIONS FOR PIECEABLE FAULT-TOLERANCE IN STABILIZER CODES

  • All nondegenerate stabilizer codes with distance at least three have a pieceably fault-tolerant gate locally Clifford-equivalent to ChZ.For codes with transversal local Clifford gates, this result is sufficient for universality.Source: §V · p. 13
  • The general constructions also work between blocks in different codes, implying a method of code switching with pieceable circuits.Source: §V · p. 13

A. Pieceable constructions in general

Round-robin circuits implement logical Γ-gates across stabilizer codes, and intermediate error-correction makes these constructions pieceably fault-tolerant. Under stated conditions, the required number of pieces has an explicit upper bound, with a distance-independent case for lowest-weight normalizers.

A. Pieceable constructions in general

  • For any h + 1 single-qubit stabilizer codes, a round-robin circuit, conjugated by local Clifford gates when needed, implements logical Γ(p).The construction puts each chosen logical operator in Z-form, applies round-robin controlled-Z gates on their supports, and reverses the Clifford gates; the single-qubit-per-block assumption can be relaxed.Source: A. Pieceable constructions in general · pp. 14, 16
  • Intermediate error-correction makes the round-robin circuits pieceably fault-tolerant by correcting contagious errors before they spread too far.PARSEC measures constant stabilizers first, then measures nonconstant stabilizers when a single block triggers; final correction uses recorded locations of possible spread.Source: A. Pieceable constructions in general · pp. 14–16
  • With distance d_j ≥ 3 and an error-correcting constant stabilizer for each logical p_j of weight w_j, a Γ(p) circuit needs at most the product of m_j divided by min_j m_j pieces, where m_j = ⌈w_j/(d_j − 1)⌉.The pieces are arranged so each qubit connects to at most d_j − 1 qubits in another block, allowing correction of contagious errors.Source: A. Pieceable constructions in general · p. 15
  • The general piece bound need not be optimal, and code-specific ordering of controlled-Z gates may exploit unused intermediate syndromes.The paper points to its improved 7-qubit-code construction as an example.Source: A. Pieceable constructions in general · p. 16
  • When lowest-weight normalizers wire the circuit, implementing an h + 1-qubit Γ-gate takes only 2h pieces, independent of code distance.The larger distance also permits more gates per piece under the connectivity constraint.Source: A. Pieceable constructions in general · p. 16

B. Universality through pieceable means

Pieceable Γ-gates supply fault-tolerant entangling operations that yield universality for several classes of nondegenerate stabilizer codes. The section also derives conditions for logical SWAPs between different codes and discusses where nondegeneracy is not required.

B. Universality through pieceable means

  • Any nondegenerate stabilizer code with a complete fault-tolerant set of logical local Clifford gates has a universal set of fault-tolerant logical gates.A nondegenerate code of distance at least three has a pieceably fault-tolerant implementation of at least one of Γ(ZZZ), Γ(XXX), or Γ(YYY), which can combine with a suitable local gate for universality.Source: B. Universality through pieceable means · p. 16
  • Any nondegenerate linear stabilizer code with distance d ≥ 3 has a fault-tolerant universal set of logical gates.The argument uses the transversal octahedral gates available to GF(4)-linear codes.Source: B. Universality through pieceable means · p. 17
  • Any nondegenerate CSS code with a fault-tolerant logical local Clifford gate has a universal set of fault-tolerant logical gates.The proof supplies pieceably fault-tolerant circuits for at least two of Γ(ZZZ), Γ(XXX), and Γ(YYY).Source: B. Universality through pieceable means · p. 17
  • A logical SWAP exists between two nondegenerate stabilizer codes if each is CSS with a logical local Clifford gate or has a complete fault-tolerant set of logical local Cliffords.The construction uses CX gates in both directions between the codes.Source: B. Universality through pieceable means · p. 17
  • Using an ancillary code block, the results also support code-switching schemes for universal computation with nondegenerate CSS codes and interactions between encoded qubits in the same block.The paper describes switching some qubits to ancillary blocks before interacting them.Source: B. Universality through pieceable means · p. 17
  • Nondegeneracy is sufficient but not necessary for error-correcting constant stabilizers; Shor’s 9-qubit code has them for some logical Z operators.Theorem V.2 requires error-correcting constant stabilizers rather than nondegeneracy itself.Source: B. Universality through pieceable means · p. 17

VI. CONCLUSION

The conclusion identifies open design questions for pieceable gates, including their use beyond concatenated codes and at higher fault tolerance. It also notes that systematic efficiency and threshold comparisons remain to be done.

VI. CONCLUSION

  • The authors leave open which additional gates can be implemented pieceably, how many functional ancillas they require, and how to implement universal gates between qubits in the same code block.Suggested targets include controlled-Hadamard, controlled-phase, and T gates.Source: §VI · p. 17
  • The universality conditions established in the paper are sufficient, not necessarily necessary, and the authors call for identifying more codes that support pieceable universality.Whether degenerate codes always admit pieceable Γ-gates remains an open question.Source: §VI · p. 17
  • The results are restricted to concatenated codes; for non-concatenated families such as surface codes, circuit-depth scaling and accumulating noncontagious errors suggest no threshold would exist.The authors describe lifting the concatenated-code restriction as important to investigate.Source: §VI · p. 17
  • The circuits recover from single faults regardless of code distance, and concatenation yields tolerance to arbitrary numbers of faults; extending t-fault-tolerant constructions to other codes remains open.Distance-d CSS codes can be pieced to be t-fault-tolerant using CSS PARSEC, while generalizing reliability guarantees for nonconstant-stabilizer measurements is posed as a question.Source: §VI · pp. 17–18
  • A complete comparison of thresholds, ancilla-qubit requirements, and circuit depth, along with rigorous threshold calculations, remains to be done.The supplied passage ends while introducing this efficiency discussion.Source: §VI · p. 18

Appendix A: Classical codes within quantum ones

The appendix associates each chosen logical normalizer with a classical code whose checks are the constant stabilizers. Its distance characterizes their ability to detect or correct contagious errors and supports the paper’s general fault-tolerance results.

Appendix A: Classical codes within quantum ones

  • The classical code C(p) induced by a normalizer p has parity checks given by rows corresponding to the constant stabilizers.The appendix obtains these checks after transforming p to Z-form and restricting the stabilizer representation to the support of p.Source: Appendix A · pp. 19–20
  • The constant stabilizer detects contagious errors exactly when C(p) has distance at least 2, and corrects them exactly when C(p) has distance at least 3.The classical errors in this correspondence are precisely the contagious errors associated with p.Source: Appendix A · p. 20
  • For a nondegenerate distance-d code and a minimum-weight logical normalizer p of weight d, the appendix’s lemmas establish an error-correcting constant stabilizer.The appendix relates existence and distance properties of C(p) to weight restrictions on normalizers and stabilizers.Source: Appendix A · p. 20
  • For nondegenerate CSS codes, the induced classical code for a normalizer in Z-form or X-form has distance at least the quantum-code distance d.This bound underlies the existence of two suitable anticommuting normalizers used for CSS-code universality.Source: Appendix A · p. 20

Appendix B: Nonstabilizer intermediate codes

The round-robin constructions considered here pass through nonstabilizer codespaces. A sufficient condition based on the transformed stabilizers and minimum-weight normalizers establishes this for intermediate codespaces that differ from the initial one.

Appendix B: Nonstabilizer intermediate codes

  • Intermediate codespaces that differ from the initial round-robin codespace are nonstabilizer under the stated minimum-weight-normalizer assumption for logical Γ-gates with h ≥ 2.The claim excludes round-robin CZ constructions; it assumes normalizers of minimum weight within their cosets.Source: Appendix B · p. 21
  • The proof shows that the transformed stabilizer projector cannot have stabilizer form by establishing that its Pauli decomposition contains terms with unequal coefficient magnitudes.The argument uses preserved constant stabilizers and a nonidentity G_jk containing multiple terms.Source: Appendix B · p. 21
  • A nonconstant stabilizer transformed into t_jkG_jk, with nonidentity G_jk a product of controlled-(h−1)-Z gates, certifies a nonstabilizer intermediate codespace.The lemma applies when the construction uses lowest-weight normalizers.Source: Appendix B · p. 21

Appendix C: Demonstrating pieceability beyond Theorem V.2

The appendix shows that fault-tolerant pieceability can implement logical CZ on Shor’s 9-qubit code even though Theorem V.2’s condition is not necessary. It also compares circuit resources for pieceable CCZ and postselected magic-state injection on the 7-qubit code.

Appendix C: Demonstrating pieceability beyond Theorem V.2

  • Pieceable CZ on Shor’s code shows that Theorem V.2’s condition is not necessary for fault-tolerant pieceable gates.The example puts the theorem’s 5- and 7-qubit code cases in context as convenient examples, not the limit of applicability.Source: Appendix C · p. 21
  • Three pieces are the minimum found for a fault-tolerant round-robin CZ on Shor’s code, and the order of gates within each piece matters.An exhaustive search over CZ-gate permutations and intermediate-correction placement found no fault-tolerant version with fewer pieces; the displayed implementation uses qubits 1, 2, and 3 from each block.Source: Appendix C · p. 22, Figure 6 · p. 22

Appendix D: Circuits for resource comparison

  • The authors expect the nearly 50% pieceable-CCZ improvement to persist despite possible optimizations to either circuit design.Reducing CAT-state size from four qubits to two is possible but increases circuit volume in the described magic-state preparation.Source: Appendix D · p. 22
  • 771 circuit-volume units for pieceable CCZ, versus 1518 for postselected magic-state injection, in the reported 7-qubit-code comparison.The pieceable total combines 21 physical CCZ gates with intermediate Z-stabilizer checks and final full Steane syndrome measurements; the injection total assumes classically controlled operations are not done.Source: Figure 7 · p. 23, Figure 12 · p. 25
Loading 1603.03948v2…