Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Definition 1.4 and §2.2 — conditional-min-entropy quantum-proof extraction

Definition
MatrixQuantumSampler595_Correspondence_Supplement_ConditionalExtractor

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

p2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1probabilityquantum-informationrandomness-extraction

Let F:{0,1}n×[t]→{0,1}mF:\{0,1\}^n\times[t]\to\{0,1\}^mF:{0,1}n×[t]→{0,1}m be a deterministic map. For every finite quantum register E=CqE=\mathbb C^qE=Cq, a normalized cq source is a collection of positive semidefinite blocks σx\sigma_xσx​ with ∑xTr⁡σx=1\sum_x\operatorname{Tr}\sigma_x=1∑x​Trσx​=1. Its conditional min-entropy is Hmin⁡(X∣E)=−log⁡2pguess(X∣E)H_{\min}(X\mid E)=-\log_2 p_{\rm guess}(X\mid E)Hmin​(X∣E)=−log2​pguess​(X∣E), where guessing probability optimizes over all POVMs on EEE.

The map is a strong quantum-proof (k,η)(k,\eta)(k,η) extractor when every such source with Hmin⁡(X∣E)≥kH_{\min}(X\mid E)\ge kHmin​(X∣E)≥k and an independent uniform public seed I∈[t]I\in[t]I∈[t] satisfies

Δ(ρF(X,I)IE,τm⊗τ[t]⊗ρE)≤η.\Delta(\rho_{F(X,I)IE},\tau_m\otimes\tau_{[t]}\otimes\rho_E)\le\eta.Δ(ρF(X,I)IE​,τm​⊗τ[t]​⊗ρE​)≤η.

Here Δ\DeltaΔ is half the trace norm and ρE=∑xσx\rho_E=\sum_x\sigma_xρE​=∑x​σx​ is the actual marginal. The output and ideal states are the published base definitions. This predicate places no bound on qqq and allows singular, zero and noncommuting blocks. It supplies the security notion for the construction theorems, whose entropy assumption differs from bounded-storage security.

Formalization Note A ddd-bit seed is indexed by Fin⁡(2d)\operatorname{Fin}(2^d)Fin(2d) with its uniform distribution, which is just a relabelling of binary strings. The imported entropy is extended-real valued; only normalized sources are tested.

Definition code
import Mathlib
import Definitions.Def_MatrixQuantumSampler595_Correspondence_QuantumProofExtractor
import Definitions.Def_DIObliviousTransfer_pGuess

namespace MatrixQuantumSampler595.Correspondence.Supplement

/-- Definition 1.4 (p.4), §2.2 (pp.12–13): full conditional-min-entropy security.
The seed alphabet `Fin t` is uniform and independent; for a d-bit seed take t=2^d.
No storage dimension bound or restriction to commuting blocks is imposed. -/
def IsStrongConditionalExtractor {n m t : ℕ}
    (F : BitString n → Fin t → BitString m) (k η : ℝ) : Prop :=
  ∀ q : ℕ, ∀ σ : BitString n → Matrix (Fin q) (Fin q) ℂ,
    QAlgorithms.Papers.Independent.Advance50.P02.NormalizedBlocks σ →
    (k : EReal) ≤ DIObliviousTransfer.Hmin σ →
    QAlgorithms.traceDistance (strongOutputState F σ)
      (strongIdealState (m := m) (t := t) σ) ≤ η

end MatrixQuantumSampler595.Correspondence.Supplement
Source
Kuan Cheng, Ruiyang Wu, STOC 2027 submission #595 (October 2026), canonical held PDF (SHA-256 35e315808fa8dd8704a13971c8ca60bc3f785907b566f8914e4bb929c38b26af), Definition 1.4, p.4; §2.2, Eqs.(2.1)–(2.3), pp.12–13

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