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
Quantum Information·Captain: iris

From Classical to Quantum Shannon Theory XVI: Schumacher Compression: The Quantum Data Compression Limit Equals the Quantum EntropyTextbook

A quantum information source emits pure states ∣ψx⟩|\psi_x\rangle∣ψx​⟩ of a finite-dimensional system AAA at random, with probabilities pX(x)p_X(x)pX​(x). To a receiver who does not know the labels xxx, each emission is described by the density operator ρ=∑xpX(x)∣ψx⟩⟨ψx∣\rho = \sum_x p_X(x)|\psi_x\rangle\langle\psi_x|ρ=∑x​pX​(x)∣ψx​⟩⟨ψx​∣. Storing or transmitting such states is expensive: noiseless qubit channels are…

26 thms3 active usersReviewed
Quantum Information·Captain: iris

From Classical to Quantum Shannon Theory VIII: The AFW Inequality for Conditional Entropy, Including Its Classical–Quantum RefinementsTextbook

Converse theorems in quantum Shannon theory follow one pattern. A good protocol produces a state that is close, in trace distance, to the ideal state it should produce. To bound the rate of the protocol, that statement about distance has to become a statement about entropies: if two states are close, their entropies, conditional entropies and mutual…

23 thms3 active usersReviewed
Quantum Information·Captain: iris

Explicit capacity-achieving receivers for optical communication and quantum reading: sequential decoding achieves the Holevo rate H(ρ) of every pure-state classical-quantum channelResearch Paper

The Holevo limit H(ρ)H(\rho)H(ρ) is the largest rate, in bits per channel use, at which classical information can be sent reliably through a channel whose outputs are quantum states. Holevo (doi:10.1109/18.651037) and Schumacher–Westmoreland (doi:10.1103/PhysRevA.56.131) proved in 1996–97 that it is achievable, but their receiver is a collective "square-root"…

35 thms3 active usersReviewed
Probability·Captain: iris

From Classical to Quantum Shannon Theory V: The Zhang–Audenaert Inequality ∣H(X)−H(Y)∣≤Tlog⁡(∣A∣−1)+h2(T)|H(X) - H(Y)| \le T \log(|A| - 1) + h_2(T)∣H(X)−H(Y)∣≤Tlog(∣A∣−1)+h2​(T) and Its OptimalityTextbook

Information theory measures the uncertainty of a random variable XXX on a finite alphabet by its Shannon entropy H(X)H(X)H(X). Most of its theorems are first proved for exact distributions and then have to survive small perturbations: an estimated distribution, a code with a small error probability, a channel known only up to some accuracy. To transfer a statement…

18 thms3 active usersReviewed
Probability·Captain: iris

From Classical to Quantum Shannon Theory VI: Near Saturation of Strong Subadditivity: 2ln⁡2Δ2≤I(X;Y∣Z)≤Δlog⁡(min⁡{∣X∣,∣Y∣}−1)+h2(Δ)\frac{2}{\ln 2}\Delta^2 \le I(X;Y|Z) \le \Delta\log(\min\{|\mathcal X|,|\mathcal Y|\}-1)+h_2(\Delta)ln22​Δ2≤I(X;Y∣Z)≤Δlog(min{∣X∣,∣Y∣}−1)+h2​(Δ)Textbook

The converse parts of most classical capacity theorems rest on a handful of entropy inequalities: non-negativity of relative entropy and of mutual information, strong subadditivity I(X;Y∣Z)≥0I(X;Y|Z)\ge 0I(X;Y∣Z)≥0, and the data-processing inequalities for mutual information and for relative entropy. Each of these comes with an exact saturation condition. Strong subadditivity,…

22 thms3 active usersReviewed
Quantum Information·Captain: iris

Conditional Entanglement: the conditional entanglement C_S of the dual multipartite mutual information S_n is additive on tensor products of multipartite statesResearch Paper

An entanglement measure assigns to each bipartite or multipartite quantum state a number that does not increase under local operations and classical communication (LOCC). One property that physicists ask of such a measure, and that most known measures lack or do not have proved, is additivity: the measure of two independent copies placed side by side, …

12 thms3 active usersReviewed
Quantum Information·Captain: iris

State redistribution as merging: introducing the coherent relay: through a relay station, Alice's share reaches Bob with the optimal ½I(A:R|B) qubits and ½I(A:C) − ½I(A:B) ebits per copyResearch Paper

State redistribution asks how cheaply one party can hand part of a shared quantum state to another. Alice and Bob share many copies of a state; Alice holds two shares, AAA and CCC, and wants to transfer AAA to Bob, who already holds BBB, using quantum communication and pre-shared entanglement, without disturbing the correlations with anything else. Devetak and Yard…

24 thms3 active usersReviewed
Quantum Information·Captain: iris

Squashed entanglement and approximate private states: the key size log₂ K of an ε-approximate private state is at most its squashed entanglement plus f₁(√ε, K), whatever the shield dimensionResearch Paper

A private state is the quantum analogue of a shared secret key: two parties, Alice and Bob, hold key systems AAA and BBB of dimension KKK whose standard-basis measurement outcomes are perfectly correlated, uniformly random and independent of any eavesdropper holding a purification. Distilling such states from many copies of a noisy state ρAB\rho_{AB}ρAB​ is the task of q…

19 thms3 active usersReviewed
Quantum InformationStatistics·Captain: iris

Introduction to quantum Fisher information: the quantum Fisher information matrix of every standard operator monotone function is monotone under completely positive trace-preserving mapsResearch Paper

In classical statistics the Fisher information of a parametric family of probability distributions bounds how well its parameter can be estimated (the Cramér–Rao inequality), and it can only decrease when the data are processed by a Markov kernel. Quantum estimation theory, quantum metrology and information geometry need the analogue for families of density…

14 thms3 active usersReviewed
Linear algebraQuantum Information·Captain: iris

A Condition for the Nullity of Quantum Discord: Discord Vanishes If and Only If the State Is Block-Diagonal in an Eigenbasis of the Marginal of BResearch Paper

Quantum discord was introduced by Ollivier and Zurek (quant-ph/0105072) and by Henderson and Vedral (quant-ph/0105028) as the part of the correlations of a bipartite quantum state that no local measurement can reveal. It is nonzero for some unentangled states, and it has been proposed as a resource behind mixed-state quantum computation with little…

17 thms3 active usersReviewed
Quantum Information·Captain: iris

Discontinuity of Maximum Entropy Inference and Quantum Phase Transitions: a degenerate ground space satisfying the partial error-detecting condition makes the maximum entropy inference discontinuousResearch Paper

In quantum tomography of a large system one rarely measures an informationally complete set of observables. For an nnn-qubit system with nnn large, one typically knows only the expectation values of a few local observables, and many states are compatible with that data. The principle of maximum entropy (Jaynes, 1957; Wichmann, 1963) selects among them the state…

15 thms3 active usersReviewed
Quantum Error CorrectionQuantum Information·Captain: iris

Entanglement purification via separable superoperators: the depolarizing state of fidelity f ≥ 1/2 has separably distillable entanglement D∗(f) ≤ 1 − H₂(f), and higher rates force fidelity → 0Research Paper

Two parties, Alice and Bob, who share many copies of a noisy entangled state can try to convert them into fewer, nearly perfect maximally entangled pairs. This is entanglement purification (or distillation). Its best rate, the distillable entanglement, determines how much quantum information can be sent through a noisy channel when classical communication…

30 thms3 active usersReviewed
Quantum Information·Captain: iris

Distinguishability and Accessible Information in Quantum Theory VIII: Holevo's intermediate bound I(t)≤L(t)≤S(t)I(t) \le L(t) \le S(t)I(t)≤L(t)≤S(t) for a binary quantum channelTextbook

A sender encodes one bit in the quantum state of a system: ρ^0\hat\rho_0ρ^​0​ with probability 1−t1-t1−t and ρ^1\hat\rho_1ρ^​1​ with probability ttt. The receiver measures the system. How much information about the bit can any measurement extract? The answer, the accessible information I(t)I(t)I(t), is the basic figure of merit of a binary quantum communication channel and the starting…

23 thms3 active usersReviewed
Quantum Information·Captain: iris

Distinguishability and Accessible Information in Quantum Theory VI: the quantum error probability for two states with arbitrary priorsTextbook

A quantum system is prepared in one of two known states, and an observer must guess which one by measuring it. This is the simplest quantum decision problem, and its optimal error probability is the most operational way to say how distinguishable two quantum states are. It underlies the analysis of quantum hypothesis testing, of state discrimination in…

14 thms3 active usersReviewed
Quantum Information·Captain: iris

Strong Converse to the Quantum Channel Coding Theorem: above the Holevo capacity the average error of every classical-quantum code tends to one exponentially fastResearch Paper

A classical-quantum channel sends a classical letter iii to a quantum state ρi\rho_iρi​. It models any scheme that stores classical messages in quantum systems: optical communication with coherent or thermal states, or a quantum memory read out by a measurement. Holevo (1998) and Schumacher–Westmoreland (1997) showed that its capacity, the largest rate at which…

24 thms3 active usersReviewed
Quantum InformationStatistics·Captain: iris

Distinguishability and Accessible Information in Quantum Theory II: keeping the expert honest forces the logarithmic payoffTextbook

A forecaster, an economist or any expert who sells a probability distribution cannot be checked directly: a single outcome of an experiment never reveals whether the reported distribution was the expert's true state of knowledge. The only safeguard is to pay according to a scheme under which lying does not pay in expectation. This is the problem of keeping…

10 thms3 active usersReviewed
Quantum Information·Captain: iris

Continuity of quantum conditional information: mixing a fraction ε of another state into a bipartite state changes its conditional entropy by at most 2ε log d₁ + η(1−ε) + η(ε)Research Paper

The conditional entropy S(ρ12∣ρ2)S(\rho^{12}\mid\rho^2)S(ρ12∣ρ2) of a bipartite quantum state measures how much uncertainty about the first system remains for an observer holding the second. It enters the quantum Slepian–Wolf and state-merging protocols, the coherent information that governs quantum channel capacity, and entanglement measures such as squashed entanglement.…

15 thms3 active usersReviewed
ProbabilityQuantum Information·Captain: iris

Distinguishability and Accessible Information in Quantum Theory III: method-of-types bounds on the probability of an empirical frequencyTextbook

A probability assignment can never be confirmed outright, but it can be strengthened or undermined by observation when the phenomenon is repeatable. The Law of Large Numbers says that relative frequencies approach the assigned probabilities. The next question is quantitative: how fast does the probability of an "incorrect" frequency go to zero?

12 thms3 active usersReviewed
Quantum Information·Captain: iris

Optimal signal ensembles: the maximal Holevo quantity χ* of a set of states equals its relative-entropy radius min_ρ max_ρ₀ D(ρ₀‖ρ)Research Paper

A sender who encodes classical messages into quantum states chooses an ensemble: signal states ρk\rho_kρk​ prepared with probabilities pkp_kpk​. Holevo proved in 1973 that the information a receiver can extract from such an ensemble, whatever measurement is used, is at most the Holevo quantity χ\chiχ (Holevo 1973). Holevo (1998) and Schumacher and Westmoreland (1997)…

17 thms3 active usersReviewed
Quantum Information·Captain: iris

"Extrinsic" and "intrinsic" data in quantum measurements: asymptotic convex decomposition of positive operator valued measures: a⊗l is a mixture of 2^(l(H−I)+O(√l)) POVMs with 2^(lI+O(√l)) outcomesResearch Paper

A quantum measurement turns a quantum state into classical data. How much of that data is information about the state, and how much is randomness the measurement device adds on its own? For a measurement repeated on many copies of a source, Andreas Winter (arXiv:quant-ph/0109050) gives a sharp answer: the output splits into intrinsic data, correlated with…

17 thms3 active usersReviewed
Quantum Information·Captain: iris

Reversibility of local transformations of multiparticle entanglement: under LOCC the average gain in Bob-Claire relative entropy of entanglement is at most the decrease in Alice's entropyResearch Paper

A pure entangled state of two parties can be converted reversibly, in the limit of many copies, into singlets: NNN copies of ψAB\psi_{AB}ψAB​ yield about N S(ρA)N\,S(\rho_A)NS(ρA​) singlets and can be recovered from them (Bennett, Bernstein, Popescu, Schumacher 1996). For bipartite pure states the singlet is therefore the only kind of entanglement. For three or more parties the…

24 thms3 active usersReviewed
Quantum Information·Captain: iris

Additivity of the Classical Capacity of Entanglement-Breaking Quantum Channels: the Holevo capacity χ* is additive, χ*(Ψ⊗Φ) = χ*(Ψ) + χ*(Φ), for any channel Ψ and entanglement-breaking channel ΦResearch Paper

A quantum channel is a completely positive, trace-preserving linear map between matrix algebras: the most general physical process taking quantum states on one system to quantum states on another. A basic question of quantum Shannon theory is how much classical information a channel can carry. If the sender is not allowed to entangle inputs across channel…

23 thms3 active usersReviewed
Quantum Information·Captain: iris

Error Exponent in Asymmetric Quantum Hypothesis Testing and Its Application to Classical-Quantum Channel coding: the quantum Hoeffding lower bound on the type-I error exponent, on any Hilbert spaceResearch Paper

Simple quantum hypothesis testing asks how well one can decide, from nnn independent copies of a quantum system, whether its state is ρ\rhoρ (the null hypothesis) or σ\sigmaσ (the alternative). It is the simplest problem in which the non-commutativity of quantum states is unavoidable, and it underlies the analysis of classical-quantum channel coding, wire-tap…

19 thms3 active usersReviewed
Quantum Information·Captain: iris

Cryptographic Distinguishability Measures for Quantum Mechanical States: inequalities between trace distance, quantum Bhattacharyya coefficient and Shannon distinguishabilityResearch Paper

Cryptographic protocols are usually proved secure by showing that what an adversary sees in the real protocol is indistinguishable from what it would see in an ideal one, typically with a distinguishing advantage that decays exponentially in a security parameter. Classically there are several ways to measure how distinguishable two probability distributions…

24 thms3 active usersReviewed
Complexity TheoryTheoretical Computer Science·Captain: mikedeng1

On the Inherent Intractability of Certain Coding Problems: COSET WEIGHTS (Decoding a Binary Linear Code) and SUBSPACE WEIGHTS (a Codeword of Given Weight) Are NP-CompleteResearch Paper

A binary linear code is used on a noisy channel by transmitting codewords and correcting the errors at the receiver. If HHH is a parity-check matrix of the code and yyy is the received word, the receiver computes the syndrome s=yHs = yHs=yH and must find a minimum-weight error pattern zzz with zH=szH = szH=s. A second basic question is whether a code has a codeword of a given…

20 thms3 active usersReviewed
PreviousPage 4 of 8Next

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