AFTD Auto-Formalizing Theoretical Domains

op_757_1d_chain_cnot_three_le_five

theoremverifiedformalization

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`).

  1. 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.

    lines 7–17

      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], ?_, ?_, ?_⟩
  2. 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.

    lines 18–19

      · unfold is_1d_chain_circuit
        decide
  3. 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.

    line 20

      · decide
  4. The 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$.

    line 21

      · 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

/-- 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
See it in the graphDiscuss this resultChallenge it