PaperlayerView exact revision on arXiv

Source-linked AI summary

Improved Transversal Non-Clifford Gates from Cup Products

Louis Golowich, Itzhak Tamo, Guanyu Zhu

arXiv:2609.27801v1quant-phcs.IT

TL;DR

Efficient fault-tolerant non-Clifford gates remain a bottleneck because they require specialized codes or distillation schemes with large space-time overhead. The paper maps classical codes to quantum codes with transversal gates and reports constant-stabilizer-weight constructions with arbitrarily small magic-state overhead exponent γ>0.

  • Problem

    Fault-tolerant non-Clifford gates require specialized codes or distillation schemes that incur large space-time overhead.

    Source: §1 · p. 3

  • Method

    The authors map classical codes with appropriate properties to quantum codes with transversal gates, then instantiate the mapping using a constructed family based on high-dimensional tensor products.

    Source: §1 · p. 4

  • Results

    The first known constant-stabilizer-weight construction supports constant-depth transversal CCZ gates beyond Equation (1) and achieves arbitrarily small γ>0.

    Source: §1 · pp. 4–5

  • Takeaways & Limitations

    The construction reaches arbitrarily small magic-state overhead exponent γ>0 with constant stabilizer weight, unlike the polylogarithmic stabilizer weight of [GL25].

    Source: §1 · p. 5

    Using Theorem 1.3 to construct polynomial-distance codes with linear logical yield and constant stabilizer weight requires polynomial-distance constant-rate classical LDPC codes with a multiplication property, whose construction remains open.

    Source: §1.2 · p. 10

Abstract

from arXiv · show

It is a major challenge in quantum fault-tolerance to obtain low-overhead protocols for performing non-Clifford gates. In this vein, we construct quantum codes with low-weight stabilizers that support transversal (i.e. low-depth) implementations of the non-Clifford $C^{r-1}Z$ gate, for every constant $r\geq 3$. In particular, we obtain length-$n$ quantum LDPC codes (with constant-weight stabilizers) of polynomial distance $d\geq n^{(1-ε)/r}$ supporting transversal $C^{r-1}Z$ gates on a close-to-linear number $k\geq n^{1-ε}$ of disjoint tuples of logical qubits, for arbitrarily small $ε>0$. Our construction is the first with constant-weight stabilizers that obtains $dk\gg n$, and as a consequence achieves arbitrarily small magic state overhead exponent $γ=\log(n/k)/\log(d)>0$. Comparable prior constructions instead required at least polylogarithmic stabilizer weight. We also show how to obtain linearly many $k=Ω(n)$ logical $C^{r-1}Z$ gates, though with stabilizer weight and physical circuit depth $n^ε$. We show that our transversal gates also support addressing (i.e. targeting) of specific logical qubits. To obtain our codes, we develop a general transformation based on cup products that maps classical codes satisfying a multiplication property to quantum codes with transversal $C^{r-1}Z$. We apply this transformation to a new family of classical Tanner codes that we construct from punctured tensor products of algebraic codes.

1 Introduction

The paper targets low-overhead fault-tolerant non-Clifford gates by constructing qLDPC codes with transversal C^(r-1)Z gates via a classical-to-quantum mapping instantiated with punctured algebraic tensor-product Tanner codes. It also derives efficient adversarial-error decoding from classical tensor-product decoders and identifies open directions for improving distance, logical yield, and noise-model coverage.

1 Introduction

  • For every r≥3, the construction yields constant-weight codes with depth-1 transversal C^(r-1)Z gates that surpass the prior bound and decode n^(1−ε)/r adversarial errors in polynomial time.The construction has length n and alphabet size q.Source: §1 · p. 4
  • A second construction achieves logical yield Ω(n), with stabilizer weight and transversal circuit depth at most n^ε, and supports addressed gates without changing those bounds.It also has a polynomial-time decoder correcting Ω(n^(1/r)) adversarial errors.Source: §1 · p. 5
  • Theorem 1.1 gives the first constant-stabilizer-weight codes with arbitrarily small magic-state overhead exponent γ>0, improving on [GL25].The codes are subsystem codes: gauge qudits and logical qudits outside the selected gate tuples must be fixed to |0⟩.Source: §1 · pp. 5–6

1.1 Our Techniques

  • The techniques proceed in two stages: map classical Tanner codes with a multiplication property to quantum codes, then instantiate the map using punctured tensor products of algebraic codes.The described instantiation focuses on constant-degree Tanner graphs; the techniques also generalize to growing-degree graphs.Source: §1.1 · p. 7

1.1.1 General Classical-to-Quantum Mapping

  • If each Tanner code has distance at least d and an information set containing M, the mapping gives quantum codes of length Θ(|V(Γ)|^r), distance Ω(d), and transversal-gate logical yield |M|^r.Cup products extend the component-wise multiplication property to tensor-product complexes, with the resulting yield bound following from the property on each factor.Source: §1.1.1 · pp. 7–8

1.1.2 Instantiating the General Mapping

  • The authors construct new constant-check-weight Tanner codes with a multiplication property, addressing the difficulty that high-distance local codes with this property have rate at most 1/2.They puncture tensor powers of algebraic codes to express them as Tanner codes while retaining their properties and parameters up to a small loss; prior constructions needed super-constant check weight for close-to-linear dimension.Source: §1.1.2 · p. 9

1.1.3 Efficient Decoding Algorithm

  • Known decoders for classical tensor products yield efficient adversarial-error decoders for the quantum codes.The puncturing makes the classical codes a disjoint union of a small number of unpunctured tensor-product codes, each decodable with known algorithms.Source: §1.1.3 · p. 9

1.2 Directions for Future Work

  • Improving Theorems 1.1 and 1.2 to near-linear distance and testing decoding under locally stochastic noise remain open directions.The paper highlights locally stochastic noise in particular for its relevance to constant space-time overhead magic-state preparation.Source: §1.2 · pp. 9–10
  • A polynomial-distance, constant-rate classical LDPC code with a multiplication property remains an open prerequisite for constant-weight codes with linear logical yield.Theorem 1.2 provides linear logical yield at the cost of super-constant stabilizer weight and transversal circuit depth; the desired code could enable constant space-time overhead magic-state preparation under locally stochastic noise.Source: §1.2 · p. 10
  • Near-linear distance via balanced products remains open for these Tanner codes while preserving high-yield transversal gates; [LLL26] obtained near-linear distance but only constant logical yield.Existing near-linear-distance techniques apply to Tanner codes with strongly expanding local codes, and adapting them to this construction remains unresolved.Source: §1.2 · p. 10

1.3 Roadmap

  • The paper proceeds from preliminaries to the cup-product mapping, then to punctured-tensor Tanner codes and their specific instantiations.Section 3 proves Theorem 1.3, Section 4 constructs the classical code family, and Section 5 gives instantiations.Source: §1.3 · p. 10

2 Preliminaries

The preliminaries establish the classical, quantum, circuit, and cochain-complex tools used to describe quantum codes and decoding, and relate Tanner codes on graphs to 0-cocycle spaces so that distance and decoding guarantees transfer between them.

2.1 Classical Codes

  • Tensor products of [n_i, k_i, d_i]_q classical codes have parameters [n_1n_2, k_1k_2, d_1d_2]_q, and their component decoders yield a decoder of radius ρ_1ρ_2 and time n_1T_2 + n_2T_1.A classical code’s parameters are its length, dimension, and minimum nonzero-word weight.Source: §2.1 · pp. 10–11

2.2 Quantum Codes and Transversal Gates

  • Subsystem CSS codes specify protected logical qudits and use low-weight commuting stabilizers, potentially improving distance by excluding easily corrupted logical qudits.The paper distinguishes these stabilizers from high-weight checks decomposed into noncommuting gauge operators, which may be difficult to measure fault-tolerantly [BFHS17].Source: §2.2 · p. 12
  • A physical circuit induced by a multilinear form of sparsity w has depth at most rw, and cohomology-invariance ensures it maps valid code states to valid states.The form applies a physical C^{r-1}Z gate across each r-tuple of qudits; its induced logical form determines the available logical gates.Source: §2.2 · pp. 12–13, Such cohomology-invariance implies a… · p. 13

Such cohomology-invariance implies a well-defined induced multilinear form

  • The subrank of the induced logical form gives the maximum number of disjoint logical C^{r-1}Z gates, while subsystem codes define the protected logical spaces on which yield is measured.The form must be cohomology-invariant and have sparsity w for the subsystem codes to support a transversal gate of sparsity w and logical yield s.Source: Such cohomology-invariance implies a… · p. 13

2.3 Quantum Codes from Cochain Complexes

  • For a tensor-product cochain complex C = A ⊗ B, decodable H0(A) and H^{rB}(B) yield a subsystem code with a radius-ρ decoder running in poly(T, |C|) time.The construction uses a subsystem drawn from H0(A) ⊗ H^{rB}(B); the paper builds its codes from tensor products of 1-dimensional complexes associated to classical Tanner codes.Source: §2.3 · pp. 15–16
  • Under bipartite orientation or characteristic 2, the Tanner code is isomorphic to the 0-cocycle space, whose distance is at least 2d/Δ when the Tanner code has distance d and the graph has maximum degree Δ.The isomorphism maps each Tanner-code word to a 0-cocycle whose local edge values agree at both endpoints.Source: §2.3 · pp. 16–17
  • A radius-ρ, time-T Tanner-code decoder yields a radius-ρ/Δ, time-(T + O(Δ^3|V(Γ)|)) decoder for the 0-cocycle space.The transfer uses the graph map between cocycles and edge vectors before decoding.Source: §2.3 · p. 16

3 High-Yield Transversal Gates via Multiplication Property

The section constructs quantum codes with transversal C^{r−1}Z gates from classical Tanner codes, using cup products to carry multiplication structure to cohomology. The construction gives bounds on gate sparsity, logical yield, locality, distance, and decoding.

3 High-Yield Transversal Gates via Multiplication Property

  • The section presents a general construction from products of classical Tanner codes and extends it to addressable gates targeting chosen subsets of logical qudits.The addressable-gate extension is described in Appendix A.Source: §3 · p. 17

3.1 Result Statement

  • The construction yields transversal C^{r−1}Z gates with sparsity ≤(4∆)^{r2} and logical yield ≥|M|^r.The associated subsystem codes have locality ≤r∆^2, X-distance at least d(r), and Z-distance at least (2/∆)^{r−1}·d(1)d(2)…d(r−1).Source: §3.1 · p. 18

3.2 Cup Products

  • Cup products satisfying the Leibniz rule induce well-defined bilinear forms on cohomology, making them suitable for the code construction.The section defines cup products on Tanner code complexes and explains that changing cocycles by coboundaries changes their product only by a coboundary.Source: §3.2 · pp. 18–19

3.3 Proof of Theorem 3.1

  • The proof constructs a cohomology-invariant form whose restriction has logical yield at least |M|^r and whose sparsity is at most (4∆)^{r2}.It also establishes the distance and decoder bounds stated for the subsystem codes.Source: §3.3 · pp. 20–23

4 Classical Tanner Codes with Multiplication Property

The section constructs Tanner codes with large dimension even when their local codes have rate below 1/2, then uses their tensor-product structure to establish code parameters and decoding guarantees.

4 Classical Tanner Codes with Multiplication Property

  • Theorem 4.1 gives a bipartite graph of maximum degree 2n whose associated Tanner code has parameters determined by the local codes.The local codes are puncturings of selected input codes; the construction also transfers decoder guarantees from restricted local codes.Source: §4 · p. 24

4.1 Proof of Theorem 4.1

  • The construction makes the Tanner code a puncturing of a tensor product, so its dimension, distance, and decoding bounds follow from that tensor code.The graph is built from intersecting columns in a t-dimensional grid, with selected coordinate ranges defining its vertices and edges.Source: §4.1 · p. 24

Then there is an isomorphism

  • The restriction map from the tensor product code to the Tanner code is an isomorphism when each input code has distance greater than n.The proof establishes injectivity from the distance condition and extends Tanner-code words to prove surjectivity.Source: Then there is an isomorphism · pp. 25–26
  • The Tanner code’s distance is at least the product of the input distances reduced by n, and local decoders combine into a decoder for the full code.The decoder radius is the product of the local radii, and its running time is the product of the local decoding times.Source: §4 · p. 24, Then there is an isomorphism · p. 27

5 Instantiations of High-Yield Transversal Gates

The paper instantiates its transversal-gate construction with algebraic Tanner codes to obtain high-yield codes across several locality regimes. The instantiations trade locality against distance and logical yield.

5 Instantiations of High-Yield Transversal Gates

  • Locality O_{r,ϵ}(1) codes support transversal C^{r−1}Z gates with logical yield at least N^{1−ϵ}.The codes have alphabet size q=p^u for u=O_r(1) and radius-Ω_{r,ϵ}(N^{(1−ϵ)/r}) time-poly(N) decoders.Source: §5 · p. 27
  • Polylogarithmic locality improves the distance to N^{1/r}/poly(log N), while retaining logical yield at least N^{1−ϵ}.The construction uses slowly growing factor codes; their locality and gate sparsity are polylogarithmic in N.Source: §5 · pp. 27–28
  • The linear-yield construction reaches logical yield Ω_{r,ϵ}(N) with locality and gate sparsity N^ϵ.Its decoder has radius Ω_{r,ϵ}(N^{1/r}) and runs in polynomial time.Source: §5 · p. 28, §5.2 · p. 31

5.2 Tanner Code Instantiations

  • The Tanner-code instantiations apply the quantum construction to codes whose factor codes satisfy the required multiplication property.The section uses Reed-Solomon and algebraic geometry codes as factor codes for the Tanner construction.Source: §5.1 · p. 28, §5.2 · pp. 29, 31

5.1 Algebraic Classical Codes

  • The algebraic geometry input codes have dimension at least n/4r, distance at least 3n/2, and product-code distance at least 3n/2.The restricted codes also have radius-n/4 time-poly(n) decoders.Source: §5.1 · p. 29

A Addressable Gates

The paper extends its construction to addressable transversal gates, allowing the logical tuples targeted by a gate to vary. It provides both a control-block route and an extension that retains the original distance scale.

A Addressable Gates

  • Addressability means applying gates to arbitrary subsets of a pre-specified collection of logical r-tuples in a fixed basis.One route uses a transversal C^rZ gate with an extra control block to induce addressable C^{r−1}Z gates.Source: A Addressable Gates · p. 36
  • Using a control block reduces the distance scale from O(N^{1/r}) to O(N^{1/(r+1)}) for addressable C^{r−1}Z gates.The paper modifies its construction to restore the O(N^{1/r}) distance scale while retaining addressability.Source: A Addressable Gates · p. 36
  • Theorem A.2 gives addressable C^{r−1}Z gates with sparsity at most (4Δ)^{r2} and logical yield at least |M|^r.It also specifies locality, X- and Z-distance bounds, and a decoder radius in terms of the input Tanner codes.Source: A Addressable Gates · p. 36
  • The addressable construction applies to the paper’s Tanner-code instantiations, retaining their parameters up to changes in hidden constants.The cited instantiations use Reed-Solomon and algebraic geometry codes with multiplication properties for constant r.Source: A Addressable Gates · pp. 37–38
Loading 2609.27801v1…