Unnumbered Appendix D: balanced-map random permutations are universal2
ProvedQAlgorithms.Papers.Independent.Advance50.P23.balanced_permutation_hashAll classical alphabets are finite and nonempty and all quantum systems are finite dimensional. A cq channel has positive semidefinite outputs of trace one; every input law is nonnegative and sums to one. Logarithms are natural. Write for the paper's Petz information, for its Gallager information, for classical Rényi entropy, and for Holevo information. Matrix powers vanish on the kernel, including exponent zero. Write , , for the number of distinct eigenvalues of , and for that of . The supported spectral spread is and .
Let be finite nonempty sets and let have balanced fibres: every fibre has size , equivalently . Sample uniformly from all permutations of . Then
Thus is universal2. Balance includes the necessary divisibility; for singleton the distinct-pair condition is vacuous.
This result supplies the corresponding finite-dimensional information or coding interface for the paper's security analysis.
import Definitions.Def_QAlgorithms_Papers_Independent_Advance50_P23
noncomputable section
namespace QAlgorithms.Papers.Independent.Advance50.P23
open scoped BigOperators Matrix ComplexConjugate ComplexOrder ENNReal
open Filter
open QAlgorithms.Papers.Independent.Information100.P56
(IsLaw entropy average holevo uniform ProjectiveRep orbit productOutput)
open QAlgorithms.Papers.Independent.Information100.P71 (supportPower)
open QAlgorithms.Papers.Independent.Dependency50.P21 (IsSupported relativeEntropy)
open QAlgorithms.Papers.Independent.Dependency50.P28 (pinch logNonnegativeExtended)
attribute [local instance] Classical.propDecidable Classical.decEq
variable {X A Z B E : Type} [Fintype X] [Fintype A] [Fintype Z]
[Fintype B] [DecidableEq B] [Fintype E] [DecidableEq E]
/-- PDF p.30, Appendix D: a balanced fixed map composed with a uniform permutation
is universal2. Singleton A is allowed, with no distinct input pairs. -/
theorem balanced_permutation_hash {D : Type} [Fintype D] [Nonempty D] [Nonempty A]
(f : A → D) (hbalanced : hayashiBalanced f) :
Universal2 (uniform : Equiv.Perm A → ℝ) (fun g a => f (g a)) := by sorry
end QAlgorithms.Papers.Independent.Advance50.P23
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
Let be a finite nonempty type with decidable equality, let be a finite nonempty type, and let satisfy
For every pair of distinct , the uniformly weighted collision probability over all permutations of satisfies
If has one element, the assertion about distinct pairs is vacuous.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.