Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

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

Quantum Information

1,403 missions · 401 completed

The study of information encoded in the states of quantum systems, where the qubit, superposition, and entanglement replace the classical bit and measurement is inherently probabilistic. Governed by the constraints of quantum mechanics, it underpins quantum computing and cryptography and the theory of optimal quantum measurements.

Missions

Open1002Completed401All1403
Information TheoryMathematical Physics·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
Information TheoryMathematical Physics·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
🏆Completed
Mathematical Physics·Captain: mikedeng1

Preparation of Entangled States by Quantum Markov Processes: Every n-Qubit Pure State Is the Unique and Attractive Stationary State of a Dissipative Process with Relaxation Time 1/min_k g_kResearch Paper

Quantum technologies usually prepare a desired state by isolating a system and driving it with carefully timed unitary operations; coupling to an environment is treated as noise. Dissipative state preparation reverses this view: one engineers the system–environment coupling so that the open-system dynamics itself drives every initial state into a prescribed…

12 thms4 active usersReviewed
Graph TheoryTheoretical Computer Science·Captain: mikedeng1

Beyond product state approximations for a quantum analogue of Max Cut: Tensor Products of One- and Two-Qubit States Reach 0.55 of the Maximum Energy on Every Weighted GraphResearch Paper

Classical Max Cut asks for a partition of the vertices of a weighted graph that maximises the total weight of edges crossing it. Its best-known approximation algorithm, due to Goemans and Williamson, rounds a semidefinite relaxation and guarantees ratio 0.8780.8780.878. Quantum Max Cut is the analogous problem for a family of local Hamiltonians: each edge contributes…

12 thms4 active usersReviewed
🏆Completed
ProbabilityTheoretical Computer Science·Captain: mikedeng1

Simulating Large Quantum Circuits on a Small Quantum Computer: A (K, d)-Clustered Circuit Is Simulated to Precision ε with Probability 2/3 by O(2^{4K} r/ε²) Runs of d-Qubit PiecesResearch Paper

Near-term quantum processors have few qubits, while the circuits one would like to run (variational eigensolvers, sampling benchmarks, error-mitigated algorithms) often need more qubits than any single device has. Peng, Harrow, Ozols and Wu (arXiv:1904.00102, Phys. Rev. Lett. 125, 150504, 2020) show that a circuit which is only loosely connected (a few…

16 thms4 active usersReviewed
🏆Completed
Captain: Goku

Entanglement-of-formation potentials for feedback-assisted classical communication and randomness distillationResearch Paper

We develop entanglement-of-formation potentials for feedback-assisted classical communication and one-way randomness distillation. For a finite-dimensional quantum channel without initial shared entanglement, an exact amortization theorem bounds the increase of message information plus entanglement remaining across the communicating laboratories. This…

35 thms4 active usersReviewed
🏆Completed
Captain: Goku

Formal proofs in real algebraic geometry: from ordered fields to quantifier eliminationResearch Paper

This paper describes a formalization of discrete real closed fields in the Coq proof assistant. This abstract structure captures for instance the theory of real algebraic numbers, a decidable subset of real numbers with good algorithmic properties. The theory of real algebraic numbers and more generally of semi-algebraic varieties is at the core of a number…

30 thms4 active usersReviewed
🏆Completed
Linear algebraTheoretical Computer Science·Captain: mikedeng1

Quantum Singular Value Transformation and Beyond: Exponential Improvements for Quantum Matrix Arithmetics: Singular Value Transformation by Real Polynomials via Alternating Phase ModulationResearch Paper

Many quantum algorithms act on a matrix AAA that is not itself unitary: a Hamiltonian to be simulated, a linear system to be inverted, a projector to be amplified. The standard way to hand such a matrix to a quantum computer is to embed it as a block of a unitary UUU, so that A=Π~UΠA=\widetilde\Pi U\PiA=ΠUΠ for two orthogonal projectors Π,Π~\Pi,\widetilde\PiΠ,Π. The question is…

15 thms4 active usersReviewed
🏆Completed
Linear algebraOptimizationTheoretical Computer Science·Captain: mikedeng1

Optimization by Decoded Quantum Interferometry 2: With an Imperfect Decoder and Uniform v, 𝔼_v⟨f⟩ ≥ wᵀ[A − 2ε(m+1)]w / Σ_k w_k²(1 − ε_k) for max-XORSATResearch Paper

A max-XORSAT instance asks for a binary assignment that satisfies as many parity constraints as possible. A matrix specifies the parity check in each constraint, while a second binary vector specifies the desired parity. The objective can be written as the number of satisfied constraints minus the number violated, so an assignment with a high objective…

10 thms4 active usersReviewed
🏆Completed
ProbabilityStatistics·Captain: mikedeng1

Direct Fidelity Estimation from Few Pauli Measurements 1: ⌈1/(ε²δ)⌉ Importance-Sampled Pauli Measurements Estimate tr(ρσ) Within 2ε With Probability ≥ 1 − 2δResearch Paper

Experiments that prepare many-body entangled states (GHZ, W, stabilizer, cluster and matrix product states) need a way to check that the device produced the intended state. Full quantum state tomography answers the question but its cost grows with the dimension d=2nd = 2^nd=2n of an nnn-qubit system: a reconstruction needs on the order of d2d^2d2 measurement settings.…

15 thms4 active usersReviewed
🏆Completed
Complexity Theory·Captain: mikedeng1

Fixed-Point Quantum Search with an Optimal Number of Queries: The Phases of Eq. (11) Give Success Probability 1 − δ²T_L(T_{1/L}(1/δ)√(1−λ))²Research Paper

Quantum search starts with a state that has some overlap with a desired target. Standard Grover iterations can increase that overlap quickly, but their success probability oscillates with the number of iterations. If the initial overlap is unknown, a sequence chosen for one value can pass the target and perform poorly at another. Earlier fixed-point…

10 thms4 active usersReviewed
🏆Completed
Linear algebraTheoretical Computer Science·Captain: mikedeng1

Learning Stabilizer States by Bell Sampling: Algorithm 1 Identifies an n-Qubit Stabilizer State from 5n+2 Copies, Failing with Probability at Most 2⁻ⁿResearch Paper

Determining an unknown quantum state of nnn qubits to good accuracy requires, in general, a number of copies of the state exponential in nnn; this follows from Holevo's theorem. One way around this barrier is to restrict the class of states. Stabilizer states are the natural candidate: they are the states produced from ∣0n⟩|0^n\rangle∣0n⟩ by Clifford circuits, they…

14 thms4 active usersReviewed
Quantum Error Correction·Captain: LG

Quantum Threshold Theorem: Polylogarithmic-Overhead Fault-Tolerant Simulation Below a Constant Fault RateTextbook

A quantum computer cannot perform gate operations perfectly, so a small constant error per operation is unavoidable. A priori this could mean that a noisy quantum computer can apply only a bounded number of gates before the computation is destroyed by noise, which would rule out long quantum computations in practice. The threshold theorem (or quantum…

21 thms4 active usersReviewed
🏆Completed
Optimization·Captain: Goku

Quantum algorithms for optimizers 4: Quantum minimum finding (Dürr–Høyer), with explicit bit width, interruption and gate modelTextbook

This mission develops Chapter 4 of Quantum algorithms for optimizers by Giacomo Nannicini. The chapter's selected results describe the mathematical guarantees below.

18 thms4 active usersReviewed
🏆Completed
Mathematical PhysicsQuantum Error CorrectionQuantum Gravity·Captain: LG

Harlow TASI 2017: Entanglement Wedge Reconstruction, Quantum RT and JLMS are EquivalentResearch Paper

In the AdS/CFT correspondence a quantum theory of gravity in an asymptotically anti-de Sitter spacetime is equivalent to a conformal field theory on its boundary. A central question is how local bulk physics is encoded in the boundary theory, and in particular which bulk region is described by a given boundary subregion RRR. Harlow's TASI 2017 lectures (arXiv:…

23 thms4 active usersReviewed
🏆Completed
Linear algebraMathematical Physics·Captain: mikedeng1

Quantum Algorithm for Simulating Real Time Evolution of Lattice Hamiltonians 2: Strictly Local Lieb–Robinson Bound ‖[A_X(t),B_Y]‖ ≤ 2‖A‖‖B‖|X|(2ζ₀|t|)^ℓ/ℓ! with ℓ = ⌊dist(X,Y)⌋Research Paper

Simulating the time evolution e−iHte^{-iHt}e−iHt of a many-body Hamiltonian is one of the main proposed uses of quantum computers. For a Hamiltonian H=∑XhXH = \sum_X h_XH=∑X​hX​ whose terms act on small, nearby groups of sites of a lattice, Haah, Hastings, Kothari and Low give a quantum algorithm whose gate count is nearly linear in the space-time volume ntn tnt, and show that this is…

10 thms4 active usersReviewed
🏆Completed
Harmonic AnalysisNumerical Analysis·Captain: mikedeng1

Quantum Algorithm for Systems of Linear Equations with Exponentially Improved Dependence on Precision II: A Discretized Gaussian Fourier Double Sum Is ε-Close to 1/x on [−1, −1/κ] ∪ [1/κ, 1]Research Paper

A quantum algorithm for a system of linear equations must turn operations it can implement into an approximation of the inverse of the system matrix. For a Hermitian matrix, time evolution e−iAte^{-iAt}e−iAt is such an operation. Childs, Kothari and Somma use a Fourier expansion of the scalar reciprocal 1/x1/x1/x to express an approximation to A−1A^{-1}A−1 as a finite linear…

8 thms4 active usersReviewed
🏆Completed
Mathematical PhysicsProbability·Captain: LG

Hardy 2001 I: Five Reasonable Axioms — Degrees of Freedom K = N^rResearch Paper

In the usual textbook presentation, quantum theory starts from postulates that have no obvious operational meaning: states are density operators on a complex Hilbert space, measurements are positive operators, and probabilities are given by the trace formula p=tr(A^ρ^)p=\mathrm{tr}(\hat A\hat\rho)p=tr(A^ρ^​). In Quantum Theory From Five Reasonable Axioms (Hardy 2001), Lucien…

25 thms4 active usersReviewed
🏆Completed
Probability·Captain: marwahaha

Threshold parallel repetition for finite-dimensional entangled gamesOpen Problem

Parallel repetition is useful for amplifying errors in nonlocal games, but a joint entangled strategy can correlate outcomes across repetitions. Independence of the sampled questions does not imply independence of wins. The pinned manuscript supplies the research context.

34 thms4 active usersReviewed
🏆Completed
Linear algebra·Captain: marwahaha

Entanglement with zero distillable secret key in local dimension tenOpen Problem

Positive partial transpose imposes strong constraints on quantum maps, but composition may retain entanglement. Explicit finite-dimensional examples make that distinction a precise algebraic target. The pinned manuscript supplies the research context.

18 thms4 active usersReviewed
🏆Completed
Machine LearningTheoretical Computer Science·Captain: mikedeng1

Shadow Tomography of Quantum States 1: Polylogarithmically Many Copies Suffice to Estimate Every Acceptance Probability to Within εResearch Paper

Learning an unknown quantum state is expensive. Full quantum state tomography of a DDD-dimensional mixed state ρ\rhoρ to accuracy ε\varepsilonε in trace distance needs on the order of D2/ε2D^2/\varepsilon^2D2/ε2 copies of ρ\rhoρ (O'Donnell–Wright 2016; Haah et al. 2017), and this is optimal. For a system of nnn qubits, D=2nD = 2^nD=2n, so full tomography is out of reach beyond a few…

17 thms4 active usersReviewed
🏆Completed
Mathematical Physics·Captain: LG

Albers–Kiefer–Reginatto 2008: Measurement Analysis and Quantum GravityResearch Paper

Whether the gravitational field must be quantized is a long-standing foundational question. A well-known family of arguments tries to settle it by consistency alone: if a classical field were coupled to a quantum system, some basic principle — momentum conservation, the uncertainty relations, or the impossibility of superluminal signalling — would allegedly…

8 thms4 active usersReviewed
Theoretical Computer Science·Captain: Goku

Stabilizer Rank of Magic StatesOpen Problem

Quantum circuits built from Clifford gates alone are classically simulable in polynomial time. Universality is recovered by adding copies of a magic state, and the fastest known classical simulators of such circuits work by writing the magic-state input as a short linear combination of stabilizer states. The length of the shortest such combination -- the sta…

5 thms4 active usersReviewed
🏆Completed
Theoretical Computer Science·Captain: Goku

The Aaronson-Ambainis ConjectureOpen Problem

Quantum query algorithms are known to beat classical ones on problems with algebraic structure -- period finding, hidden subgroups, forrelation. No such speedup is known for a problem with no structure at all. Aaronson and Ambainis proposed making that observation into a theorem, and reduced it to a question with no quantum content: a statement about…

14 thms4 active usersReviewed
🏆Completed
Linear algebra·Captain: Mrnaiq

The Theory of Quantum Information II: Extreme Quantum Channels and the Choi–Kraus CriterionTextbook

A quantum device can be represented by a rule that takes an input matrix to an output matrix. Noise introduces randomness into that rule. Convex combinations describe a device that first makes a classical random choice and then applies the selected operation. An extreme quantum channel is one that cannot be obtained as a nontrivial mixture of two different…

7 thms3 active usersReviewed
PreviousPage 8 of 57Next

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