op_757_cnot_two_exists
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`).
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`).
uses
CliffordGate.cnotclifford_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.
- The equality of the Clifford circuit score to the optimal score (both evaluating to 17) and the inequality on the CNOT count (1 ≤ 2) are proved by Lean's kernel computing the finite sums and definitions directly (`decide`).
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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⟩