PaperlayerView exact revision on arXiv

Source-linked AI summary

Construction of the full logical Clifford group for high-rate quantum Reed-Muller codes using only transversal and fold-transversal gates

Theerapat Tansuwannont, Tim Chan, Ryuji Takagi

arXiv:2602.09788v4quant-ph

TL;DR

High-rate QECCs use fewer physical qubits per logical qubit at equal code distance, while universal logical computation using only transversal gates is ruled out. The authors construct addressable Clifford gates for quantum Reed–Muller codes using transversal and fold-transversal gates. This realizes the full logical Clifford group for the family and is the first known construction of this kind for codes whose logical-qubit count grows near-linearly with block length.

  • Problem

    High-rate QECCs use fewer physical qubits per logical qubit at equal code distance, but universal logical computation using only transversal gates is ruled out.

    Source: §1.1 · pp. 1–2

  • Method

    The paper builds phase-type fold-transversal gates from products of code automorphisms Q(i, j) to construct addressable gates for QRM(m).

    Source: §2.2 · p. 8, §3.1 · p. 18, §5 · p. 28

  • Results

    The construction realizes any addressable Clifford gate in the full logical Clifford group of quantum Reed–Muller codes using only transversal and fold-transversal gates.

    Source: §5 · p. 28

  • Takeaways & Limitations

    This is the first known such construction for a code family whose logical-qubit count grows near-linearly with block length.

    Source: §5 · p. 28

    For k = ω(√n log n), arbitrary logical Clifford implementation cannot be constant-depth, and whether compiled circuits attain Corollary 2's lower bound remains open.

    Source: §4 · pp. 27–28

Abstract

from arXiv · show

To build large-scale quantum computers while minimizing resource requirements, one may want to use high-rate quantum error-correcting codes that can efficiently encode information. However, realizing an addressable gate$\unicode{x2014}$a logical gate on a subset of logical qubits within a high-rate code$\unicode{x2014}$in a fault-tolerant manner can be challenging and may require ancilla qubits. Transversal and fold-transversal gates could provide a means to fault-tolerantly implement logical gates using a constant-depth circuit without ancilla qubits, but available gates of these types could be limited depending on the code and might not be addressable. In this work, we study a family of $[\![n=2^m,k={m \choose m/2}\approx n/\sqrt{\pi \log_2(n)/2},d=2^{m/2}=\sqrt{n}]\!]$ self-dual quantum Reed$\unicode{x2013}$Muller codes, where $m$ is a positive even number. For any code in this family, we construct a generating set of the full logical Clifford group comprising only transversal and fold-transversal gates, thus enabling the implementation of any addressable Clifford gate. To our knowledge, this is the first known construction of the full logical Clifford group using only transversal and fold-transversal gates without requiring ancilla qubits for a family of codes in which $k$ grows near-linearly in $n$.

1 Introduction

High-rate codes can reduce physical qubits per logical qubit, but addressable fault-tolerant gates can require large ancilla blocks, and transversal options may be limited. This work constructs the full logical Clifford group for a high-rate quantum Reed–Muller code family using transversal and fold-transversal gates.

1.1 Background

  • High-rate codes use fewer physical qubits per logical qubit than surface or color codes at the same distance, but addressable gates can be difficult to realize fault-tolerantly.Gate teleportation can implement addressable Clifford gates on stabilizer codes but requires two ancilla blocks, which can be large.Source: §1.1 · pp. 1–2
  • The available transversal and fold-transversal logical gates depend on code symmetries, and earlier high-rate constructions generally did not provide the full logical Clifford group as k grows.The cited SHYPS-code exception has k scaling poly-logarithmically with block length n.Source: §1.1 · p. 2

1.2 Our contributions

  • The studied self-dual quantum Reed–Muller family is constructed from classical Reed–Muller codes using CSS construction.The work focuses on code parameters with m a positive even number.Source: §1.2 · p. 3
  • The construction generates the full logical Clifford group from transversal and fold-transversal gates, including addressable H, S, controlled-Z, and swap gates.The gate constructions use fold-transversal gates derived from automorphisms of classical Reed–Muller codes, together with transversal Hadamard gates.Source: §1.2 · p. 3
  • For the studied high-rate quantum Reed–Muller codes, some logical Clifford gates cannot be implemented in constant depth using the specified transversal and fold-transversal physical gates.The paper states this restriction applies when k = ω(√n log n), which holds for the quantum Reed–Muller family of interest.Source: §1.2 · p. 3
  • The authors provide an open-source Python package to construct addressable H, S, controlled-Z, and swap gates and compute logical actions of the introduced gates.The package can also verify theorems related to the logical-gate construction.Source: §1.2 · p. 3
  • The construction allows logical Clifford gates to be implemented without ancilla qubits, though circuit depth may grow with block length.Fault-tolerant error-correction gadgets can be interleaved into the gate sequence to limit error propagation and accumulation.Source: §1.2 · p. 3
  • The construction generalizes the logical controlled-Z gate of the [[4, 2, 2]] code; the authors identify the family as a candidate for fault-tolerant demonstrations on near- or mid-term devices.The [[4, 2, 2]] code is the smallest code in the studied family.Source: §1.2 · pp. 3–4

2 Classical and quantum Reed–Muller codes

This section establishes the classical and quantum Reed–Muller code framework for the construction, defining the code family, automorphisms, stabilizers, and logical-qubit indexing. It also describes stabilizer generation at minimum weight and implications of growing stabilizer weights.

2.1 Definition of classical Reed–Muller codes

  • RM(r, m) is generated by vectors v_A with |A| ≤ r and equivalently consists of truth tables of Boolean polynomials of degree at most r.The classical Reed–Muller codes are nested by order, and RM(r, m)^⊥ = RM(m − r − 1, m).Source: §2.1 · p. 5

2.2 Automorphisms of classical Reed–Muller codes

  • P(i, j) and Q(i, j) are involutions whose bit permutations can be implemented by pairwise physical swaps, with a quantum analogue given by swap-type fold-transversal gates.P(i, j) and Q(i, j) act as variable swaps and the substitution x_i → x_i + x_j, respectively, on Boolean-function variables.Source: §2.2 · p. 7
  • The transvections Q(i, j) generate GL(m, 2), whereas the transpositions P(i, j) generate only a proper subgroup isomorphic to S_m.P(i, j) swaps basis vectors v_i and v_j; Q(i, j) maps v_i to v_i + v_j and leaves the other basis vectors unchanged.Source: §2.2 · pp. 7–8

2.3 Definition of quantum Reed–Muller codes

  • A quantum Reed–Muller code is formed by applying the CSS construction to classical Reed–Muller codes when r_x + r_z + 1 ≤ m.The self-dual family QRM(m) takes even positive m and r_x = r_z = m/2 − 1; examples include [[4, 2, 2]] and [[16, 6, 4]].Source: §2.3 · p. 9
  • Logical X(B) and Z(B) operators use index sets B of size m/2, and X(B) anticommutes with Z(B′) exactly when B=B′.The code labels its logical qubits using a canonical ordering of these sets and their complements.Source: §2.3 · p. 10
  • For every positive even m, QRM(m) has a stabilizer generating set whose generators each have minimum weight 2^(m/2+1)=2√n.Here n=2^m.Source: §2.3 · p. 11
  • Replacing the RM(m/2−1,m) generators v_A with linear combinations h_A preserves their span while giving each h_A weight 2^(m/2+1).For lower-degree indices, the construction multiplies v_A by factors (1+v_i); the empty-set generator is constructed similarly.Source: §2.3 · p. 11
  • QRM(m) is not quantum LDPC because stabilizer weights increase with block length; minimum-weight generators can help Shor or flag measurement circuits scale with stabilizer weight.For Steane or Knill schemes, stabilizer weight may instead affect preparation of required ancilla blocks.Source: §2.3 · p. 13

3 Logical Clifford operators of quantum Reed–Muller codes

The section constructs addressable logical Clifford operations for quantum Reed–Muller codes from transversal and fold-transversal gates, including gates derived from classical-code automorphisms and additional fold-transversal examples. It shows that these operations generate the full logical Clifford group and describes further gates whose logical actions yield products of swaps, controlled-Z, or CX gates, some of which may help reduce circuit depth.

3.1 Fold-transversal gates constructed from code automorphisms

  • Fold-transversal gates combine single-qubit gates with two-qubit gates on non-overlapping supports, enabling constant-depth logical operations without ancillas.The work distinguishes these from strictly transversal gates, which use only single-qubit gates.Source: §3.1 · p. 14
  • For even m, USW and UPH gates from P(i, j) and Q(i, j) preserve the QRM(m) stabilizer group.These fold-transversal gates are valid logical operators for every distinct i, j in [m].Source: §3.1 · p. 17
  • For any allowed set K of up to m/2 disjoint ordered pairs, UPH(Q(K)) preserves the QRM(m) stabilizer group.The construction uses products of Q(i, j) automorphisms, with all indices in K distinct.Source: §3.1 · pp. 18–19

3.2.1 Addressable S, S †, and C00Z gates

  • Logical operations on one or two qubits are denoted V(B) and W(B, B′), indexed by the corresponding logical-qubit sets.For canonical indices, the notation is shortened to V(i) and W(i, j).Source: §3.2.1 · p. 19
  • Products of phase-type fold-transversal gates provide addressable S or S† on every logical qubit and addressable C00Z on selected pairs, but not every pair.The S versus S† choice depends on the parity of m/2; the S construction has depth √n, while C00Z for pairs differing by one basis vector has depth √n/2.Source: §3.2.1 · pp. 21, 23

3.2.2 Addressable H, SW, and C00Z gates

  • Transversal H⊗n and addressable S gates construct any addressable H in O(√n), while addressable SW and C00Z on any pair have depth O(√n log n).For pairs differing by one basis vector, addressable SW can be constructed from C00Z and two addressable H gates in O(√n).Source: §3.2.2 · pp. 23–24

3.2.3 The full logical Clifford group

  • For every QRM(m), H⊗n and phase-type fold-transversal gates UPH(Q(K)) for 0 ≤ |K| ≤ m/2 generate the full logical Clifford group, independent of symplectic basis.The construction proceeds through addressable S, H, and C00Z gates.Source: §3.2.3 · p. 25

3.3 Other logical gates

  • In QRM(4), USW(P(1, 2)) fixes logical qubits 1 and 4 and swaps 2 with 6 and 3 with 5, mapping their X and Z operators correspondingly.Source: §3.3 · p. 25
  • For P(i,j), USW acts as a product of logical swaps and UPH as a product of logical controlled-Z gates on pairs of logical qubits.For example, USW(P(1,2)) = SW(2,6)SW(3,5), while UPH(P(1,2)) = C11Z(1,4)C00Z(2,3)C00Z(5,6).Source: §3.3 · p. 26
  • For Q(i,j), USW acts as a product of logical CX gates; for example, USW(Q(1,2)) = CX(2,6)CX(3,5).The corresponding UPH(Q(1,2)) is C11Z(1,4)C11Z(2,5)C11Z(3,6)C00Z(2,3).Source: §3.3 · p. 26
  • The authors did not prove closed forms for USW(P(i,j)), UPH(P(i,j)), or USW(Q(i,j)) for any QRM(m), since these gates are unnecessary for generating the full logical Clifford group.They suggest the gates could nevertheless help optimize the depth of circuits implementing arbitrary logical Clifford gates.Source: §3.3 · p. 26

4 Fundamental limitations on circuit depth for realizing an arbitrary logical Clifford gate

A counting argument gives a worst-case depth lower bound for generating the full logical Clifford group with bounded-support physical Clifford gates. For the studied quantum Reed–Muller codes, arbitrary logical Cliffords cannot all be constant-depth, although the standard addressable gates have better depth scaling.

  • For QRM(m), addressable H and S have depth O(√n), while C00Z has depth O(√n log n); these bounds are not constant in n.Source: §4 · p. 26
  • For codes generated by physical Clifford gates of support at most l=O(1), some logical Clifford gate requires depth Ω(k^2/(n log n)).The argument compares the number of realizable depth-D circuits with the size of the logical Clifford group.Source: §4 · p. 27
  • For high-rate codes with k=ω(√n log n), constant-depth implementation of every logical Clifford gate is impossible; the studied QRM codes meet this condition.Source: §4 · p. 27
  • The standard addressable H, S, and C00Z gates scale better than the worst-case arbitrary logical Clifford gate.The construction implements these gates on specified logical qubits, but arbitrary Cliffords generally require sequential application of generators.Source: §4 · pp. 26, 28
  • Compiling an arbitrary logical circuit gate by gate may be suboptimal: a paired C11Z operation has a depth-1 UPH(e) implementation, while separate compilation requires depth k.Whether general compilation matches the Corollary 2 lower bound remains open, and the authors suggest both the bound and compilation may be improved.Source: §4 · p. 28

5 Discussion and conclusions

The paper constructs the full logical Clifford group for the studied quantum Reed–Muller codes using only transversal and fold-transversal gates, without an additional ancilla block. The discussion considers circuit-depth trade-offs, fault-tolerance caveats, and limits on extending the approach.

5 Discussion and conclusions

  • For the studied quantum Reed–Muller code family, addressable Clifford gates can be constructed from transversal and fold-transversal gates, yielding the first such construction for a family with near-linear k in n.The construction does not require an additional ancilla block.Source: §5 · pp. 28–29
  • The construction saves 50% of space overhead versus [61], but its time overhead may be smaller or larger depending on the Clifford circuit.The generic circuit-depth bound from [61] may overestimate the depth for addressable gates with additional structure.Source: §5 · p. 29
  • Some operations can be virtually realized by relabeling physical qubits, but swap-type fold-transversal gates alone do not give addressable SW or CX on a single logical pair.For phantom quantum Reed–Muller codes, the required H^⊗n may fail to preserve the stabilizer group, so the full construction may not apply.Source: §5 · p. 29
  • Whether the construction extends to other codes with similar automorphism groups is unknown, and possible rate-related limits on constant-time or addressable Clifford gates remain under investigation.The paper says its results partially answer one conjecture about such limits, while the bound may be improved.Source: §5 · p. 29
  • Other fold-transversal gates may help optimize circuit depth, so decomposing arbitrary Clifford circuits into addressable gates need not be the best compilation strategy.The package also constructs examples such as USW(P(i, j)), UPH(P(i, j)), and USW(Q(i, j)).Source: §5 · pp. 28, 30
  • Fold-transversal gates can spread errors within a code block and do not meet the strict fault-tolerance conditions discussed for the standard circuit-level depolarizing model.Simulations of specific code and gate constructions have nevertheless shown performance approaching ideal fault-tolerant operations under various noise models.Source: §5 · p. 30
  • Interleaving fault-tolerant error-correction gadgets would add space and time overhead, and comparison with ancilla-block or teleportation-based approaches remains for future work.The paper identifies careful simulations as necessary for that comparison.Source: §5 · pp. 30–31
  • Clifford gates alone do not provide universal quantum computation; future directions include magic-state protocols or code switching to a code admitting non-Clifford gates.Some non-self-dual quantum Reed–Muller codes are known to admit transversal logical non-Clifford gates.Source: §5 · p. 31

6 Author contributions

The authors describe their respective contributions to the construction, software, mathematical results, and manuscript.

6 Author contributions

  • Theerapat Tansuwannont led the project, developed the addressable-gate construction, and contributed to mathematical statements in Sections 2 and 3 and Appendix A.Source: §6 · p. 31
  • Tim Chan developed the Python package for explicit gate construction and made all figures, while Ryuji Takagi developed the circuit-depth limitations and contributed to Section 4's mathematical statements.Source: §6 · p. 31
  • All authors wrote Section 1 and Section 5 and revised the manuscript.Source: §6 · p. 31

A Proofs of theorems

The appendix develops the operators and weight properties used in the proofs of Theorems 4–6. It establishes how these operators act on basis vectors and provides identities and divisibility results for the construction.

A Proofs of theorems

  • On a basis vector vA, R(K) maps to the vector indexed by (A ∪ F2(K))\F1(K) when F1(K) is contained in A, and maps to zero otherwise.Source: A Proofs of theorems · p. 32
  • For paired index sets K, Q(K) sums permutation matrices over subsets of K, while R(K) sums the corresponding replacement operators modulo 2.With distinct indices in the pairs, the replacement operations commute, so their order does not matter.Source: A Proofs of theorems · p. 32
  • The operator identities give R(K) = Q(K) and MQ(K) = R(K).Source: A Proofs of theorems · p. 33
  • For |A| ≤ m/2 − 1, wt(vA ∧ Q(K)vA) is divisible by 4.Source: A Proofs of theorems · p. 33
  • For |B| = m/2, the weight is zero if a pair in K lies wholly in B; otherwise it is 1, 2, or divisible by 4 according to |B ∩ F1(K)|.The weight is 1 when |B ∩ F1(K)| = m/2, 2 when it equals m/2 − 1, and divisible by 4 when it is at most m/2 − 2.Source: A Proofs of theorems · p. 33

A.1 Proof of Theorem 4

The proof shows that UPH(Q(K)) preserves the stabilizer group by mapping X-type stabilizer generators to products of X- and Z-type stabilizers and leaving Z-type generators unchanged.

A.1 Proof of Theorem 4

  • UPH(Q(K)) preserves the stabilizer group: it maps X-type generators to products of the same X-type generator and some Z-type stabilizer, and maps Z-type generators to themselves.The proof uses the divisibility of wt(vA ∧ Q(K)vA) by 4 and the behavior of R(L)vA for subsets L of K.Source: §A.1 · p. 34

A.2 Proof of Theorem 5

The proof classifies the logical action of UPH(Q(K)) by |K|, identifying the resulting two-qubit Clifford gates and, at |K| = m/2, an additional S gate.

A.2 Proof of Theorem 5

  • When |K| ≤ m/2−2, UPH(Q(K)) induces C11Z between logical-qubit pairs satisfying the stated F1(K), F2(K), and B′ conditions.The coefficient c is divisible by 4 in this case.Source: §A.2 · p. 35
  • When |K| = m/2−1, the combined action induces C11Z for the qualifying L subsets and C00Z for the qualifying K pair.The special C00Z pair satisfies the F1(K), F2(K), and B′ conditions.Source: §A.2 · pp. 35–36
  • When |K| = m/2, the action induces C11Z for qualifying L subsets, C00Z for |L| = m/2−1, and S(F1(K)) or its adjoint.The S gate is S when m/2 is even and S† when m/2 is odd.Source: §A.2 · pp. 36–37

A.3 Proof of Theorem 6.

The proof shows that logical gates associated with proper subsets of K cancel in the product, leaving only gates associated with M = K. Their form depends on |K|.

A.3 Proof of Theorem 6

  • For any M ⊊ K, each associated C11Z or C00Z gate occurs an even number of times and disappears from the overall product.The number of terms L containing M is 2^|K\M|, which is even for M ⊊ K.Source: §A.3 · p. 37
  • When |K| ≤ m/2−2, the remaining gate is C11Z on pairs satisfying the stated F1(K), F2(K), and B′ conditions.Source: §A.3 · p. 37
  • When |K| = m/2−1, the remaining gate is C00Z on the pair satisfying the stated F1(K), F2(K), and B′ conditions.Source: §A.3 · p. 37
  • When |K| = m/2, the remaining gate is S(F1(K)) for even m/2 or S†(F1(K)) for odd m/2.Source: §A.3 · p. 37

B Stabilizer generators and logical Pauli operators of QRM(6)

The section provides stabilizer-generator and logical-Pauli-operator choices for QRM(6), including a minimum-weight stabilizer-generator choice.

B Stabilizer generators and logical Pauli operators of QRM(6)

Loading 2602.09788v4…