AFTD Auto-Formalizing Theoretical Domains

implements_ccz_layer

def

A 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 e^{i theta} and every input x of 3m bits, it maps |x, 0^a> to e^{i theta} (-1)^{#{j : x_{3j} = x_{3j+1} = x_{3j+2} = 1}} |x, 0^a> (all other output amplitudes zero), so the ancillas return to |0>.

Statement

def implements_ccz_layer (m a : ℕ) (gs : List (CliffordTGate (3 * m + a))) : Prop
Defined in
Exact T-counts of Toffoli Layers from an Isotropy Bound, arXiv:2610.01024, abstract and Sec. 1 (implementing the parallel CCZ layer with clean ancillas, the setting of its open problem on circuits with Hadamards)
Verified
06 Oct 2026
Axioms
none listed
Built on 2
  • clifford_t_circuit_matrixThe unitary of a Clifford+T circuit given as a list of gates, the first gate of the list acting first: g_k ... g_2 g_1.
  • CliffordTGateA gate of a Clifford+T circuit on N qubits: a Hadamard H on qubit i, a phase gate S on qubit i, a CNOT with control c and target t (c…
Used by 1

Lean source view module on GitHub

/-- A circuit on 3m + a qubits implements the layer of m disjoint CCZ gates with a clean ancillas: up to a global phase it maps |x, 0> to (-1)^{sum_j x_{3j} x_{3j+1} x_{3j+2}} |x, 0> for every input x. -/
def implements_ccz_layer (m a : ℕ) (gs : List (CliffordTGate (3 * m + a))) : Prop :=
  ∃ θ : ℝ, ∀ (x : Fin (3 * m) → Bool) (z : Fin (3 * m + a) → Bool),
    clifford_t_circuit_matrix gs z (fun i => if h : i.val < 3 * m then x ⟨i.val, h⟩ else false) =
      if z = (fun i => if h : i.val < 3 * m then x ⟨i.val, h⟩ else false) then
        Complex.exp (θ * Complex.I) *
          (-1) ^ ((Finset.univ.filter fun j : Fin m =>
            x ⟨3 * j.val, by omega⟩ && x ⟨3 * j.val + 1, by omega⟩ &&
              x ⟨3 * j.val + 2, by omega⟩).card)
      else 0
See it in the graphDiscuss this resultChallenge it