AFTD Auto-Formalizing Theoretical Domains

is_1d_chain_circuit

def

A Clifford circuit circ : List (CliffordGate k) satisfies the 1D nearest-neighbor chain connectivity condition if every cnot gate with control c and target t satisfies c.val + 1 = t.val or t.val + 1 = c.val.

Statement

def is_1d_chain_circuit {k : ℕ} (circ : List (CliffordGate k)) : Prop
Defined in
scout/2610-04621-exact-clifford-optimality-for-two-sided-locally-randomized.md:1668
Verified
30 Oct 2026
Axioms
none listed
Built on 1
  • CliffordGateAn inductive type representing a quantum gate in a k-qubit Clifford circuit: Hadamard h on qubit i : Fin k, phase gate s on qubit i : Fin…
Used by 2
  • op_757_cnot_two_existsFor k = 2, there exists a Clifford circuit circ : List (CliffordGate 2) satisfying is_1d_chain_circuit circ and clifford_circuit_score…
  • op_757_1d_chain_cnot_three_le_fiveFor k = 3 with 1D nearest-neighbor chain connectivity, there exists a Clifford circuit circ : List (CliffordGate 3) satisfying…

Read back from the Lean

Given a natural number k and a list circ of Clifford gates on k qubits, is_1d_chain_circuit circ asserts that every gate in circ satisfies: if it is a CNOT gate with control qubit c and target qubit t (in Fin k), then c and t are adjacent in index (specifically, c.val + 1 = t.val or t.val + 1 = c.val); and if it is any other gate (Hadamard or Phase), the condition holds trivially.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- Predicate that a Clifford circuit on k qubits has 1D nearest-neighbor chain connectivity. -/
def is_1d_chain_circuit {k : ℕ} (circ : List (CliffordGate k)) : Prop := circ.all (fun g => match g with | .cnot c t _ => decide (c.val + 1 = t.val ∨ t.val + 1 = c.val) | _ => true) = true
See it in the graphDiscuss this resultChallenge it