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 InformationTheoretical Computer Science·Captain: iris

Dimension-Free Polylogarithmic Quantum Shadow TomographyResearch Paper

Measuring a quantum state disturbs it, so copies are the resource that any learning task consumes. Shadow tomography, introduced by Aaronson (STOC 2018), asks how many copies of an unknown state suffice to predict the expectation values of many known measurements, without reconstructing the state. The question matters in quantum learning theory and in the…

38 thms4 active usersReviewed
Harmonic AnalysisProbabilityTheoretical Computer Science·Captain: iris

A Nonadaptive Sparse Fourier Transform in Every DimensionResearch Paper

A sparse Fourier transform recovers the few large Fourier coefficients of a signal from far fewer samples than the signal's length, and in time polynomial in the number of coefficients rather than in the length. It is used whenever a spectrum is dominated by a small number of frequencies and reading the whole signal is expensive. The standard accuracy…

24 thms4 active usersReviewed
CombinatoricsConvex OptimizationProbability+1·Captain: iris

Optimal e(γ+o(1))ne^{(\gamma+o(1))n}e(γ+o(1))n-Approximation of the Permanent of Positive Semidefinite MatricesResearch Paper

The permanent of a matrix A∈Cn×nA\in\mathbb C^{n\times n}A∈Cn×n is per(A)=∑σ∈Sn∏i=1nAi,σ(i)\mathrm{per}(A)=\sum_{\sigma\in S_n}\prod_{i=1}^n A_{i,\sigma(i)}per(A)=∑σ∈Sn​​∏i=1n​Ai,σ(i)​. Computing it exactly is #P-hard even on 0/1 matrices (Valiant 1979). For nonnegative entries a randomized approximation scheme exists (Jerrum, Sinclair, Vigoda 2004). For a Hermitian positive semidefinite matrix the entries may have…

37 thms4 active usersReviewed
Quantum Information·Captain: iris

Locking of accessible information and implications for the security of quantum cryptography: a key with accessible information at most e^(-(n-2)/8) whose last bit is revealed given the othersResearch Paper

Quantum key distribution produces a classical key SSS shared by two parties, while an adversary may hold a quantum system EEE correlated with it. For a long time, security of such a key was measured by the accessible information Iacc(S;E)I_{\mathrm{acc}}(S;E)Iacc​(S;E): the largest mutual information between SSS and the outcome of any measurement the adversary can perform on EEE. A…

24 thms4 active usersReviewed
Quantum Information·Captain: iris

The Uniqueness Theorem for Entanglement Measures: on pure states, a functional equals the reduced von Neumann entropy iff it is normalized, LQCC-monotone, asymptotically continuous and additiveResearch Paper

Entanglement is the resource behind teleportation, dense coding and much of quantum cryptography, and quantifying it is a basic task of quantum information theory. Many entanglement measures have been proposed, and for mixed states they genuinely disagree. For pure states of two parties they all reduce to one quantity, the entropy of the reduced state.…

46 thms4 active usersReviewed
Quantum Information·Captain: iris

From Classical to Quantum Shannon Theory XXII: The Quantum Capacity of the Erasure Channel Is (1−2ε)log⁡dA(1 - 2\varepsilon) \log d_A(1−2ε)logdA​Textbook

The quantum capacity of a channel is the largest rate, in qubits per channel use, at which quantum information can be sent through it with vanishing error. Unlike the classical capacity of a classical channel, it is not given by a single-letter formula in general: the quantum capacity theorem (Lloyd, Shor, Devetak) identifies it with the regularized coherent…

28 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
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
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
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
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
Combinatorics·Captain: mikedeng1

Massively Parallel Algorithms for Huffman CodingResearch Paper

Huffman coding assigns binary codewords to the characters of a text so that no codeword is a prefix of another and the encoded text is as short as possible. Huffman's greedy algorithm (Huffman 1952) solves it in linear time once the character frequencies are sorted. It is a basic step of practical compression.

27 thms3 active usersReviewed
Complexity Theory·Captain: mikedeng1

Efficient Randomized Communication Without Large Monochromatic RectanglesResearch Paper

In Yao's two-party model, Alice holds x∈{0,1}nx\in\{0,1\}^nx∈{0,1}n, Bob holds y∈{0,1}ny\in\{0,1\}^ny∈{0,1}n, and they exchange bits to compute a Boolean function F(x,y)F(x,y)F(x,y). The randomized communication complexity R(F)R(F)R(F) is the least worst-case number of bits of a public-coin protocol that errs with probability at most 1/31/31/3 on every input. Two questions about total functions motivate this…

22 thms3 active usersReviewed
CombinatoricsTheoretical Computer Science·Captain: Shuze Chen

Dynamic LZ77: No Space for ImprovementResearch Paper

Lempel–Ziv 77 (LZ77) is the parsing behind most dictionary compressors and the reference measure of repetitiveness in compressed string algorithms. Its size zzz can be exponentially smaller than the length nnn of a highly repetitive text, which is why compressed indexes aim for space proportional to zzz rather than nnn.

22 thms3 active usersReviewed
ProbabilityQuantum InformationTheoretical Computer Science·Captain: iris

Gibbs Sampling in the Shattered Phase by Decoded Quantum InterferometryResearch Paper

Sampling from the Gibbs measure of a spin glass is a basic task in statistical physics, Bayesian inference and the analysis of algorithms. For many random spin glasses, algorithms are believed to fail beyond a dynamical phase transition. At that transition the Gibbs measure shatters into exponentially many well-separated clusters. Results for dense models…

26 thms3 active usersReviewed
CombinatoricsComplexity TheoryProbability+1·Captain: Shuze Chen

Nearly Tight Cell-Probe Lower Bounds for Querying on Tree via Talagrand InequalityResearch Paper

Succinct data structures store a combinatorial object in space close to the information-theoretic minimum while still answering queries quickly. Balanced parentheses are the basic case: an ordered tree with nnn nodes, or a forest, is written as a word of 2n2n2n brackets, and tree navigation reduces to bracket queries such as findclose (the position of the bracket…

18 thms3 active usersReviewed
AlgebracryptographyTheoretical Computer Science·Captain: Shuze Chen

Reed–Solomon Codes Beyond Johnson: Efficient Decoding and Smaller Cryptographic ProofsResearch Paper

Reed–Solomon codes are the codes behind most deployed proof systems that use the FRI protocol and its successors (STARK provers such as ProveKit, ZisK and LambdaVM). The soundness of those protocols reduces to two combinatorial facts about the code: how many codewords can lie close to a received word (list decoding), and whether closeness of a random linear…

25 thms3 active usersReviewed
PreviousPage 2 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