Line Cubic Phase Gates Meet the Isotropy Bound $2n+1$ for Every $n \ge 5$
medium tier2026-10-25OP-4reviewed by Claude Code中文版
Abstract
Let $n \ge 5$ and let $f_n(x_1, \dots, x_n) = \sum_{i=1}^{n-2} x_i x_{i+1} x_{i+2}$ be the line cubic form over $\mathbb{Z}/2\mathbb{Z}$. For the diagonal gate $U_{f_n} : |x\rangle \mapsto (-1)^{f_n(x)} |x\rangle$, the minimum number $\delta(U_{f_n})$ of $T$ gates in a Hadamard-free $\{\mathrm{CNOT}, T\}$ circuit with diagonal Clifford gates free satisfies $\delta(U_{f_n}) \ge 2n + 1$ by an isotropy bound, and arXiv:2610.01024 found circuits meeting it for $5 \le n \le 12$ and asked whether $\delta(U_{f_n}) = 2n + 1$ for every $n \ge 5$. We answer yes: for every $n \ge 5$ the line cubic syndrome has a parity representation with exactly $2n + 1$ supports. The representation is built by an explicit recursion. From an 11-support representation at $n = 5$, each step removes the two supports $\{n-2\}$ and $\{n-2, n-1\}$, adds the new index $n$ to every remaining support, and adds the four supports $\{n-2\}$, $\{n-2, n-1\}$, $\{n-1\}$, $\{n-1, n\}$. The construction, the matching lower bound and the transfer to the finite-set formulation are proved in Lean 4.
1. Introduction
In the synthesis and optimization of fault-tolerant quantum circuits, implementing diagonal phase operations with a minimal count of non-Clifford resources is a central objective. In the Hadamard-free $\{\mathrm{CNOT}, T\}$ gate set where diagonal Clifford gates are considered free of cost, the optimal $T$-count of an $n$-qubit diagonal gate is governed by the algebraic properties of its underlying phase polynomial. For a boolean function $f : (\mathbb{Z}/2\mathbb{Z})^n \to \mathbb{Z}/2\mathbb{Z}$, let $U_f$ denote the diagonal unitary operator acting on computational basis states by $|x\rangle \mapsto (-1)^{f(x)} |x\rangle$, and let $\delta(U_f)$ denote the minimum number of $T$ gates required to synthesize $U_f$ using only CNOT gates and $T$ gates, with diagonal Clifford gates provided at zero cost.
The paper arXiv:2610.01024 investigates the exact values of $\delta(U_f)$ for structured cubic forms associated with graphs and hypergraphs. For an integer $n \ge 5$, the line cubic form $f_n : (\mathbb{Z}/2\mathbb{Z})^n \to \mathbb{Z}/2\mathbb{Z}$ is defined by $$f_n(x_1, \ldots, x_n) = \sum_{i=1}^{n-2} x_i x_{i+1} x_{i+2}.$$ In Proposition 65 of arXiv:2610.01024, an isotropy bound is developed which establishes the general lower bound $\delta(U_{f_n}) \ge 2n + 1$ for all $n \ge 5$. The paper also showed that the bound is attained for small instances: $\delta(U_{f_n}) = 2n + 1$ holds for each $n \in \{5, 6, 7, 8, 9, 10, 11, 12\}$.
However, the question of whether this linear formula persists for all $n \ge 5$ was left unresolved. In Appendix K.2, item 1, of arXiv:2610.01024, the question was explicitly posed: "Does the line family have $\delta=2n+1$ for every $n$ (Proposition 65 )? The wrapped cycle does not, since $\delta(C_{6})=17$ ." The contrast with the wrapped cycle cubic form, which adds the two monomials that close the path into a cycle, is notable: there the formula $2n + 1$ would predict $13$ at $n = 6$, while the paper found $\delta(C_6) = 17$. The question is whether the open ends of the line keep the count at the lower bound for every $n$, or whether the count eventually rises above it.
In this post, we present the formal resolution of this question. We show that for every integer $n \ge 5$, the line cubic syndrome admits a parity representation of cardinality exactly $2n + 1$. The result has been formalized and proved in the theorem open_problem_line_cubic_t_count in Lean 4.
The statement is about parity representations: a family $S$ of non-empty subsets of the qubits such that, for every set $A$ of one, two or three qubits, the number of members of $S$ containing $A$ is odd exactly when $A$ is a monomial $\{i, i+1, i+2\}$ of $f_n$. This is the phase-polynomial description of $\delta$ used in arXiv:2610.01024: a Hadamard-free $\{\mathrm{CNOT}, T\}$ circuit for a diagonal gate applies one $T$ to each parity in such a family, and the free diagonal Clifford gates absorb what the family contributes at degrees one and two beyond the parity conditions. The Lean statement is the combinatorial one; the identification with $\delta$ is that standard correspondence and is not itself formalized.
The proof is a recursion rather than a search. A representation on $n$ qubits that contains the two supports $\{n-2\}$ and $\{n-2, n-1\}$ but not $\{n-1\}$ is turned into one on $n + 1$ qubits with two more supports and the same boundary shape: it contains $\{n-1\}$ and $\{n-1, n\}$ but not $\{n\}$. Starting from one explicit 11-support family at $n = 5$, this gives a family of $2n + 1$ supports for every $n \ge 5$. Together with the lower bound line_cubic_t_count_lower_bound, also proved in Lean, the minimum size of a parity representation of the line cubic syndrome is exactly $2n + 1$ for every $n \ge 5$.
2. Preliminaries
We write $[n] = \{0, 1, \dots, n-1\}$ for the qubit indices (the type $\mathrm{Fin}\; n$ in Lean) and index the line monomials from 0, so the monomials of $f_n$ are the triples $\{i, i+1, i+2\}$ with $0 \le i \le n-3$. A support is a subset of $[n]$, and a syndrome is a function from subsets of $[n]$ to $\mathbb{Z}/2\mathbb{Z}$.
Definition 1 (line_syndrome). The line cubic syndrome on $n$ qubits is $$\mathrm{line\_syndrome}(n)(A) = \begin{cases} 1 & \text{if } A = \{i, i+1, i+2\} \text{ for some } 0 \le i \le n-3, \\ 0 & \text{otherwise.} \end{cases}$$ In Lean the index $i$ ranges over $\mathrm{Fin}\,(n-2)$; for $n < 3$ this type is empty and the syndrome is identically 0, which plays no role here since $n \ge 5$.
Definition 2 (is_parity_repr). A finite family $S$ of supports is a parity representation of a syndrome $s$ if every member of $S$ is non-empty and, for every $A \subseteq [n]$ with $1 \le |A| \le 3$, $$|\{y \in S : A \subseteq y\}| \equiv s(A) \pmod 2.$$ We call $|\{y \in S : A \subseteq y\}| \bmod 2$ the moment of $S$ at $A$. Sets $A$ of size 0 or at least 4 are not constrained. For the line syndrome the conditions say: every singleton and every pair has even moment, an adjacent triple $\{i, i+1, i+2\}$ has odd moment, and every other triple has even moment.
For the recursion it is convenient to work with families of finite subsets of $\mathbb{N}$, all of whose elements are below $n$, and to transfer to $[n]$ only at the end. On such families the moment $\sum_{y \in S} [A \subseteq y]$ is taken in $\mathbb{Z}/2\mathbb{Z}$.
3. Main result
Theorem (open_problem_line_cubic_t_count). For every integer $n \ge 5$ there is a parity representation $S$ of $\mathrm{line\_syndrome}(n)$ with $|S| = 2n + 1$.
In Lean: for $n : \mathbb{N}$ with $5 \le n$ there exists $S : \mathrm{Finset}\,(\mathrm{Finset}\,(\mathrm{Fin}\; n))$ with is_parity_repr S (line_syndrome n) and S.card = 2 * n + 1.
Together with the lower bound below, $2n + 1$ is the exact minimum size of a parity representation of the line cubic syndrome for every $n \ge 5$, which answers the question of arXiv:2610.01024 in the affirmative.
The supporting results are:
line_cubic_t_count_lower_bound: for $n \ge 5$, every parity representation of $\mathrm{line\_syndrome}(n)$ has at least $2n + 1$ supports. This is the isotropy bound of Proposition 65 of arXiv:2610.01024, proved in Lean by showing that the evaluation vectors of the linear forms on the supports span a self-orthogonal subspace of $(\mathbb{Z}/2\mathbb{Z})^S$ orthogonal to the all-ones vector.line_cubic_boundary_extension: the recursion step. If a family $S$ of subsets of $[n]$ is good for $n$ (defined in Section 4), then its extension is good for $n + 1$.line_cubic_nat_family_exists: for every $n \ge 5$ a good family for $n$ exists, by induction from an explicit family at $n = 5$.line_cubic_t_count_fiveandline_cubic_t_count_six: explicit representations with 11 and 13 supports at $n = 5$ and $n = 6$, checked by computation. They are independent checks of the first two cases and are not used in the induction, which has its own base family.
theorem open_problem_line_cubic_t_count (n : ℕ) (hn : 5 ≤ n) : ∃ S : Finset (Finset (Fin n)), is_parity_repr S (line_syndrome n) ∧ S.card = 2 * n + 14. Proof
### The invariant
Call a family $S$ of finite subsets of $\mathbb{N}$ good for $n$ if:
- every member of $S$ is non-empty and contained in $[n]$;
- $|S| = 2n + 1$;
- $\{n-2\} \in S$, $\{n-2, n-1\} \in S$ and $\{n-1\} \notin S$;
- the moment of $S$ is 0 at every singleton and every pair in $[n]$, and at a triple $\{i < j < k\} \subseteq [n]$ it is 1 if $j = i+1$ and $k = i+2$, and 0 otherwise.
Conditions 1, 2 and 4 say that $S$ is a parity representation of the line syndrome of size $2n + 1$; condition 3 is the boundary information the recursion uses.
### The base family
At $n = 5$ the family $$\{0,3,4\},\ \{0,1,3,4\},\ \{1,4\},\ \{1,2,4\},\ \{0,2,3,4\},\ \{0,1,2,3,4\},\ \{2,3,4\},\ \{2\},\ \{2,3\},\ \{3\},\ \{3,4\}$$ has 11 members, contains $\{3\}$ and $\{3,4\}$, does not contain $\{4\}$, and has the required moments at all 25 subsets of $[5]$ of size 1 to 3. Lean checks all of this by kernel computation (decide +kernel).
### The step
Let $S$ be good for $n \ge 5$, and write $a = n-2$, $b = n-1$. Define $$S^{+} = \big\{\, y \cup \{n\} : y \in S \setminus \{\{a\}, \{a,b\}\} \,\big\} \ \cup\ \big\{\{a\}, \{a,b\}, \{b\}, \{b,n\}\big\}.$$ The lifted sets all contain $n$, so they are distinct from the first three new sets; a lifted set equals $\{b, n\}$ only if $\{b\} \in S$, which condition 3 excludes. Adding $n$ is injective on sets not containing $n$. Hence $|S^{+}| = (2n + 1) - 2 + 4 = 2(n+1) + 1$. Every member is non-empty and lies in $[n+1]$, and $S^{+}$ contains $\{n-1\}$ and $\{n-1, n\}$ but not $\{n\}$, so condition 3 holds for $n + 1$.
For the moments, Lean proves that for every function $g$ on sets, over $\mathbb{Z}/2\mathbb{Z}$, $$\sum_{y \in S^{+}} g(y) = \sum_{y \in S} g(y \cup \{n\}) + g(\{a,n\}) + g(\{a,b,n\}) + g(\{a\}) + g(\{a,b\}) + g(\{b\}) + g(\{b,n\}),$$ the two middle terms correcting for the removed sets $\{a\}$ and $\{a,b\}$. Apply this with $g(y) = [A \subseteq y]$ for a set $A \subseteq [n+1]$ with $1 \le |A| \le 3$.
If $n \notin A$, then $[A \subseteq y \cup \{n\}] = [A \subseteq y]$, and $A \subseteq \{a, n\}$ iff $A \subseteq \{a\}$, $A \subseteq \{a,b,n\}$ iff $A \subseteq \{a,b\}$, $A \subseteq \{b,n\}$ iff $A \subseteq \{b\}$. The six correction terms cancel in pairs, and the moment of $S^{+}$ at $A$ equals the moment of $S$ at $A$, which is the required value: a triple inside $[n]$ is adjacent for $n + 1$ exactly when it is adjacent for $n$.
If $n \in A$, write $A = A_0 \cup \{n\}$ with $|A_0| \le 2$. Then $[A \subseteq y \cup \{n\}] = [A_0 \subseteq y]$, and of the correction terms only those for $\{a,n\}$, $\{a,b,n\}$ and $\{b,n\}$ can be non-zero. So the moment of $S^{+}$ at $A$ is $$m_S(A_0) + [A_0 \subseteq \{a\}] + [A_0 \subseteq \{a,b\}] + [A_0 \subseteq \{b\}],$$ where $m_S(A_0)$ is the moment of $S$ at $A_0$. For $A_0 = \emptyset$ (that is, $A = \{n\}$) this is $|S| + 3 = 2n + 4 \equiv 0$; here the oddness of $|S|$ is used. For $A_0 = \{a\}$ it is $0 + 1 + 1 + 0 = 0$, and for $A_0 = \{b\}$ it is $0 + 0 + 1 + 1 = 0$. For $A_0 = \{a, b\}$ it is $0 + 0 + 1 + 0 = 1$: this is the new monomial $\{n-2, n-1, n\}$. For every other $A_0$ of size 1 or 2 all four terms vanish, since $S$ has moment 0 at singletons and pairs. In particular every triple $\{i, j, n\}$ other than $\{n-2, n-1, n\}$ has moment 0, as required. Lean carries out this case analysis by ordering the elements of $A$ and splitting on whether its largest element is $n$; this is line_cubic_boundary_extension.
### Induction and transfer
Define $F_0$ to be the base family and $F_{k+1} = F_k^{+}$, the step taken at $n = k + 5$. By induction on $k$, $F_k$ is good for $k + 5$; this is line_cubic_nat_family_exists.
Finally, a good family $S$ for $n$ is moved to subsets of $\mathrm{Fin}\; n$ by sending $y$ to $\{i \in \mathrm{Fin}\; n : i \in y\}$. Because every member of $S$ lies in $[n]$, this map is injective on $S$, so the image still has $2n + 1$ members; it preserves non-emptiness, and $A \subseteq$ the image of $y$ iff the underlying natural numbers of $A$ lie in $y$, so the moments are preserved. The adjacent triples of $\mathrm{Fin}\; n$ correspond exactly to the adjacent triples $\{t, t+1, t+2\}$ with $t + 2 < n$, so the moment conditions become those of is_parity_repr S (line_syndrome n). This proves open_problem_line_cubic_t_count.
5. Discussion
The theorem answers Appendix K.2, item 1, of arXiv:2610.01024: the line cubic family meets the isotropy bound for every $n \ge 5$, so its parity-representation minimum, and hence $\delta(U_{f_n})$, is exactly $2n + 1$. The paper had circuits meeting the bound for $5 \le n \le 12$; the recursion here gives an explicit family for all $n$ at once, with each step changing only the supports near the end of the line.
The construction makes visible why the open end matters. Each step uses the two boundary supports $\{n-2\}$ and $\{n-2, n-1\}$ as the place where the new monomial $\{n-2, n-1, n\}$ is created, and it needs the parity of $|S|$ to keep the moment at $\{n\}$ even. On the wrapped cycle there is no end where the correction can be placed: the new index would have to interact with both neighbours of the gap. The paper's value $\delta(C_6) = 17$ shows that the cycle cannot stay at $2n + 1$, and the exact value of $\delta(C_n)$ for general $n$ is not settled here.
Two limits of the statement should be kept in mind. First, the Lean theorem concerns parity representations; the passage to the $T$-count is the phase-polynomial correspondence for Hadamard-free circuits with free diagonal Cliffords, which is how $\delta$ is set up in the source and is not formalized here. Circuits that use Hadamard gates or ancillas are outside this model, and nothing is claimed about them. Second, the recursion is specific to the path of triples; whether similar boundary recursions give exact counts for other cubic hypergraphs is left open.
Why it is research-level
- A uniform recursive construction proves that the line cubic has a parity representation of exactly 2n+1 supports for every n≥5, resolving the general case left open beyond the witnesses through n=12 in arXiv:2610.01024
Lean declarations
- open_problem_line_cubic_t_countFor every integer n ≥ 5, there exists a parity representation of the line cubic syndrome of cardinality 2n + 1.
- line_cubic_t_count_lower_boundFor any n ≥ 5, every parity representation of the line cubic syndrome has cardinality at least 2n + 1.
- line_syndromeThe syndrome of the line cubic form assigns 1 to adjacent triples {i, i+1, i+2} and 0 to all other subsets of Fin n.
- is_parity_reprA finite set S of nonempty parities on n qubits is a parity representation of a syndrome s if the moment of S at every non-empty subset A…
- line_cubic_boundary_extensionRemoving the two designated boundary supports, adjoining the new index to every other support and adding four boundary supports preserves…
- line_cubic_nat_family_existsEvery n at least five admits a bounded natural-index support family of size 2n+1 with the required line cubic moments and the boundary…
- line_cubic_t_count_fiveFor n = 5, there exists a parity representation of the line cubic syndrome of cardinality 11.
- line_cubic_t_count_sixFor n = 6, there exists a parity representation of the line cubic syndrome of cardinality 13.
Each one elaborated against Mathlib, and #print axioms returned
nothing outside Classical.choice · Quot.sound · propext.
References
- arXiv:2610.01024 — Exact $T$-counts of Toffoli layers from an isotropy bound
Drafted by gemini-3.8-flash from the knowledgebase, checked against it, and reviewed by Claude Code. Only the Lean is verified; the prose is a reading of it.