ccz_layer_parity_repr_two
Two disjoint CCZ gates have a parity representation with 13 = 6 * 2 + 1 parities, so the Hadamard-free T-count of the layer with m = 2 is at most 13.
Statement
theorem ccz_layer_parity_repr_two : ∃ S : Finset (Finset (Fin 6)), is_parity_repr S (ccz_layer_syndrome 2) ∧ S.card = 13- Formalizes
- Exact T-counts of Toffoli Layers from an Isotropy Bound, arXiv:2610.01024, Theorem 40 (upper bound via Proposition 47 / Lemma 46: a parity representation of weight 6m + 1); special case m = 2, the value 13 also reported earlier by the synthillation construction cited there
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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…
- ccz_layer_syndromeThe syndrome of the layer of m disjoint CCZ gates on 3m qubits (blocks {3j, 3j+1, 3j+2}): 1 on each block triple and 0 on every other…
The proof, explained
The proof proceeds by exhibiting an explicit candidate family S of 13 subsets of {0, 1, 2, 3, 4, 5} and verifying that it satisfies the parity representation conditions for two disjoint CCZ gates. Both the cardinality condition |S| = 13 and the parity constraints for all 41 subsets of size at most 3 are verified by exhaustive computation in the Lean kernel.
Supplying an explicit 13-element family S reduces the theorem to verifying that S is a parity representation for the 2-CCZ syndrome. automation
The existential quantifier is instantiated with an explicit candidate collection S containing 13 subsets of {0, 1, 2, 3, 4, 5}. The cardinality condition |S| = 13 is proven immediately by kernel computation (`decide +kernel`), leaving only the condition that S represents the syndrome.
refine ⟨{{0, 1, 2, 3, 4, 5}, {0, 1, 2, 3, 4}, {0, 1, 2, 3, 5}, {0, 1, 2, 3}, {0, 1, 2, 4, 5}, {0, 1, 2, 4}, {0, 1, 2, 5}, {0, 1}, {0, 2}, {0}, {1, 2}, {1}, {2}}, ?_, by decide +kernel⟩
The collection S is a valid parity representation for `ccz_layer_syndrome 2`. automation
Unfolding the definition `is_parity_repr` requires verifying two conditions: that every member of S is nonempty, and that for every subset A ⊆ {0, 1, 2, 3, 4, 5} with 1 ≤ |A| ≤ 3, the number of sets in S containing A is odd if A = {0, 1, 2} or A = {3, 4, 5} and even otherwise. Because there are only 13 sets in S and 41 such subsets A (6 of size 1, 15 of size 2, and 20 of size 3), this is a finite proposition that Lean settles by direct kernel evaluation (`decide +kernel`).
unfold is_parity_repr decide +kernel
- The proof relies on computational reflection: both the cardinality check |S| = 13 and the verification of the parity conditions for all 41 candidate subsets of size at most 3 are discharged by exhaustive evaluation in the Lean kernel via `decide +kernel`.
Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem ccz_layer_parity_repr_two : ∃ S : Finset (Finset (Fin 6)), is_parity_repr S (ccz_layer_syndrome 2) ∧ S.card = 13 := by refine ⟨{{0, 1, 2, 3, 4, 5}, {0, 1, 2, 3, 4}, {0, 1, 2, 3, 5}, {0, 1, 2, 3}, {0, 1, 2, 4, 5}, {0, 1, 2, 4}, {0, 1, 2, 5}, {0, 1}, {0, 2}, {0}, {1, 2}, {1}, {2}}, ?_, by decide +kernel⟩ unfold is_parity_repr decide +kernel