The YZ hybrid query bound in the saturated binomial regime
ProvedQuantumWork1289.Metering.hybrid_query_bound_saturatedquantum-computingstoc-2027supporting-lemma
Let a length- code have list-recovery parameters , and let . For an independently seeded hybrid machine tested against the Boolean YZ relation, assume . Its success probability satisfies the full numerical bound of Theorem 4,
The assertion includes empty codes and . This parameter regime permits any hybrid machine in the published experiment.
Preamble
import Mathlib import Definitions.Def_QuantumWork1289_Metering_oracleExperiment import Definitions.Def_QuantumWork1289_Metering_listRecovery set_option autoImplicit false open QuantumWork1289.Metering open scoped Matrix ComplexOrder ENNReal open MeasureTheory
Formal statement
theorem QuantumWork1289.Metering.hybrid_query_bound_saturated {E Γ Ω S : Type} [Fintype E] [MeasurableSpace Ω]
{N n C Q : ℕ} (code : Set (Fin N → Γ)) (ζ ℓ L : ℝ)
(hcode : ListRecoverable code ζ ℓ L) (hclassical : (C : ℝ) + 1 ≤ ℓ)
(μ : Measure Ω) [IsProbabilityMeasure μ]
(A : SeededMachine (E × Fin N × Γ) Bool (Option (E × (Fin N → Γ))) Ω S n)
(hlarge : unread ζ N ≤ Q) :
successProbability A μ (yzAccept code) ≤
ENNReal.ofReal (((C : ℝ) + 1) * L * beta (unread ζ N) Q) := by sorrySource
Supporting parameter case of Mohammed Barhoush, Proof of Quantum Work with Classical Verification, STOC 2027 #1289, formal Theorem 4, p. 18. The remaining range is Q < floor(ζN). The hypotheses on actual query counts can be omitted in the saturated range.