Coupled quantum hybrid bound with conditional oracle disagreement
ProvedQAlgorithms.coupled_acceptance_boundLet be a finite query-input set, a finite additive commutative group of answers, and a finite workspace. Let be a quantum algorithm making standard additive oracle queries, with a fixed accepting event in its final computational-basis measurement.
Consider two finite families of oracle functions, and . Let be coupling weights whose row and column marginals are and , with
Thus both marginals are probability distributions. Suppose a real number satisfies the mismatch bound separately for every reference oracle and query input:
For every of positive marginal mass, this says that the conditional chance of disagreement at any fixed input, given , is at most .
Writing and for acceptance averaged under the two marginals, one has
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 and are derived explicitly, rather than quoted from the source's big- statement. The oracle adds its answer in ; 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.
import Definitions.Def_QAlgorithms_Defs_Query set_option autoImplicit false
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