op_757_all_to_all_cnot_three_exists
For k = 3 with all-to-all connectivity, there exists a Clifford circuit circ : List (CliffordGate 3) achieving clifford_circuit_score circ = two_sided_shadow_optimal_score 3 with clifford_cnot_count circ = 4.
Statement
theorem op_757_all_to_all_cnot_three_exists :
∃ circ : List (CliffordGate 3),
clifford_circuit_score circ = two_sided_shadow_optimal_score 3 ∧
clifford_cnot_count circ = 4- Formalizes
- scout/2610-04621-exact-clifford-optimality-for-two-sided-locally-randomized.md:1658
- Verified
- 31 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- 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).
- 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 Clifford circuit circ on 3 qubits (represented as a list of Clifford gates: single-qubit Hadamard, single-qubit phase $S$, and CNOT gates between distinct qubits) such that:
1. The score of circ, clifford_circuit_score circ, is equal to two_sided_shadow_optimal_score 3 (which evaluates to $(3 \cdot 5^3 + 3^3 - 6) / 4 = 99$), and
2. The number of CNOT gates in circ (clifford_cnot_count circ) is equal to 4.
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 is proved constructively by exhibiting an explicit 7-gate Clifford circuit on 3 qubits consisting of 4 CNOT gates interspersed with Hadamard and phase gates. Lean's computational decision procedure `decide` then verifies that the circuit achieves the optimal two-sided shadow score of 99 and contains exactly 4 CNOT gates.
There exists a valid 7-gate Clifford circuit on 3 qubits with all-to-all connectivity.
We instantiate the existential quantifier with an explicit candidate circuit: $\mathrm{CNOT}(2, 0)$, $H(2)$, $\mathrm{CNOT}(0, 1)$, $S(0)$, $S(2)$, $\mathrm{CNOT}(1, 2)$, and $\mathrm{CNOT}(2, 0)$. For each CNOT gate, the required inequality between control and target qubit indices ($2 \neq 0$, $0 \neq 1$, $1 \neq 2$, and $2 \neq 0$) is discharged immediately by decision procedure.
uses
CliffordGate.cnot,CliffordGate.h,CliffordGate.srefine ⟨[CliffordGate.cnot 2 0 (by decide), CliffordGate.h 2, CliffordGate.cnot 0 1 (by decide), CliffordGate.s 0, CliffordGate.s 2, CliffordGate.cnot 1 2 (by decide), CliffordGate.cnot 2 0 (by decide)], ?_, ?_⟩
The candidate circuit achieves the optimal two-sided shadow score of 99. automation
For $k = 3$, the optimal shadow score $(3 \cdot 5^3 + 3^3 - 6) / 4$ evaluates to 99. The decision procedure `decide` closes the goal by evaluating the circuit score: it propagates each of the $3^3 = 27$ full-support Pauli operators through the 7-gate circuit, computes the size of each resulting Pauli operator, and verifies that the sum of $3^{3 - \mathrm{size}}$ equals 99.
· decideThe candidate circuit has exactly 4 CNOT gates. automation
The function `clifford_cnot_count` counts gates constructed by `CliffordGate.cnot`. The decision procedure `decide` evaluates the count on the explicit 7-gate list and verifies that it equals 4.
· decide
CliffordGate.cnot- Constructs a controlled-NOT gate on $k$ qubits from distinct control and target qubit indices $c$ and $t$ with $c \neq t$.
CliffordGate.h- Constructs a Hadamard gate $H$ on qubit $i$.
CliffordGate.s- Constructs a phase gate $S$ on qubit $i$.
- The verification that the circuit achieves the optimal score of 99 (line 9) and contains exactly 4 CNOT gates (line 10) is performed entirely by Lean's computational kernel (`decide`), exhaustively evaluating the Clifford action on all 27 full-support Pauli operators.
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: exact CNOT count 4 on 3 qubits with all-to-all connectivity. -/theorem op_757_all_to_all_cnot_three_exists : ∃ circ : List (CliffordGate 3), clifford_circuit_score circ = two_sided_shadow_optimal_score 3 ∧ clifford_cnot_count circ = 4 := by refine ⟨[CliffordGate.cnot 2 0 (by decide), CliffordGate.h 2, CliffordGate.cnot 0 1 (by decide), CliffordGate.s 0, CliffordGate.s 2, CliffordGate.cnot 1 2 (by decide), CliffordGate.cnot 2 0 (by decide)], ?_, ?_⟩ · decide · decide