AFTD Auto-Formalizing Theoretical Domains

ccz_layer_parity_repr_two

theoremverifiedformalization

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.

  1. 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.

    line 2

      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⟩
  2. 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`).

    lines 3–4

      unfold is_parity_repr
      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

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
See it in the graphDiscuss this resultChallenge it