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
🏆Completed
Complexity TheorycryptographyTheoretical Computer Science·Captain: Shuze Chen

Information Loss Is All You Need: TC^0 Pseudorandomness from Worst-Case LatticesResearch Paper

Learning with errors (LWE) is the standard source of post-quantum hardness: given many noisy inner products As+e mod qA s + e \bmod qAs+emodq of a secret sss, distinguish them from uniform. Regev showed in 2005 that this is as hard, for quantum algorithms, as worst-case approximate lattice problems (Reg05). Removing the random error makes the samples deterministic: learning…

138 thms9 active usersReviewed
🏆Completed
Theoretical Computer Science·Captain: mikedeng1

Quantum circuit compilation with constant overheadResearch Paper

Quantum algorithms are usually written as circuits of arbitrary one- and two-qubit gates. A fault-tolerant machine executes only a finite instruction set, and a standard choice is G={H,T,CNOT}\mathcal G=\{H,T,\mathrm{CNOT}\}G={H,T,CNOT}. An arbitrary rotation cannot be written exactly over a finite gate set, so every compiler approximates. Ross and Selinger (RS16) approximate a…

31 thms8 active usersReviewed
🏆Completed
Computational Complexity·Captain: iris

Quantum Algorithms for OPI Variants Beyond Locality and Classical DecodabilityResearch Paper

The code intersection problem asks for a codeword of a linear code C⊆FqmC\subseteq\mathbb F_q^mC⊆Fqm​ that lies in a prescribed set AAA. It is NP-hard even for q=3q=3q=3 and AAA a Cartesian product of per-coordinate sets (arXiv:2610.00502, §1). Optimal polynomial intersection (OPI), which asks for a low-degree polynomial whose values lie in prescribed sets at all evaluation…

80 thms8 active usersReviewed
🏆Completed
Linear algebra·Captain: Mrnaiq

The Theory of Quantum Information I: Unital Qubit Channels Are Mixed UnitaryTextbook

A noisy quantum operation can sometimes be implemented by drawing a classical random variable and applying a reversible gate selected by its outcome. Such an implementation separates the randomness from the quantum operation: each selected gate is unitary, while the average transformation can reduce the information carried by a state. Determining which…

12 thms7 active usersReviewed
🏆Completed
Theoretical Computer Science·Captain: iris

When are bosonic Gaussian states classical to learn?Research Paper

Bosonic Gaussian states describe laser light, thermal radiation, squeezed light and the modes of many continuous-variable quantum devices. They sit on the boundary between quantum and classical physics: a Gaussian state is fixed by a mean vector and a covariance matrix, exactly like a classical Gaussian random vector, yet some Gaussian states are entangled…

111 thms7 active usersReviewed
🏆Completed
Functional Analysis·Captain: iris

From Classical to Quantum Shannon Theory IX: Relative Entropy Decrease Bounds the Averaged Fidelity of Rotated Petz RecoveryTextbook

The monotonicity of quantum relative entropy, D(ρ∥σ)≥D(N(ρ)∥N(σ))D(\rho\|\sigma)\ge D(\mathcal N(\rho)\|\mathcal N(\sigma))D(ρ∥σ)≥D(N(ρ)∥N(σ)) for every quantum channel N\mathcal NN, is the inequality from which the converse parts of the coding theorems of quantum Shannon theory are derived: strong subadditivity, concavity of conditional entropy, joint convexity of relative entropy and the Holevo…

23 thms7 active usersReviewed
🏆Completed
Captain: Goku

Quantum Computing: Lecture Notes 5: One run of Shor's period-finding circuit reveals the period with probability Omega(1/log log N)Textbook

This mission develops Chapter 5 of Quantum Computing: Lecture Notes by Ronald de Wolf. The chapter's selected results describe the mathematical guarantees below.

10 thms7 active usersReviewed
🏆Completed
Mathematical PhysicsProbability·Captain: mikedeng1

Fast mixing of the SYK model at high temperaturesResearch Paper

A Gibbs state describes thermal equilibrium, but specifying its matrix does not provide an efficient procedure for preparing it. For quantum algorithms, the useful guarantee is convergence from every initial state in a distance that controls arbitrary measurements. Agreement of a few local observables is insufficient for this purpose. The Sachdev–Ye–Kitaev…

33 thms6 active usersReviewed
🏆Completed
Complexity Theory·Captain: mikedeng1

Near-optimal quantum query lower bounds on bipartiteness and expansion testing in the bounded-degree graph modelResearch Paper

A property tester inspects a small part of an input and decides whether the input has a specified property or is far from every input having that property. For a large graph, the number of inspected adjacency entries can matter more than the time needed for computations between inspections. A quantum query permits a coherent superposition of such…

47 thms6 active usersReviewed
🏆Completed
Number Theory·Captain: iris

Towards Large-Scale Quantum Computation II: for N=N1N2N=N_1N_2N=N1​N2​ with distinct primes, every useful outcome j=⌊c22L/r⌋j=\lfloor c2^{2L}/r\rfloorj=⌊c22L/r⌋ or ⌈c22L/r⌉\lceil c2^{2L}/r\rceil⌈c22L/r⌉ has c/rc/rc/r as a convergent of j/22Lj/2^{2L}j/22LTextbook

Shor's algorithm factors an integer NNN in time polynomial in its binary length, and in doing so threatens the RSA protocol, whose security rests on factoring being hard for classical computers (Shor 1994/1997). Every hardware proposal for running it, including the linear nearest-neighbour architectures studied in A. G. Fowler's thesis Towards Large-Scale…

9 thms6 active usersReviewed
🏆Completed
Information Theory·Captain: iris

From Classical to Quantum Shannon Theory XXIV: A 50% Erasure Channel Turns Half the Private Information into Coherent InformationTextbook

The quantum capacity of a channel is the largest rate at which it can transmit quantum information reliably. Most capacity formulas of information theory are additive: two channels used side by side are worth the sum of their individual values. Quantum capacity is not. Smith and Yard found two channels, each with zero quantum capacity, whose tensor product…

21 thms6 active usersReviewed
🏆Completed
Linear algebra·Captain: iris

From Classical to Quantum Shannon Theory IV: Gentle Measurement for Ensembles: Σ pX(x)∥ρx − √Λρx√Λ∥₁ ≤ 2√εTextbook

Measuring a quantum system generally changes it. A qubit prepared in ∣0⟩|0\rangle∣0⟩ and measured along the XXX axis is left in ∣+⟩|+\rangle∣+⟩ or ∣−⟩|-\rangle∣−⟩, each with probability one half, and the original state is lost. The same qubit measured along the ZZZ axis returns its outcome with certainty and is left untouched. The gentle measurement lemma turns this intuition…

19 thms6 active usersReviewed
🏆Completed
Linear algebra·Captain: iris

From Classical to Quantum Shannon Theory II: All Purifications of a Density Operator Are Related by an Isometry on the Purifying SystemTextbook

Quantum Shannon theory repeatedly replaces a mixed state by a pure state on a larger system. A noisy state ρA\rho_AρA​ of a system AAA can always be viewed as the reduced state of a pure state ∣ψ⟩RA|\psi\rangle_{RA}∣ψ⟩RA​ in which AAA is entangled with a reference system RRR that nobody holds. This is the purification viewpoint of Chapter 5 of M. M. Wilde, From Classical to…

10 thms6 active usersReviewed
🏆Completed
Captain: Gohan

Quantum linear Boltzmann equationResearch Paper

We review the quantum version of the linear Boltzmann equation, which describes in a non-perturbative fashion, by means of scattering theory, how the quantum motion of a single test particle is affected by collisions with an ideal background gas. A heuristic derivation of this Lindblad master equation is presented, based on the requirement of…

30 thms6 active usersReviewed
🏆Completed
Information Theory·Captain: mikedeng1

A Simple Proof of the Strong Subadditivity Inequality: Strong Subadditivity of the von Neumann Entropy via Monotonicity of the Relative Entropy under Partial TraceResearch Paper

Strong subadditivity of the von Neumann entropy is the basic inequality of quantum information theory: most entropy inequalities used in quantum Shannon theory, the data-processing inequality for quantum mutual information, and many capacity converses rest on it (Nielsen–Chuang, ch. 11). This mission formalizes the route to it presented by M. A. Nielsen and…

15 thms6 active usersReviewed
🏆Completed
ProbabilityTheoretical Computer Science·Captain: mikedeng1

Simulating quantum computers with probabilistic methods: a circuit on a computationally tractable state is classically simulable by sampling when U†OU is sparseResearch Paper

A quantum circuit may create a state whose full list of amplitudes is far too large for a classical computer to store. That fact alone does not show that every observable feature of its output is hard to estimate. In Simulating quantum computers with probabilistic methods, Van den Nest asks when classical sampling can reproduce the accuracy of a quantum…

12 thms6 active usersReviewed
🏆Completed
Theoretical Computer Science·Captain: mikedeng1

Asymptotically Optimal Approximation of Single Qubit Unitaries by Clifford and T Circuits Using a Constant Number of Ancillary Qubits: O(log(1/ε)) Gates Approximate Every Single-Qubit UnitaryResearch Paper

A fault-tolerant quantum computer executes only a discrete set of gates. The standard choice is the Clifford and T library: the Hadamard gate HHH, the phase gate SSS, CNOT, and the gate T=diag(1,eiπ/4)T = \mathrm{diag}(1, e^{i\pi/4})T=diag(1,eiπ/4), which together are universal and are well suited to error-corrected implementation. Every other gate, in particular every single-qubit rotation…

18 thms6 active usersReviewed
🏆Completed
Theoretical Computer Science·Captain: mikedeng1

A Meet-in-the-Middle Algorithm for Fast Synthesis of Depth-Optimal Quantum Circuits: Meet-in-the-Middle Search Returns a Minimal-Depth Circuit, Generating Only Circuits of Half the DepthResearch Paper

A quantum algorithm is run as a quantum circuit: a sequence of elementary gates drawn from a fixed instruction set, such as the Hadamard, phase, controlled-NOT and TTT gates. On fault-tolerant hardware every layer of gates costs time and error-correction overhead, so the depth of a circuit, its number of layers, is a primary cost measure. Compilers therefore…

28 thms6 active users
🏆Completed
Captain: Goku

General paradigm for distilling classical key from quantum statesResearch Paper

We develop a formalism for distilling a classical key from a quantum state in a systematic way, expanding on our previous work on secure key from bound entanglement [K. Horodecki et. al., Phys. Rev. Lett. 94 (2005)]. More detailed proofs, discussion and examples are provided of the main results. Namely, we demonstrate that all quantum cryptographic…

48 thms6 active usersReviewed
🏆Completed
Captain: Goku

Energy-constrained two-way capacities of pure-loss and quantum-limited amplifier channelsResearch Paper

We determine the two-way quantum, entanglement-distribution, private, and secret-key capacities of the pure-loss bosonic channel under an unconditional mean transmitted-photon-number constraint. For transmissivity ηηη and mean photon number NNN, all four capacities coincide and are given by g(N)−g((1−η)N)g(N)-g((1-η)N)g(N)−g((1−η)N), where ggg is the entropy of a thermal mode. This resolves…

18 thms6 active usersReviewed
🏆Completed
Captain: Goku

Quantifying CoherenceResearch Paper

Quantifying Coherence establishes the selected mathematical guarantees below. The mission turns those original paper results into precise Lean proof targets.

35 thms6 active usersReviewed
🏆Completed
Optimization·Captain: Goku

Quantum algorithms for optimizers 9: QAOA with enough layers reaches a maximum eigenstate of H_FTextbook

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

15 thms6 active usersReviewed
🏆Completed
Machine Learning·Captain: Goku

Quantum Algorithms and Learning Theory — Part II 6: Shadow tomography with poly(log m, log d, 1/ε, log(1/δ)) copiesTextbook

This mission develops Chapter 6 of Quantum Algorithms and Learning Theory — Part II by Srinivasan Arunachalam. The chapter's selected results describe the mathematical guarantees below.

13 thms6 active usersReviewed
🏆Completed
Computational Complexity·Captain: mikedeng1

Random-Oracle Unitary Synthesis is ImpossibleResearch Paper

Unitary synthesis asks how a quantum circuit can implement a prescribed transformation when it may consult a classical function in quantum superposition. The choice of function can carry substantial information about the requested transformation. The question changes when that function must be sampled uniformly: how many queries are needed before the…

26 thms5 active usersReviewed
🏆Completed
Statistics·Captain: iris

Structure of sufficient quantum coarse-grainings: both outputs of a sufficient coarse-graining factorize over the central blocks of a multiplicative-domain subalgebra, with a common commutant factorResearch Paper

In classical statistics a statistic is sufficient for a family of distributions when nothing is lost by passing to it: the original data can be regenerated from the statistic by a Markov kernel that does not depend on the unknown parameter. The quantum analogue concerns a coarse-graining TTT, a trace-preserving map sending density matrices on one system to…

33 thms5 active usersReviewed
PreviousPage 1 of 17Next

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