Building codes with transversal CCZ using projective geometry and SAT solvers

AI summary

Overview

Research area: Quantum error correction and fault-tolerant quantum computing, specifically the design of Calderbank–Shor–Steane (CSS) codes that admit transversal non-Clifford gates. The paper sits at the intersection of quantum coding theory, classical coding theory (divisible and two-weight codes, projective geometry), and automated constraint solving (SAT solvers).

Technical level: Advanced. The paper assumes familiarity with CSS codes, stabilizer formalism, the Clifford hierarchy, Reed–Muller codes, and finite projective geometry.

Scope: The paper constructs CSS codes with three logical qubits whose logical CCZ gate is realized by transversal physical (T/T^\dagger) gates, builds such codes at thirteen block lengths from (n=48) to (n=496), and proves a length lower bound of (n \ge 39) for the quasi-transversal version of the problem.

What This Paper Is About

Fault-tolerant quantum computers need non-Clifford gates such as CCZ, and the usual route—magic-state distillation—costs a great deal of space-time overhead. One way around that overhead is to design a code whose physical phase rotations directly implement the desired logical diagonal gate, so that the gate is transversal and errors cannot spread between qubits. This paper asks how to systematically build CSS codes with three logical qubits that have this property, how short such codes can be, and what classical geometric structures make the construction possible.

Key Contributions

1. A geometric recipe for the stabilizer part. The authors choose the (X)-stabilizer code (\mathcal{C}_2) to be (8)-divisible (triply even) and to come from a subspace complement in binary projective geometry. This automatically satisfies the stabilizer-only Campbell–Howard conditions S1–S3 and, when the columns of the stabilizer generator matrix are distinct and nonzero (a projective code), guarantees (d_Z \ge 3) for every choice of logical rows.

2. A SAT-based search for logical operators. With (\mathcal{C}_2) fixed by geometry, the search for three (X)-logical rows (K) is encoded as a Boolean satisfiability problem with (3n) Boolean label variables and (7 + 6s + 3\binom{s}{2} = O(s^2)) parity constraints coming from conditions K1, K2, K3, KS1, KS2, and KS3. This yields codes at thirteen block lengths from (n=48) to (n=496), with (d_Z = 3) or (4).

3. A new (\llbracket 48,3,3 \rrbracket) code, (\mathcal{Q}_{48}). Its stabilizer code is FG48, the projective (8)-divisible ([48,6]) two-weight code (\mathrm{PG}(5,2)\setminus\mathrm{PG}(3,2)). Its logical CCZ is implemented by physical (T) and (T^\dagger) rotations. The paper states that (\mathcal{Q}_{48}) is the smallest known code with a single-qubit transversal CCZ.

4. A length lower bound and its tightness. The authors prove that no CSS code with (k=3), (d_Z \ge 3), and a quasi-transversal CCZ gate (transversal (T) followed by a diagonal Clifford correction) exists below (n=39). The (\llbracket 47,3,3 \rrbracket) code of Jacinto et al. [2026] attains the minimum length in this class, as certified by the classification of Wills, Jain, and Singh [2026].

Main Findings

• FG48 is unique. Up to coordinate permutation, the only projective (8)-divisible ([48,6]) code is the two-weight complement of a solid, (\mathrm{PG}(5,2)\setminus\mathrm{PG}(3,2)). It has 48 columns drawn from the 63 points of (\mathrm{PG}(5,2)), missing 15 points. Hyperplanes of (\mathrm{PG}(5,2)) have 31 points, forcing section sizes of 16 or 24; a double count gives (N_{16}=3) hyperplanes and (N_{24}=60), hence codeword weights 32 and 24.

• Distance reduces to a column condition. Lemma 2.1 shows (d_Z \ge 3) is equivalent to the support being multiplicity-free: no column has zero syndrome with nonzero logical label, and no two columns share the same nonzero syndrome with different labels. A projective (\mathcal{C}_2) satisfies this for every (K).

• Triple divisibility is stronger than the stabilizer conditions. Conditions S1–S3 impose parity constraints mod 2, while (8)-divisibility imposes (|S_l| \equiv 0 \pmod 8), pairwise overlaps (\equiv 0 \pmod 4), and triple overlaps (\equiv 0 \pmod 2). The authors use the stronger condition because it lets them borrow classical divisible-code constructions.

• The nine Campbell–Howard conditions are necessary and sufficient. Theorem 3.3 combines the sufficiency result of Campbell and Howard [2017] with the necessity result of Hu et al. [2022a]: (C,T^{\otimes n}) realizes logical CCZ for some diagonal Clifford correction (C) if and only if the generator matrix satisfies all nine conditions K1–K3, KS1–KS3, S1–S3. K3 is the single condition with odd parity.

• Indicator polynomials live in a Reed–Muller coset. Lemma 3.2 shows the column indicator of (G) satisfies (\chi_G \in \chi_{G,0} + \varepsilon \delta_0 + \mathrm{RM}(r-4,r)) with (\varepsilon = n \bmod 2). At even length this simplifies to (\chi_G \in y_1\cdots y_s + \mathrm{RM}(s-1,s+3)), so (\deg \chi_G = s) with (y_1\cdots y_s) the only degree-(s) term.

• (\mathcal{Q}_{48}) has low-degree structure. Its stabilizer indicator has degree 2 and its full indicator has degree 6, and the label map (\kappa) on each of the three nonzero cosets is quadratic in the coordinates (u).

• Lower bound. No CSS code with (k=3), (d_Z \ge 3) satisfying the nine conditions exists at (n \le 38), for any number of (X)-stabilizer generators. The conditions involving only stabilizers restrict valid block lengths to the weight spectrum of a Reed–Muller code, and each admissible length is then decided exactly.

Methodology in Plain English

The authors split the design problem into two stages. First, they fix the stabilizer part of the code using classical geometry rather than search. They take all nonzero points of a binary projective space and delete a lower-dimensional subspace, which leaves a fixed number of points and produces a code whose codeword weights take only two values. This geometric choice is automatically (8)-divisible and automatically has distinct, nonzero columns, which locks in (d_Z \ge 3) before any logical operators are chosen.

Second, they search for the three logical rows. Because the stabilizer part is already fixed and already guarantees distance, the search carries no distance constraints; it only needs to satisfy the parity conditions linking logical and stabilizer rows. They encode this as a SAT instance and solve it. Once a candidate generator matrix is found, they check whether an actual (T/T^\dagger) pattern—possibly with (S^\dagger) corrections on some qubits—reproduces logical CCZ.

For the lower bound, they observe that the stabilizer-only conditions force the block length into the weight spectrum of a Reed–Muller code. They then decide each surviving length exactly, which rules out every (n \le 38).

Why This Matters

The paper reduces the cost of a non-Clifford gate by making it transversal, and it shows how to search for such codes in a structured way instead of guessing. It also connects quantum code design to well-developed classical objects—divisible codes, two-weight codes, and subspace complements—and demonstrates that SAT solvers can serve as practical design tools for small codes.

Potential applications of the broader technology:

• Quantum chemistry and materials simulation, where non-Clifford gates dominate the cost of preparing correlated ground states.
• Cryptographic applications such as factoring and discrete logarithms, which require large numbers of non-Clifford gates.
• Compilation and resource estimation for fault-tolerant architectures, where shorter blocks and fewer magic-state factories translate directly into smaller hardware footprints.
• Architecture co-design for platforms that can apply single-qubit phase gates globally or in parallel, since the construction uses only physical (T/T^\dagger) and Clifford corrections.

Industry relevance: The work targets the overhead problem that dominates fault-tolerant resource estimates. Code designers and hardware architects can use the geometric plus SAT workflow to generate candidate codes at useful block lengths. The paper does not report hardware demonstrations, experimental error rates, or implementations on specific devices.

Future Directions

• Other non-Clifford gates. The paper lists extensions to other non-Clifford gates as an open problem, since the Campbell–Howard framework is not specific to CCZ.
• More logical qubits. Extending the construction beyond (k=3) is left open; the SAT encoding and the Reed–Muller coset characterization would need to be generalized.
• Closing the length gap. The lower bound rules out (n \le 38) for quasi-transversal CCZ, while the smallest known code in that class has (n=47). Whether intermediate lengths exist and which geometric families could realize them remains open.
• Higher distance and other geometric families. The constructed codes have (d_Z = 3) or (4); finding families with larger (d_Z), or using other two-weight and divisible-code families beyond subspace complements, is a natural next step.

Target Audience

This paper is most useful to researchers in quantum error correction and fault-tolerant quantum computing, especially those working on transversal non-Clifford gates, CSS-T codes, and magic-state overhead reduction. It is also relevant to classical coding theorists interested in divisible codes, two-weight codes, and projective geometry, and to engineers doing fault-tolerant resource estimation who need concrete code parameters. Readers should be comfortable with stabilizer codes and binary linear codes; the projective-geometry and SAT details are self-contained enough for a determined graduate student.

Authors’ abstract

We construct CSS codes with three logical qubits whose logical CCZ gate is implemented by transversal physical $T/T^\dagger$ gates and whose distance is at least 3. These codes start with 8-divisible $X$-stabilizers defined by projective geometry, which guarantees $d_Z \geq 3$. A SAT solver then finds three $X$-logical operators compatible with the transversal CCZ. We build codes at thirteen block lengths from $n=48$ to $n=496$, with $d_Z=3$ or 4, and illustrate the method with the [[48,3,3]] code $Q_{48}$. Additionally, we prove that no CSS code with three logical qubits, $Z$-distance at least 3, and a quasi-transversal CCZ gate (transversal $T$ with a diagonal Clifford correction) exists below $n=39$. The [[47,3,3]] code of Jacinto et al. attains the minimum length in this class, as established by the classification of Wills, Jain, and Singh.