Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Coupled quantum hybrid bound with conditional oracle disagreement

Proved
QAlgorithms.coupled_acceptance_bound

by dmilosch · Nov 17, 2026 · Mathlib 0df444a (Lean v4.33.1)

couplinghybrid-argumentquantum-query-complexitywelded-trees

Let III be a finite query-input set, KKK a finite additive commutative group of answers, and WWW a finite workspace. Let AAA be a quantum algorithm making q≥0q\geq 0q≥0 standard additive oracle queries, with a fixed accepting event EEE in its final computational-basis measurement.

Consider two finite families of oracle functions, Ha:I→KH_a:I\to KHa​:I→K and Gb:I→KG_b:I\to KGb​:I→K. Let w(a,b)≥0w(a,b)\geq 0w(a,b)≥0 be coupling weights whose row and column marginals are μ(a)\mu(a)μ(a) and ν(b)\nu(b)ν(b), with

∑bw(a,b)=μ(a),∑aw(a,b)=ν(b),∑aμ(a)=1.\sum_b w(a,b)=\mu(a),\qquad \sum_a w(a,b)=\nu(b),\qquad \sum_a\mu(a)=1.b∑​w(a,b)=μ(a),a∑​w(a,b)=ν(b),a∑​μ(a)=1.

Thus both marginals are probability distributions. Suppose a real number ε\varepsilonε satisfies the mismatch bound separately for every reference oracle and query input:

∑b: Gb(x)≠Ha(x)w(a,b)≤ε μ(a)for every a,x.\sum_{b:\,G_b(x)\ne H_a(x)}w(a,b) \leq\varepsilon\,\mu(a) \qquad\text{for every }a,x.b:Gb​(x)=Ha​(x)∑​w(a,b)≤εμ(a)for every a,x.

For every aaa of positive marginal mass, this says that the conditional chance of disagreement at any fixed input, given aaa, is at most ε\varepsilonε.

Writing pH(A,E)p_H(A,E)pH​(A,E) and pG(A,E)p_G(A,E)pG​(A,E) for acceptance averaged under the two marginals, one has

pH(A,E)≤2pG(A,E)+8q2ε.p_H(A,E)\leq 2p_G(A,E)+8q^2\varepsilon.pH​(A,E)≤2pG​(A,E)+8q2ε.

The event is the same for all sampled oracles. The theorem isolates the quantum part of a distribution-comparison argument: any coupling with the stated conditional mismatch control gives an acceptance bound for every query algorithm.

Formalization Note. This is a general finite-coupling form of the final hybrid and accepting-projection argument in Section 4.4, proof of Lemma 4.13, of Carolan et al. The constants 222 and 888 are derived explicitly, rather than quoted from the source's big-OOO statement. The oracle adds its answer in KKK; bitwise-XOR answers are a special case. The formal statement also allows zero queries and real-valued coupling weights. It does not require additional nonnegativity hypotheses on the marginals, since these follow from the coupling equations.

Preamble
import Definitions.Def_QAlgorithms_Defs_Query

set_option autoImplicit false
Formal statement
namespace QAlgorithms

theorem coupled_acceptance_bound {ι κ W α β : Type*} [Fintype ι] [Fintype κ] [Fintype W]
    [Fintype α] [Fintype β] [DecidableEq ι] [DecidableEq κ] [DecidableEq W]
    [AddCommGroup κ] {q : ℕ} (A : QueryAlg ι κ W q)
    (H : α → ι → κ) (G : β → ι → κ) (w : α → β → ℝ) (μ : α → ℝ) (ν : β → ℝ)
    (ε : ℝ) (hw : ∀ a b, 0 ≤ w a b)
    (hrow : ∀ a, ∑ b, w a b = μ a) (hcol : ∀ b, ∑ a, w a b = ν b)
    (hμ : ∑ a, μ a = 1)
    (hdis : ∀ a x, (∑ b, if G b x ≠ H a x then w a b else 0) ≤ ε * μ a)
    (acc : ((ι × κ) × W) → Prop) [DecidablePred acc] :
    (∑ a, μ a * probEvent (A.finalState (xorOracle (H a))) acc) ≤
      2 * (∑ b, ν b * probEvent (A.finalState (xorOracle (G b))) acc) +
      8 * (q : ℝ) ^ 2 * ε := by sorry

end QAlgorithms
Source
Derived generalization of Carolan, Childs, Coudron, Gilani, Miloschewsky, Podder, Algorithmic Wave-Particle Duality: Pathfinding in Welded Trees is Hard, https://arxiv.org/abs/2611.05912v1, Section 4.4, proof of Lemma 4.13, pp.41–42: final hybrid inequality after (77) and accepting-projection argument. Constants 2 and 8 are derived explicitly in this formalization.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me