§2.2 Corollaries, item 1: wire permutation
OpenQAlgorithms.Papers.Independent.Intakethird100.P03.wire_permutationFor any permutation of the wire positions, there is a CNOT operation sequence with clean auxiliary work that performs the corresponding bit permutation using at most gates:
The assertion includes , when the empty computation is the identity. It concerns wire positions, rather than arbitrary permutations of Boolean words.
import Definitions.Def_QAlgorithms_Papers_Independent_Intakethird100_P03
noncomputable section
open scoped Matrix ComplexConjugate Kronecker
namespace QAlgorithms.Papers.Independent.Intakethird100.P03
open QAlgorithms.Papers.Independent.Renew46.P01 (cleanVector)
attribute [local instance] Classical.propDecidable
/-- PDF p.8, Corollary 1: permutation of wire positions, with clean work; the source's
4n is an upper bound on actual CNOT applications. The n=0 case is the identity. -/
theorem wire_permutation (n : ℕ) (p : Equiv.Perm (Fin n)) :
∃ (w : ℕ) (c : Circuit {Gate.ofMatrix2 cnot} (n + w)),
c.size ≤ 4 * n ∧ ∀ x : Qubits n,
act c.unitary (inputState x w) = inputState (fun i => x (p.symm i)) w := by sorry
end QAlgorithms.Papers.Independent.Intakethird100.P03
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
For every natural number , including , and every permutation of , there exist a natural number and a circuit on bits containing at most gates, all controlled-NOT gates, such that for every bit string ,
Here is the coordinate vector supported at the concatenation of with false bits; each gate acts on an ordered pair of distinct wires by , leaving other wires unchanged; and is the product of the embedded gate matrices, with gates applied in their list order. The ancillary bits return to false exactly. For , the gate bound requires an empty circuit.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.