Joint L1 error propagation for adaptive finite-state stages
ProvedInfoLossLAR.WorstCase.RegevSketch.adaptive_stages_l1Let be probability laws on the same finite state space. Suppose and are obtained by applying respective stochastic kernels and . Assume the initial distance is at most and that for every state the two conditional output laws at step have distance at most . Then
The state may retain the complete common random pool and every previous transcript, so the kernels may depend on that retained history. The theorem assumes a uniform conditional bound for each state; it does not derive that bound from an average error or assume that reuse of a pool gives independent steps. It is an error-accounting interface for classical stages in the DGS reduction and does not construct a quantum circuit.
Formalization Note. The laws are AFT.FiniteDist; is the sum of absolute differences of weights, without the factor used in total variation.
import Definitions.Def_InfoLossLAR_LoadedBatchBundle_05 set_option autoImplicit false open AFT open scoped BigOperators
theorem InfoLossLAR.WorstCase.RegevSketch.adaptive_stages_l1 {State : Type*} [Fintype State]
(actual ideal : ℕ → FiniteDist State)
(actualStep idealStep : ℕ → State → FiniteDist State)
(δ : ℝ) (error : ℕ → ℝ)
(hstart : (∑ x, |(actual 0).weight x-(ideal 0).weight x|) ≤ δ)
(hactual : ∀ i, actual (i+1) = (actual i).mix (actualStep i))
(hideal : ∀ i, ideal (i+1) = (ideal i).mix (idealStep i))
(hstep : ∀ i state, (∑ x, |(actualStep i state).weight x-(idealStep i state).weight x|) ≤ error i) :
∀ n, (∑ x, |(actual n).weight x-(ideal n).weight x|) ≤ δ + ∑ i ∈ Finset.range n, error i := by sorry