Classical random-parity verification
OpenQAlgorithms.Papers.Independent.Intakenext100.P87.classical_hashingLet , let , and fix distinct strings before the questions are selected. Choose masks independently and uniformly from the nonzero -bit masks. The parity of mask on is modulo two. Then
Nonzero masks encode the source's fair questions. The empty sequence of questions has collision probability one. No equality with is claimed for this mask distribution.
import Definitions.Def_QAlgorithms_Papers_Independent_Intakenext100_P87
noncomputable section
namespace QAlgorithms.Papers.Independent.Intakenext100.P87
open scoped Matrix ComplexConjugate
open QAlgorithms.Measurements
/-- PDF pp.7--8: collision probability is at most 2^(-m), including m=0.
No equality to 2^(-m) is asserted for nonzero masks. -/
theorem classical_hashing (N m : ℕ) (hN : 0 < N) (hm : m < N)
(x y : Qubits N) (hxy : x ≠ y) :
hashingCollisionProbability m x y ≤ (2 : ℝ)⁻¹ ^ m := by sorry
end QAlgorithms.Papers.Independent.Intakenext100.P87
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
For every positive integer , every natural number , and every pair of distinct Boolean strings of length , let be the set of all Boolean strings of length except the all-false string. The fraction of ordered tuples satisfying
is at most . Tuple entries may repeat, and the fraction is the number of satisfying tuples divided by the total number of tuples. The hypotheses make that denominator positive. The case is included, with fraction and bound .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.