AFTD Auto-Formalizing Theoretical Domains

op_757_cnot_two_exists

theoremverifiedformalization

For k = 2, there exists a Clifford circuit circ : List (CliffordGate 2) satisfying is_1d_chain_circuit circ and clifford_circuit_score circ = two_sided_shadow_optimal_score 2 with clifford_cnot_count circ <= 2.

Statement

theorem op_757_cnot_two_exists :
    ∃ circ : List (CliffordGate 2),
      is_1d_chain_circuit circ ∧
      clifford_circuit_score circ = two_sided_shadow_optimal_score 2 ∧
      clifford_cnot_count circ ≤ 2
Formalizes
scout/2610-04621-exact-clifford-optimality-for-two-sided-locally-randomized.md:1658
Verified
31 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • two_sided_shadow_optimal_scoreThe optimal score s_k for a k-qubit Clifford unitary in the two-sided locally randomized classical shadow architecture, defined as a…
  • 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…
  • clifford_cnot_countThe CNOT count of a k-qubit Clifford circuit, defined as the number of cnot gates in the list circ : List (CliffordGate k).
  • is_1d_chain_circuitA Clifford circuit circ : List (CliffordGate k) satisfies the 1D nearest-neighbor chain connectivity condition if every cnot gate with…
  • clifford_circuit_scoreThe integer score S_k(U) of a k-qubit Clifford circuit circ : List (CliffordGate k), defined as the sum over all p in full_support_paulis…

Read back from the Lean

There exists a list circ of 2-qubit Clifford gates (where gates are Hadamard h, Phase s, or CNOT cnot) such that: 1. circ is a 1D chain circuit (every CNOT gate acts on adjacent qubits, meaning c.val + 1 = t.val ∨ t.val + 1 = c.val); 2. the Clifford circuit score of circ equals two_sided_shadow_optimal_score 2 (which evaluates to 17); and 3. the number of CNOT gates in circ is at most 2.

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

The proof, explained

The theorem shows that for two qubits, there exists a 1D chain Clifford circuit achieving the optimal two-sided shadow score using at most two CNOT gates. The proof explicitly constructs the circuit consisting of a single CNOT gate between qubits 0 and 1. All conditions—validity of the gate indices, adjacency on the 1D chain, optimality of the score (both sides equal 17), and the CNOT count bound (1 ≤ 2)—are verified directly by computational reflection (`decide`) and definition unfolding (`rfl`).

  1. The single-gate circuit [CNOT(0, 1)] is a valid 1D chain circuit on 2 qubits achieving the optimal two-sided shadow score of 17 with at most 2 CNOT gates.

    We provide the witness circuit containing a single CNOT gate with control 0 and target 1. Constructing this gate with `CliffordGate.cnot` requires showing that the qubits are distinct (0 ≠ 1), which `decide` verifies by finite evaluation. The three conjuncts are then verified: 1. `is_1d_chain_circuit` holds by definition (`rfl`) because the gate connects adjacent qubits |0 - 1| = 1 on the 1D chain. 2. The circuit score equals the optimal two-sided shadow score (`two_sided_shadow_optimal_score 2`), as both sides evaluate to 17 (verified by `decide` via exhaustive summation over all 9 full-support Pauli operators). 3. The CNOT count is at most 2, since the circuit contains 1 CNOT gate and 1 ≤ 2 (verified by `decide`).

    line 6

    uses CliffordGate.cnot

          clifford_cnot_count circ ≤ 2 := ⟨[CliffordGate.cnot 0 1 (by decide)], rfl, by decide, by decide⟩
CliffordGate.cnot
Given two distinct qubits c and t in Fin k with a proof that c ≠ t, constructs a CNOT gate with control c and target t.

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

/-- Partial result for OP-757: 2 CNOTs suffice on 2 qubits. -/theorem op_757_cnot_two_exists :    ∃ circ : List (CliffordGate 2),      is_1d_chain_circuit circ ∧      clifford_circuit_score circ = two_sided_shadow_optimal_score 2 ∧      clifford_cnot_count circ ≤ 2 := ⟨[CliffordGate.cnot 0 1 (by decide)], rfl, by decide, by decide⟩
See it in the graphDiscuss this resultChallenge it