AFTD Auto-Formalizing Theoretical Domains

op_757_all_to_all_cnot_three_exists

theoremverifiedformalization

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.

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

    lines 6–8

    uses CliffordGate.cnot, CliffordGate.h, CliffordGate.s

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

    line 9

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

    line 10

      · 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$.

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