Proof of Theorem 3.6 — each permutation in the transposition chain is uniform
ProvedBBBV.RandomPermutation.piChain_uniformp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1random-permutationtransposition
In the transposition chain, for every index , the permutation is uniformly distributed among all permutations of length- binary strings:
The construction also satisfies for every sampled outcome. These facts identify both the law of the oracle and the distinguished inverse image at each stage.
Preamble
import Mathlib import Definitions.Def_BBBV_RandomPermutation_Chain
Formal statement
namespace BBBV.RandomPermutation
theorem piChain_uniform {n T : ℕ} (i : ℕ) (hi : i ≤ T + 1)
(σ : Equiv.Perm (BBBV.RandomOracle.Str n)) :
(((Finset.univ.filter fun ω : Ω n T => piChain ω i = σ).card : ℝ) /
(Fintype.card (Ω n T) : ℝ) =
1 / (Fintype.card (Equiv.Perm (BBBV.RandomOracle.Str n)) : ℝ)) ∧
(∀ ω : Ω n T, piChain ω i (x ω i) = BBBV.RandomOracle.ones n) := by sorry
end BBBV.RandomPermutation
Source
Bennett, Bernstein, Brassard and Vazirani, Strengths and weaknesses of quantum computing, arXiv:quant-ph/9701001v1, p. 10, proof of Theorem 3.6, transposition-chain paragraph
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.