op_757_1d_chain_cnot_three_le_five
For k = 3 with 1D nearest-neighbor chain connectivity, there exists a Clifford circuit circ : List (CliffordGate 3) satisfying is_1d_chain_circuit circ and clifford_circuit_score circ = two_sided_shadow_optimal_score 3 with clifford_cnot_count circ <= 5.
Statement
theorem op_757_1d_chain_cnot_three_le_five :
∃ circ : List (CliffordGate 3),
is_1d_chain_circuit circ ∧
clifford_circuit_score circ = two_sided_shadow_optimal_score 3 ∧
clifford_cnot_count circ ≤ 5- Formalizes
- scout/2610-04621-exact-clifford-optimality-for-two-sided-locally-randomized.md:1669
- 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 Clifford gates on 3 qubits (CliffordGate 3) such that:
1. circ is a 1D chain circuit (every CNOT gate in circ acts on adjacent qubits, i.e., control c and target t satisfy c.val + 1 = t.val ∨ t.val + 1 = c.val),
2. The Clifford circuit score of circ equals two_sided_shadow_optimal_score 3 (which evaluates to 99), and
3. The number of CNOT gates in circ is at most 5.
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 proof demonstrates that 5 CNOT gates suffice for optimal shadow tomography on a 3-qubit 1D chain by exhibiting an explicit 19-gate Clifford circuit with exactly 5 CNOT gates. Lean verifies the three required conditions—that all CNOT gates act only between nearest-neighbor qubits, that the circuit achieves the optimal score of 99, and that at most 5 CNOTs are used—entirely by direct computational evaluation (`decide`).
Provide an explicit candidate Clifford circuit on 3 qubits, reducing the goal to three verifiable properties.
We instantiate the existential quantifier with a concrete 19-gate circuit consisting of single-qubit Hadamard and phase gates alongside 5 CNOT gates: $\operatorname{CNOT}(1, 0)$, $\operatorname{CNOT}(1, 2)$, $\operatorname{CNOT}(0, 1)$, $\operatorname{CNOT}(1, 2)$, and $\operatorname{CNOT}(0, 1)$. For each CNOT gate, the distinctness requirement between control and target indices ($1 \neq 0$, $1 \neq 2$, $0 \neq 1$) is discharged on the spot by decision procedure (`decide`). This leaves three subgoals corresponding to the three conjunctions.
refine ⟨[CliffordGate.s 1, CliffordGate.s 0, CliffordGate.h 2, CliffordGate.cnot 1 0 (by decide), CliffordGate.s 1, CliffordGate.h 1, CliffordGate.cnot 1 2 (by decide), CliffordGate.s 2, CliffordGate.h 2, CliffordGate.cnot 0 1 (by decide), CliffordGate.h 2, CliffordGate.cnot 1 2 (by decide), CliffordGate.s 2, CliffordGate.h 0, CliffordGate.h 2, CliffordGate.cnot 0 1 (by decide), CliffordGate.h 1, CliffordGate.s 1, CliffordGate.s 1], ?_, ?_, ?_⟩
The circuit satisfies the 1D nearest-neighbor chain connectivity condition. automation
Unfolding the definition `is_1d_chain_circuit` requires showing that every CNOT gate acts on adjacent qubits, i.e., $c + 1 = t$ or $t + 1 = c$. The decision procedure (`decide`) evaluates this boolean predicate over the list of gates by inspection: all five CNOT operations couple indices $(1, 0)$, $(1, 2)$, or $(0, 1)$, all of which are nearest neighbors along the linear chain.
· unfold is_1d_chain_circuit decide
The circuit achieves the optimal two-sided shadow score of 99. automation
For $k = 3$, the theoretical optimal score `two_sided_shadow_optimal_score 3` evaluates to $(3 \cdot 5^3 + 3^3 - 6) / 4 = 99$. The score of the circuit is defined as the sum over all 27 full-support Pauli operators $p$ on 3 qubits of $3^{3 - |C(p)|}$, where $|C(p)|$ is the Pauli weight after conjugation by the circuit. The decision procedure (`decide`) computes this sum by finite enumeration and confirms that it equals 99.
· decideThe circuit uses at most 5 CNOT gates. automation
The number of CNOT gates is calculated by filtering the circuit list for CNOT constructors and taking its length. Direct evaluation (`decide`) counts exactly 5 CNOT gates and checks that $5 \le 5$.
· decide
- The proof proceeds entirely by finite computational verification: after an explicit 19-gate Clifford circuit is provided, Lean's kernel decision procedure (`decide`) evaluates its 1D chain connectivity, exhaustively checks the shadow score over all 27 full-support Pauli operators, and counts the CNOT gates.
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: 5 CNOTs suffice on a 1D chain for k = 3, beating the dual-axis bound of 6. -/theorem op_757_1d_chain_cnot_three_le_five : ∃ circ : List (CliffordGate 3), is_1d_chain_circuit circ ∧ clifford_circuit_score circ = two_sided_shadow_optimal_score 3 ∧ clifford_cnot_count circ ≤ 5 := by refine ⟨[CliffordGate.s 1, CliffordGate.s 0, CliffordGate.h 2, CliffordGate.cnot 1 0 (by decide), CliffordGate.s 1, CliffordGate.h 1, CliffordGate.cnot 1 2 (by decide), CliffordGate.s 2, CliffordGate.h 2, CliffordGate.cnot 0 1 (by decide), CliffordGate.h 2, CliffordGate.cnot 1 2 (by decide), CliffordGate.s 2, CliffordGate.h 0, CliffordGate.h 2, CliffordGate.cnot 0 1 (by decide), CliffordGate.h 1, CliffordGate.s 1, CliffordGate.s 1], ?_, ?_, ?_⟩ · unfold is_1d_chain_circuit decide · decide · decide