Reverse extraction reproduces the source distribution and cq correlations
OpenQAlgorithms.Papers.Independent.Intakenext100.P30.reverse_extraction_shaperLet be a law on and a deterministic extractor with induced law . Assume and . There is a stochastic shaper , using private randomness, with when and , zero for other at such , and an arbitrary normalized conditional law at zero-mass , such that
For every cq eavesdropper channel , the complete joint state of the actual input with law and the shaper's output through that channel equals the extractor-output/eavesdropper state before reversal. Consequently every trace-distance privacy-amplification bound relative to a uniform and a fixed normalized reference holds unchanged for that actual-input joint state. This identity explains how reverse extraction preserves secrecy while reproducing the desired source law.
All alphabets are finite and nonempty, and output Hilbert spaces are finite dimensional and nonzero. A classical–quantum channel assigns a positive semidefinite, trace-one matrix to each input. Encoders may use private randomness; decoders are normalized POVMs. Codes are fixed independently of the message, with no supplied shared key or entanglement. Logarithms and entropies are in bits.
For uniform shaper input, the joint input/eavesdropper trace distance to the same uniform-product reference is at most whenever the original extracted state has distance at most . In particular an -private extractor yields uniform-input secrecy error at most , as used in section II.D.
import Definitions.Def_QAlgorithms_Papers_Independent_Intakenext100_P30
noncomputable section
open scoped BigOperators ComplexConjugate Matrix ComplexOrder
open Filter
namespace QAlgorithms.Papers.Independent.Intakenext100.P30
variable {X Y Z M U V A B C : Type*}
variable [Fintype X] [DecidableEq X] [Fintype Y] [DecidableEq Y]
variable [Fintype Z] [DecidableEq Z] [Fintype M] [DecidableEq M]
variable [Fintype U] [DecidableEq U] [Fintype V] [DecidableEq V]
variable [Fintype A] [DecidableEq A] [Fintype B] [DecidableEq B]
variable [Fintype C] [DecidableEq C]
attribute [local instance] Classical.propDecidable
/-- Section II.C, PDF p.4: reverse extraction samples P(X|U'=u) with private
randomness. At zero-mass u the normalized law can be arbitrary. Exact reproduction
uses the actual extracted law U'; uniform input is epsilon-close. The complete
cq identity preserves the actual-law privacy guarantee. With uniform input,
the secrecy error is at most delta + epsilon, hence 2 epsilon when delta=epsilon. -/
theorem reverse_extraction_shaper [Nonempty X] [Nonempty U] [Nonempty Z]
(p : RRDistribution X) (extract : X → U) (epsilon : ℝ) (he : 0 ≤ epsilon)
(hnear : tvDist (rrExtractedLaw p.prob extract) (rrUniform U) ≤ epsilon) :
∃ shape : U → RRDistribution X,
(∀ u, rrExtractedLaw p.prob extract u ≠ 0 → ∀ x,
(shape u).prob x =
if extract x = u then p.prob x / rrExtractedLaw p.prob extract u else 0) ∧
rrShapedLaw (rrExtractedLaw p.prob extract) shape = p.prob ∧
tvDist (rrShapedLaw (rrUniform U) shape) p.prob ≤ epsilon ∧
(∀ thetaZ : X → Matrix Z Z ℂ, RRIsCq thetaZ →
rrCqState (rrExtractedLaw p.prob extract) (rrPreprocess thetaZ shape) =
rrExtractedState p.prob extract thetaZ) ∧
(∀ (thetaZ : X → Matrix Z Z ℂ) (reference : Matrix Z Z ℂ) (delta : ℝ),
RRIsCq thetaZ → IsDensityMatrix reference → 0 ≤ delta →
traceNorm (rrExtractedState p.prob extract thetaZ -
rrUniformReference (U := U) reference) / 2 ≤ delta →
(traceNorm (rrCqState (rrExtractedLaw p.prob extract) (rrPreprocess thetaZ shape) -
rrUniformReference (U := U) reference) / 2 ≤ delta ∧
traceNorm (rrCqState (rrUniform U) (rrPreprocess thetaZ shape) -
rrUniformReference (U := U) reference) / 2 ≤ delta + epsilon)) := by sorry
end QAlgorithms.Papers.Independent.Intakenext100.P30
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
Let be nonempty finite types with decidable equality, let satisfy and , let be any function, and let . Put and , and suppose . Then there exist probability distributions on , one for every , such that, whenever , if , and otherwise; no such conditional formula is required when . They satisfy
For matrices, write , with the square root defined by continuous functional calculus. For every family of positive semidefinite matrices on with trace , put , define , and define . The same distributions satisfy . Moreover, for every such family , every positive semidefinite reference matrix on with trace , and every , writing , the hypothesis implies both
There is no upper bound imposed on or , and the fibres of may be empty.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.