Collision test on a product input: ,
DefinitionPRUPermLayer_Supplement_productCollisionAcceptLet , let and let be the product input. Fix an oracle on and a number of queries . The -query collision test on queries times, measures each output in the computational basis and accepts if two of the outcomes are equal. For a fixed oracle the outcomes are independent samples from
so the test accepts with probability
This is the non-adaptive test that attains the lower bound of Theorem 1.3 (with in the paper's proof). It generalizes the mission's collision test on to an arbitrary product input.
Formalization Note Basis labels are Fin (2^n), read as bit strings through bitsEquivFin (wire most significant); factor sits on wire , as in the published product layer. The formula is extended to arbitrary vectors and arbitrary matrices ; the theorem that uses it requires unit vectors and integrates only over unitary . On those physical inputs, the test never accepts when .
import Mathlib
import Definitions.Def_QAlgorithms_Defs_Basic
namespace PRUPermLayer.Supplement
/-- The acceptance probability of the `k`-query **collision test on a product input** with a fixed
oracle `U` (Shen–Zhong, *Pseudorandom Unitaries from a Random Permutation and One Layer of Single-Qubit Gates*, manuscript (STOC 2027 submission; held version sha256 395fcfa3…5bcb), Theorem 1.3, p.3 (PDF p.5): "a non-adaptive algorithm that queries one fixed
product state at most min{t, ⌊(3/2)^{n/2}⌋} times and looks for a collision among the measured
outputs"; §7.2, p.24 (PDF p.26): "Query |m⟩^{⊗n} k times, measure all outputs and accept if two of
them are equal. … Conditioned on the oracle, the k outcomes are independent samples from p").
The input is the product state `ψ = φ₀ ⊗ ⋯ ⊗ φ_{n−1}`, `ψ(y) = ∏ᵢ φᵢ(yᵢ)` where `yᵢ` is bit `i`
of the label `y`. Each of the `k` outputs `Uψ` is measured in the computational basis, giving
`k` independent samples of `p_x = |⟨x|Uψ⟩|²`, and the test accepts iff two samples are equal:
`1 − Σ_{x : [k] → [N] injective} ∏ᵢ p_{x_i}`.
**Formalization Note** The label `y : Fin (2 ^ n)` is the bit string
`(QAlgorithms.bitsEquivFin n).symm y`, and factor `φ i` sits on wire `i`, as in the published
`PRUPermLayer.productLayer`. The formula is extended to every `φ` and every matrix `U`; the
statements that use it require unit vectors `φ i` and integrate only over unitary `U`, so `p` is a
probability distribution. On those physical inputs, the test never accepts when `k ≤ 1`. -/
noncomputable def productCollisionAccept (n k : ℕ) (φ : Fin n → Bool → ℂ)
(U : Matrix (Fin (2 ^ n)) (Fin (2 ^ n)) ℂ) : ℝ :=
1 - ∑ x ∈ Finset.univ.filter (fun x : Fin k → Fin (2 ^ n) => Function.Injective x),
∏ i, ‖Matrix.mulVec U (fun y => ∏ j, φ j ((QAlgorithms.bitsEquivFin n).symm y j)) (x i)‖ ^ 2
end PRUPermLayer.Supplement