Alphabeta Math
LemmaStatement: AI-adaptedProof: AI-adaptedPipeline-generatedjudge pass (gpt-6-luna)
How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

  • Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
  • AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
  • AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

A SWAP Is Three CNOTs

Statement

On two ordered qubit wires, let S be the wire-swap permutation ∣a,b⟩↦∣b,a⟩. Let C12 be the CNOT with wire 1 controlling wire 2, so C12∣a,b⟩=∣a,b⊕a⟩, and define the reverse orientation by C21∣a,b⟩=∣a⊕b,b⟩, extending both actions linearly; here ⊕ is addition modulo two. The operator identity

S=C12C21C12

holds, where products act right to left. Therefore the swap of two wires has an exact three-CNOT implementation with no ancillas.

Facts & Assumptions

Given: Two ordered qubit factors with computational basis ∣a,b⟩, a,b∈{0,1}.

[F1]

The first-to-second CNOT has action C12∣a,b⟩=∣a,b⊕a⟩ (CNOT and Control-Target Order).

[F2]

The swap wire permutation sends ∣a,b⟩ to ∣b,a⟩ (Ordered tensor registers, their inner product, and wire permutations).

[F3]

The four computational basis vectors form a basis of the two-qubit register (The product basis is orthonormal and tensor dimensions multiply).

Proof

technique · direct finite verification

Given: The basis actions in [F1]–[F3] and the explicit reverse CNOT action in the Statement.

1.1givenF1F3algebra

Both CNOT maps are involutions: applying either twice uses x⊕x=0 and returns every basis vector to itself, so their linear extensions permute the orthonormal basis [F3] and are exact unitary gates. Now for any a,b∈{0,1}, apply the three maps from right to left: C12∣a,b⟩=∣a,b⊕a⟩, then C21 sends this to ∣a⊕(b⊕a),b⊕a⟩=∣b,b⊕a⟩, and the final C12 sends it to ∣b,(b⊕a)⊕b⟩=∣b,a⟩. The last equalities use a⊕a=b⊕b=0.

2.1F2F3step 1.1algebra∎

This is exactly the action of S in [F2] on every vector of the basis [F3]. Two linear maps agreeing on a basis agree on every vector, so S=C12C21C12. The displayed product contains three CNOTs on the same two wires and uses no ancillary register.

Depends on

Used by

Dependency tree · two levels

18 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources