Coherent decoder query failures bound a complete joint output event
ProvedInfoLossLAR.WorstCase.RegevSketch.decoder_failure_to_joint_eventLet and be probability distributions on a finite set of complete sample pools, with total variation at most . Consider a normalized initial state, ideal isometries independent of the pool, and actual isometries that may reuse the same pool at every step. Suppose that at every ideal prefix the actual and ideal step outputs have the following common compute/copy/uncompute representation: both start from the same decoder workspace amplitudes and use the same pool-dependent uncomputation isometry, while one copies the decoder's actual answer and the other copies the correct answer. The ideal query amplitudes are normalized and do not depend on the pool.
If, at step for each query, the decoder's workspace-weighted failure probability averaged over is at most , then every event on the complete final measured register satisfies
The common uncomputation and exact ideal-prefix representation are explicit assumptions, not assertions that a BDD or DGS circuit has been constructed. Pool replacement is charged once, and no independence is assumed between steps.
Formalization Note. The decoder's workspace and copied answer register are retained as finite complex Euclidean spaces. The pool-distance hypothesis uses half the distance of its weights.
import Definitions.Def_RegevJointHybrid set_option autoImplicit false open scoped BigOperators open RegevJointHybrid
namespace InfoLossLAR.WorstCase.RegevSketch
theorem decoder_failure_to_joint_event
{Ω ι W β α : Type*} [Fintype Ω] [Fintype ι] [Fintype W]
[Fintype β] [Fintype α] [DecidableEq β]
(actualPool referencePool : Ω → ℝ)
(hp : ∀ sample, 0 ≤ actualPool sample) (hq : ∀ sample, 0 ≤ referencePool sample)
(hpmass : ∑ sample, actualPool sample = 1)
(hqmass : ∑ sample, referencePool sample = 1)
(sourceError : ℝ)
(hsource : (∑ sample, |actualPool sample-referencePool sample|) ≤ 2*sourceError)
(actual : Ω → ℕ → EuclideanSpace ℂ α →ₗᵢ[ℂ] EuclideanSpace ℂ α)
(ideal : ℕ → EuclideanSpace ℂ α →ₗᵢ[ℂ] EuclideanSpace ℂ α)
(count : ℕ) (state : EuclideanSpace ℂ α) (hstate : ‖state‖ = 1)
(event : α → Prop) (failure : ℕ → ℝ)
(amplitude : ℕ → ι → ℂ) (work : Ω → ℕ → ι → W → ℂ)
(readout : Ω → ℕ → ι → W → β) (answer : ℕ → ι → β)
(uncompute : Ω → ℕ → EuclideanSpace ℂ ((ι × W) × β) →ₗᵢ[ℂ] EuclideanSpace ℂ α)
(hamplitude : ∀ index < count, ∑ query, ‖amplitude index query‖^2 = 1)
(hfailure : ∀ index < count, ∀ query,
(∑ pool, referencePool pool *
∑ workState, if readout pool index query workState = answer index query
then 0 else ‖work pool index query workState‖^2) ≤ failure index)
(hactual : ∀ pool index, index < count →
actual pool index (evolve ideal index state) =
uncompute pool index (WithLp.toLp 2 (fun p : (ι × W) × β =>
if p.2 = readout pool index p.1.1 p.1.2 then
amplitude index p.1.1 * work pool index p.1.1 p.1.2 else 0)))
(hideal : ∀ pool index, index < count →
ideal index (evolve ideal index state) =
uncompute pool index (WithLp.toLp 2 (fun p : (ι × W) × β =>
if p.2 = answer index p.1.1 then
amplitude index p.1.1 * work pool index p.1.1 p.1.2 else 0))) :
|(∑ sample, actualPool sample * bornEvent event (evolve (actual sample) count state)) -
bornEvent event (evolve ideal count state)| ≤
sourceError + ∑ index ∈ Finset.range count, 4*Real.sqrt (failure index) := by sorry
end InfoLossLAR.WorstCase.RegevSketch