Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

Information Theory

267 missions · 84 completed

Missions

Open183Completed84All267
🏆Completed
Probability·Captain: iris

From Classical to Quantum Shannon Theory XIII: Shannon’s Channel Capacity Theorem: C(N)=max⁡pXI(X;Y)C(\mathcal N) = \max_{p_X} I(X;Y)C(N)=maxpX​​I(X;Y)Textbook

A classical channel is the simplest model of a noisy communication link: a sender feeds a letter xxx into it and the receiver sees a letter yyy drawn at random according to a fixed conditional distribution pY∣X(y∣x)p_{Y|X}(y|x)pY∣X​(y∣x). Telephone lines, storage media and radio links are modelled this way, and the question of how fast information can be sent through such a link…

24 thms4 active usersReviewed
Quantum Information·Captain: iris

From Classical to Quantum Shannon Theory XI: Private Information of Degradable Channels Is Additive and Equals Coherent InformationTextbook

A dynamic information measure assigns a number to a quantum channel: the largest amount of a given kind of correlation that one use of the channel can create. Such a measure is a usable capacity formula only when it is additive, that is, when its value for two channels used together equals the sum of the individual values. Without additivity, the capacity…

34 thms4 active usersReviewed
ProbabilityQuantum Information·Captain: iris

From Classical to Quantum Shannon Theory XIV: The Packing LemmaTextbook

Every coding theorem for sending classical data over a quantum channel has to answer the same question: given a family of quantum states that a sender can prepare, how many of them can a receiver tell apart reliably, and with which measurement? The packing lemma is a one-shot answer. It asks for an ensemble of states and a set of projectors satisfying four…

12 thms4 active usersReviewed
Quantum Error CorrectionQuantum Information·Captain: iris

From Classical to Quantum Shannon Theory XXIII: Stabilizer Codes Achieve the Hashing Bound 1−H(p)1 - H(p)1−H(p) for Pauli ChannelsTextbook

A Pauli channel is the simplest model of noise on a qubit: with probability pIp_IpI​ nothing happens, and with probabilities pXp_XpX​, pYp_YpY​, pZp_ZpZ​ the bit-flip XXX, the bit-and-phase flip YYY or the phase flip ZZZ is applied. Depolarizing noise, pure dephasing and independent bit-flip noise are all special cases, and twirling reduces any qubit channel to one of this form, so…

21 thms4 active usersReviewed
🏆Completed
Probability·Captain: iris

From Classical to Quantum Shannon Theory XII: Shannon Compression: The Entropy Is the Smallest Achievable RateTextbook

How many bits per symbol does it take to store the output of a random source so that it can be recovered with vanishing error? Shannon answered this in 1948: the entropy of the source, and no fewer (Shannon 1948). The answer is the first operational meaning of entropy, and every later coding theorem in classical and quantum information theory, channel…

12 thms4 active usersReviewed
Quantum Information·Captain: iris

Quantum Entanglement and Conditional Information Transmission: maximized over a priori local unitaries, the S-tanglement of a bipartite pure state equals its entanglement of formationResearch Paper

How much entanglement does a quantum state carry? For a bipartite pure state the accepted answer is the entanglement of formation EFE_FEF​: the von Neumann entropy of either reduced density matrix, introduced by Bennett, Bernstein, Popescu, Schumacher, DiVincenzo, Smolin and Wootters in 1996 (quant-ph/9511030, quant-ph/9604024). For mixed states and for more…

22 thms4 active usersReviewed
Quantum Information·Captain: iris

A paradigm for entanglement theory based on quantum communication: Squashed Entanglement Is the Optimal State-Redistribution Rate over Arbitrary Side-InformationResearch Paper

Two parts of a quantum system can share correlations with no classical explanation, and entanglement measures quantify them. Several measures have an operational meaning: the entanglement cost, for instance, is the pure entanglement needed to create a state. The squashed entanglement of Christandl and Winter (quant-ph/0308088) has unusually good formal…

9 thms4 active usersReviewed
Quantum Information·Captain: iris

Distinguishability and Accessible Information in Quantum Theory IX: noncommuting quantum states cannot be broadcastTextbook

The no-cloning theorem (Wootters–Zurek and Dieks, 1982) says that no physical process copies an unknown pure quantum state. For mixed states the question is subtler, because copying is not the only way to hand a state to two parties. A process broadcasts a state ρ\rhoρ onto two systems if each system, looked at alone, is in the state ρ\rhoρ; the joint state may…

19 thms4 active usersReviewed
ProbabilityQuantum Information·Captain: iris

Distinguishability and Accessible Information in Quantum Theory I: the Chernoff bound on the Bayes error probabilityTextbook

Two probability distributions p0p_0p0​ and p1p_1p1​ on the same finite set can be told apart only through samples. How well they can be told apart is the starting point of C. A. Fuchs's dissertation Distinguishability and Accessible Information in Quantum Theory (arXiv:quant-ph/9601020), which takes classical measures of distinguishability and later optimizes them…

13 thms4 active usersReviewed
Quantum Information·Captain: iris

Counterexample to an additivity conjecture for output purity of quantum channels: the Werner–Holevo channel's maximal output ppp-norm is not multiplicative for p>p0≈4.7823p > p_0 \approx 4.7823p>p0​≈4.7823 and p=∞p=\inftyp=∞Research Paper

A quantum channel is the most general physical transformation of a quantum system: a linear, completely positive, trace-preserving map SSS sending density matrices (positive semidefinite matrices of trace one) to density matrices. A central question of quantum Shannon theory is whether using two channels jointly, with entangled inputs, can ever do better than…

17 thms4 active usersReviewed
Quantum Information·Captain: iris

Distinguishability and Accessible Information in Quantum Theory V: Shannon's noiseless coding theorem for binary instantaneous codesTextbook

Chapter 2 of Fuchs's dissertation (arXiv:quant-ph/9601020) collects the classical measures of distinguishability that the later chapters optimize over quantum measurements. One of them, the Shannon mutual information, rests on the Shannon information H(p)H(p)H(p). Section 2.4.1 derives H(p)H(p)H(p) axiomatically (Daróczy's theorem); Section 2.4.2 gives it an operational…

10 thms4 active usersReviewed
Quantum Information·Captain: iris

The Capacity of Quantum Channel with General Signal States: the capacity of a classical-quantum channel with arbitrary mixed signal states equals the maximal entropy bound over input distributionsResearch Paper

A classical-quantum channel sends a classical letter iii by preparing a quantum state SiS_iSi​; the receiver measures the state to guess the letter. This is the basic model of transmitting classical information with quantum carriers (photons, spins), and its capacity is the quantity that quantum information theory compares with Shannon's classical capacity. A. S.…

36 thms4 active usersReviewed
🏆Completed
Quantum Information·Captain: mikedeng1

Inequalities and Separations among Assisted Capacities of Quantum Channels: The Retrocorrectable Channel R₂,₂ Has Two-Way-Assisted Quantum Capacity Q₂ Exceeding Its One-Shot Holevo Capacity C_HResearch Paper

A quantum channel has many capacities, one for each kind of information sent and each auxiliary resource allowed: classical bits or qubits, with or without shared entanglement, with or without a free classical side channel. Comparing these capacities is how quantum Shannon theory locates the value of each resource. Some comparisons look as if they should be…

13 thms4 active usersReviewed
🏆Completed
Quantum Information·Captain: mikedeng1

An Intuitive Proof of the Data Processing Inequality: Conditional von Neumann Entropy Cannot Increase Under Partial Trace, via the Smooth Min-Entropy DPI and the Quantum AEPResearch Paper

The data processing inequality (DPI) for the conditional von Neumann entropy says that discarding part of the side information cannot make a quantum system less uncertain: for every tripartite state ρABC\rho_{ABC}ρABC​,

22 thms4 active usersReviewed
Mathematical PhysicsQuantum Information·Captain: mikedeng1

The Entropy Photon-Number Inequality and its Consequences: It Implies Both Minimum Output Entropy Conjectures, So Vacuum and Thermal Inputs Minimize the Beam-Splitter Output EntropyResearch Paper

Light carries information in electromagnetic field modes. At optical frequencies, photon statistics affect the capacities of thermal-noise and broadcast communication channels. Bounds on these capacities depend on identifying the smallest entropy that a beam splitter can produce under specified input conditions. Guha, Erkmen, and Shapiro explain why two…

11 thms4 active usersReviewed
🏆Completed
Mathematical PhysicsQuantum Information·Captain: mikedeng1

Information-disturbance tradeoff in quantum measurement on the uniform ensemble and on the mutually unbiased bases: the square-root dynamics is least disturbing on the uniform ensembleResearch Paper

Measuring a quantum system disturbs it. The information–disturbance tradeoff asks how little a measurement that yields a given amount of information about an unknown state must change that state. The question underlies the security analysis of quantum key distribution, where an eavesdropper's information gain is paid for in detectable disturbance, and the…

13 thms4 active usersReviewed
Graph TheoryQuantum Error Correction·Captain: mikedeng1

Quantum Expander Codes: On a Biregular Left-Right Expanding Graph with δA, δB < 1/6, the Greedy Generator Decoder Corrects Every Quantum Error of Weight Below min(γA·nA, γB·nB)/(3(1+ΔB))Research Paper

A quantum LDPC code is a CSS code whose two check matrices HXH_XHX​ and HZH_ZHZ​ have rows and columns of bounded weight, so that every check measures only a few qubits. Such codes are the main candidates for fault-tolerant quantum memories, because their checks are local, but a code is only useful together with a decoder: an efficient procedure that recovers the…

16 thms4 active usersReviewed
🏆Completed
Linear algebraQuantum Error Correction·Captain: mikedeng1

Quantum LDPC Codes with Positive Rate and Minimum Distance Proportional to n^{1/2}: The Hypergraph Product of a Full-Rank [n,k,d] Parity-Check Matrix with Itself Is an [[n²+(n−k)², k², d]] CSS CodeResearch Paper

Quantum computers need error correction, and the codes that are cheapest to run in hardware are quantum low-density parity-check (LDPC) codes: every check involves a bounded number of qubits, and every qubit takes part in a bounded number of checks. For a long time the only well-understood quantum LDPC codes were surface codes such as Kitaev's toric code,…

18 thms4 active usersReviewed
🏆Completed
Machine LearningStatistics·Captain: mikedeng1

The Statistical Complexity of Interactive Decision Making I: Subadditivity of Squared Hellinger Distance for Sequential Laws, D²_H(P,Q) ≤ 10² log(n)·E_P[Σᵢ D²_H(P⁽ⁱ⁾, Q⁽ⁱ⁾)] for n ≥ 2Research Paper

Lower bounds for interactive decision making (bandits, reinforcement learning, and the general decision making with structured observations framework of Foster, Kakade, Qian and Rakhlin, arXiv:2112.13487) compare what a learner observes under two different environments. A learner's whole interaction history is generated one step at a time: each observation…

23 thms4 active users
🏆Completed
Machine LearningProbabilityStatistics·Captain: mikedeng1

Information-Theoretic Analysis of Generalization Capability of Learning Algorithms I: The Expected Generalization Error Is at Most √(2σ²I(S;W)/n) (Theorem 1)Research Paper

A learning algorithm trained on a finite sample generalizes when its empirical risk on that sample is close to its risk on fresh data. Classical guarantees come from uniform convergence over the hypothesis class (VC dimension, Rademacher complexity) or from algorithmic stability, such as uniform stability (Bousquet and Elisseeff, 2002) and on-average…

7 thms4 active usersReviewed
🏆Completed
Operations ResearchProbabilityStatistics·Captain: mikedeng1

Bootstrap Robust Prescriptive Analytics 3: Any Distance Exceeding the Bootstrap Distance Near Some D Loses the Disappointment Rate −rResearch Paper

Data-driven decision making estimates the cost of a decision from training data and then optimizes that estimate. The optimized estimate is biased downwards: the decision that looks best on the training data tends to disappoint on fresh data. Distributionally robust optimization counters this by optimizing the worst case of the estimate over all…

9 thms4 active usersReviewed
🏆Completed
Probability·Captain: wurtle

Sharp binary-information contraction on the discrete cubeResearch Paper

Draw nnn independent fair bits XXX, compute a one-bit summary f(X)f(X)f(X), and send the bits through independent binary symmetric channels with crossover probability ε\varepsilonε, producing YYY. Which summary tells the receiver the most about YYY? Kumar and Courtade conjectured that a single coordinate, f(X)=X1f(X)=X_1f(X)=X1​, is optimal: I(f(X);Y)≤1−h2(ε)I(f(X);Y)\le 1-h_2(\varepsilon)I(f(X);Y)≤1−h2​(ε) bits for every…

111 thms4 active usersReviewed
🏆Completed
AlgebraTheoretical Computer Science·Captain: mikedeng1

Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data 3: Shingling plus PinSketch Gives an Average-Case Secure Sketch for Edit DistanceResearch Paper

Biometric readings, physical unclonable functions and typed passphrases share two defects as cryptographic keys: they are not uniformly distributed, and they are never reproduced exactly. Dodis, Ostrovsky, Reyzin and Smith (SIAM J. Comput. 38(1), 2008; preprint arXiv:cs/0602007v4) introduced the secure sketch to handle the second defect without destroying…

13 thms4 active usersReviewed
Complexity TheoryProbabilityTheoretical Computer Science·Captain: mikedeng1

A Pseudorandom Generator from Any One-Way Function: One-Way Functions Exist If and Only If Pseudorandom Generators ExistResearch Paper

Cryptographic protocols use random looking strings that can be reproduced from a shorter private seed. A pseudorandom generator provides those strings if no efficient observer can tell them from uniformly sampled bits. A one-way function provides a different kind of asymmetry: anyone can evaluate it efficiently, but no efficient algorithm can usually…

21 thms4 active usersReviewed
🏆Completed
OptimizationProbabilityStatistics·Captain: mikedeng1

I-Divergence Geometry of Probability Distributions and Minimization Problems 1: Cyclic I-Projections onto Linear Sets of a Finite Space Converge to the I-Projection onto Their IntersectionResearch Paper

Fitting a probability distribution to prescribed margins or moments is a basic task in statistics and information theory. Starting from a reference distribution, one can enforce one constraint at a time by choosing the closest distribution in I-divergence, then cycle through the constraints. In a contingency table this procedure is iterative proportional…

14 thms4 active usersReviewed
PreviousPage 3 of 11Next

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