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
Captain: Goku

Continuity bounds on the quantum relative entropyResearch Paper

The quantum relative entropy is frequently used as a distance, or distinguishability measure between two quantum states. In this paper we study the relation between this measure and a number of other measures used for that purpose, including the trace norm distance. More precisely, we derive lower and upper bounds on the relative entropy in terms of various…

51 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
Computational ComplexityGraph TheoryTheoretical Computer Science·Captain: mikedeng1

The Complexity of Space–Reset Tradeoffs in Online Quantum ComputationResearch Paper

Quantum devices that process a stream of inputs — a quantum memory interleaved with arriving qubits, a sequential state generator, a device simulating a correlated noise process — keep a bounded private memory between time steps and remove information by irreversible operations such as qubit RESET. Both resources are limited on hardware: the number of…

42 thms7 active usersReviewed
Complexity TheoryTheoretical Computer Science·Captain: iris

Optimal and Verifiable Quantum Advantages in Communication ComplexityResearch Paper

Communication complexity measures how many bits (or qubits) two parties, Alice and Bob, must exchange to solve a joint task when each sees only part of the input. It is one of the few settings where quantum advantages can be proved unconditionally, and such separations now underpin experimental demonstrations of quantum advantage in space (Kretschmer et al.…

39 thms7 active usersReviewed
Representation Theory·Captain: mikedeng1

Random dimension reduction and learning symmetric properties of quantum statesResearch Paper

A quantum state is a positive complex matrix of trace one. Its matrix entries depend on a basis, while quantities such as its eigenvalues do not. When several unknown states share a physical register, their relative eigenbases also contain information. Applying the same change of coordinates to every state preserves this relationship. Quantum learning tasks…

35 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
Quantum Error Correction·Captain: iris

General conditions for approximate quantum error correction and near-optimal recovery channels: for complementary channels, max_R F(RN, M) = max_R' F(N̂, R'M̂) in worst-case entanglement fidelityResearch Paper

Quantum error correction protects quantum information against noise by encoding it into a larger system and undoing the damage with a recovery channel. The classical criterion for exact correctability is the Knill–Laflamme condition (Knill, Laflamme 1997). Realistic codes, however, rarely correct errors perfectly, and many useful schemes (approximate codes,…

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
Captain: mikedeng1

Near-optimal incoherent tomography of low-rank quantum channelsResearch Paper

A quantum channel describes how an input quantum system changes when it passes through a physical device. Learning that channel gives a classical description that can be used to compare devices, characterize noise, and predict their response to new inputs. The choice of experimental resources matters: a learner with quantum memory can combine several…

23 thms6 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
Machine Learning·Captain: mikedeng1

Optimal Quantum-Classical Separations for Exact LearningResearch Paper

Exact learning with membership queries asks how many values of an unknown Boolean function must be inspected to identify that function completely, given a known finite list of possibilities. It models information acquisition in black-box identification: computation between queries is unrestricted, while access to the target is charged. Classical and quantum…

30 thms6 active usersReviewed
AnalysisHarmonic AnalysisMathematical Physics·Captain: iris

Sensing frequencies at the discrete Grover-Heisenberg limit using a single qubitResearch Paper

Quantum sensing uses a controlled quantum system to detect weak fields. In AC magnetometry a single qubit, such as a nitrogen-vacancy centre in diamond, feels a field Bcos⁡(ωt+ϕ)B\cos(\omega t+\phi)Bcos(ωt+ϕ) along its ZZZ axis. A conventional protocol needs evolution time Θ(1/B)\Theta(1/B)Θ(1/B) per candidate frequency, so scanning NNN candidates costs Θ(N/B)\Theta(N/B)Θ(N/B). Allen et al. ([AMC+25])…

23 thms6 active usersReviewed
Convex OptimizationOptimization·Captain: iris

Solving Sparse SDPs in Sublinear Time: A Classical Algorithm Inspired by the Quantum OR LemmaResearch Paper

Semidefinite programs underlie approximation algorithms such as Goemans–Williamson, the sum-of-squares hierarchy, and basic tasks in quantum information. They are also the main example of a claimed large quantum speedup for a continuous optimization problem. For sparse SDPs with n×nn\times nn×n matrices and mmm constraints, the best known classical solver had…

38 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
Functional AnalysisLinear algebra·Captain: iris

From Classical to Quantum Shannon Theory III: The Diamond Norm Is Attained on a Pure State with a Reference of the Input DimensionTextbook

Quantum Shannon theory proves coding theorems by allowing a small error and showing that it vanishes for long blocks. The error has to be measured, and the standard measure for states is the trace distance ∥ρ−σ∥1\|\rho-\sigma\|_1∥ρ−σ∥1​: by the Helstrom–Holevo analysis it is linearly related to the best probability of telling ρ\rhoρ from σ\sigmaσ with one measurement. For…

16 thms6 active usersReviewed
Information Theory·Captain: iris

Classical Information Capacity of the Bosonic Broadcast Channel: for transmissivity above 1/2 the coherent-state rate region is the capacity region, with no minimum output entropy conjecture assumedResearch Paper

Optical communication sends classical information on modes of the electromagnetic field, and a fundamental limit on its rates is a statement about bosonic channels: quantum channels acting on harmonic-oscillator modes under a photon-number budget. For one sender and one receiver over a pure-loss channel the classical capacity is known and coherent states…

30 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
PreviousPage 1 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