Quantum polynomial-time samplers and their output events (p.51)
DefinitionQuantumKtSoI_Supplement_QSamplercomplexity-theorykolmogorov-complexityp2o-gran-per-chapterp2o-plan-bookp2o-v1quantum-computing
A quantum polynomial-time sampler is a machine of Definition 3.1 together with a polynomial such that halts on every branch within steps on input . Its output distribution is , written .
For a property of pairs, is the total probability of the outputs with and ; an output that is not such a pair does not belong to the event.
This is the sampling convention of the average-case statement, Theorem 5.16.
Formalization Note The polynomial is taken in the normal form . Every polynomial is bounded by one of this form, and a machine that has halted on every branch has the same output law at every later deadline, so neither the samplers nor their laws change.
Definition code
import Mathlib
import Definitions.Def_QuantumKtSoI_pair
import Definitions.Def_QuantumKtSoI_CodedMachine
open Classical
noncomputable section
namespace QuantumKtSoI.Supplement
/-- A **quantum polynomial-time sampler** (p.51 of Myrisiotis, STOC 2027 submission, held version
sha256 6616571c…): a machine `S` of Definition 3.1 (a valid coded machine) and a polynomial
`q_S(n) = c(n+2)^k` such that `S` halts on every branch within `q_S(n)` steps on input `1ⁿ`. Its
output distribution is `w ↦ P_S(1ⁿ; q_S(n), w)`.
**Formalization Note** Every polynomial is bounded by one of the form `c(n+2)^k`, and a machine
that halts on every branch by a deadline has the same output law at every later deadline (a
halted branch is continued only by final records, Definition 3.4), so this normal form changes
neither the samplers nor their output laws. -/
structure QSampler where
B : CodedMachine
valid : B.Valid
c : ℕ
k : ℕ
halts : ∀ n : ℕ, B.toMachine.HaltsWithin (ones n) (c * (n + 2) ^ k)
namespace QSampler
variable (S : QSampler)
/-- The all-branch deadline `q_S(n) = c(n+2)^k`. -/
def time (n : ℕ) : ℕ := S.c * (n + 2) ^ S.k
/-- The probability `P_S(1ⁿ; q_S(n), w)` that `S(1ⁿ)` outputs `w`. -/
def outProb (n : ℕ) (w : List Bool) : ℝ := S.B.toMachine.outputProb (ones n) (S.time n) w
/-- `Pr_{(x,y) ∼ S(1ⁿ)}[|x| = |y| = n and E(x, y)]` (p.51): the total probability of the outputs
`⟨x, y⟩ = xy` with `x, y ∈ {0,1}ⁿ` and `E(x, y)`. An output that is not such a pair is outside the
event. -/
def pairProb (n : ℕ) (E : List Bool → List Bool → Prop) : ℝ :=
∑ x : Fin n → Bool, ∑ y : Fin n → Bool,
if E (List.ofFn x) (List.ofFn y) then S.outProb n (pair (List.ofFn x) (List.ofFn y)) else 0
end QSampler
end QuantumKtSoI.Supplement
Source
Myrisiotis, Failure of Symmetry of Information for Quantum Computations, STOC 2027 submission (held version, sha256 6616571c…), p.51 (sampling convention before Definition 5.1)