Acceptance probability of a mixed-access algorithm
DefinitionPRUPermLayer_Supplement_mixAcceptProbp2o-gran-per-chapterp2o-plan-paperp2o-v1pseudorandom-unitariesquantum-cryptographyquery-complexity
For a mixed-access algorithm with effect and oracle , the probability of the output is
where is the final state. For unitary this lies in .
Formalization Note The real part of the inner product; for an effect the inner product is real.
Definition code
import Mathlib
import Definitions.Def_PRUPermLayer_Supplement_mixFinalState
namespace PRUPermLayer.Supplement
/-- The acceptance probability `Pr[A^{U,U†} = 1] = ⟨ψ| M |ψ⟩` of a mixed-access algorithm with
oracle `U`, `ψ` its final state (Shen–Zhong, *Pseudorandom Unitaries from a Random Permutation and One Layer of Single-Qubit Gates*, manuscript (STOC 2027 submission; held version sha256 395fcfa3…5bcb), §2.2, p.9 (PDF p.11); Theorem 1.6, p.4 (PDF p.6)).
**Formalization Note** The real part of `⟨ψ, M ψ⟩`; for an effect `M` the inner product is real,
and for a unitary `U` the final state is a unit vector, so the value lies in `[0, 1]`. -/
noncomputable def mixAcceptProb {n q : ℕ} (alg : MixAlg n q)
(U : Matrix (Fin (2 ^ n)) (Fin (2 ^ n)) ℂ) : ℝ :=
(dotProduct (star (mixFinalState alg U)) (Matrix.mulVec alg.M (mixFinalState alg U))).re
end PRUPermLayer.Supplement
Source
Shen–Zhong, Pseudorandom Unitaries from a Random Permutation and One Layer of Single-Qubit Gates, manuscript (STOC 2027 submission; held version sha256 395fcfa33ec861a7e9c10d88cfcefc2794b77ad1674c02661c9298c5ba565bcb), §2.2, p.9 (PDF p.11); Theorem 1.6, p.4 (PDF p.6)