AFTD Auto-Formalizing Theoretical Domains

implements_ccz_layer_zero

theoremverifiedoriginal

Sanity check: with no CCZ gates and no ancillas, the empty circuit implements the (identity) layer.

Statement

theorem implements_ccz_layer_zero : implements_ccz_layer 0 0 []
Source
Stated here; not taken from a source
Verified
06 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • implements_ccz_layerA Clifford+T circuit on 3m + a qubits implements the layer U_m of m disjoint CCZ gates with a clean ancillas if, for some global phase…

The proof, explained

To show that the empty circuit implements a CCZ layer with zero target triples (m = 0) and zero ancillas (a = 0), we choose the global phase θ = 0. By definition, the empty circuit represents the identity matrix on zero-qubit states. Comparing its entries to the CCZ specification, both sides evaluate to 1 when the output state matches the input state and 0 otherwise, because the set of applied CCZ gates is empty.

  1. To show that the empty circuit implements the CCZ layer with m = 0 target triples and a = 0 ancillas, it suffices to show that for any basis states x and z on zero qubits, the circuit matrix entry matches the CCZ specification with phase θ = 0.

    Unfolding the definition of implements_ccz_layer, the goal requires exhibiting an overall phase θ ∈ ℝ such that the circuit matrix matches the target CCZ phase-shift on all basis states. We instantiate the existential quantifier with θ = 0 and introduce arbitrary input basis state x and output basis state z.

    lines 2–4

      unfold implements_ccz_layer
      use 0
      intro x z
  2. The empty circuit's matrix entry on (z, x̃) is 1 if z = x̃ and 0 otherwise, where x̃ is the zero-qubit input state extended to the full register.

    By definition of clifford_t_circuit_matrix on the empty gate list, the circuit matrix is the identity matrix 1. Applying Matrix.one_apply rewrites this matrix entry as the Kronecker delta: 1 if z = x̃ and 0 otherwise.

    lines 5–6

    uses Matrix.one_apply

      change (1 : Matrix (Fin (3 * 0 + 0) → Bool) (Fin (3 * 0 + 0) → Bool) ℂ) z _ = _
      rw [Matrix.one_apply]
  3. The identity matrix entry matches the target CCZ entry in both the diagonal (z = x̃) and off-diagonal (z ≠ x̃) cases.

    We perform a case split on whether z = x̃. If z ≠ x̃, both sides evaluate to 0. If z = x̃, the left-hand side is 1, while the right-hand side is exp(0 * I) * (-1)^k = 1 * (-1)^k, where k is the cardinality of the set of active CCZ triples; since the triple index set Fin 0 is empty, k = 0, which gives 1 * (-1)^0 = 1. Simplification closes both cases.

    line 7

      split_ifs <;> simp
Matrix.one_apply
The (i, j)-entry of the identity matrix is 1 if i = j and 0 otherwise.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

theorem implements_ccz_layer_zero : implements_ccz_layer 0 0 [] := by  unfold implements_ccz_layer  use 0  intro x z  change (1 : Matrix (Fin (3 * 0 + 0) → Bool) (Fin (3 * 0 + 0) → Bool) ℂ) z _ = _  rw [Matrix.one_apply]  split_ifs <;> simp
See it in the graphDiscuss this resultChallenge it