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

unitaryQIP = unitaryPSPACEResearch Paper

Quantum complexity theory has long classified decision problems, and more recently it has classified state synthesis (preparing a target quantum state) and unitary synthesis (applying a target unitary to an unknown input state). For decision problems, interactive proofs capture polynomial space: QIP=PSPACE\mathsf{QIP}=\mathsf{PSPACE}QIP=PSPACE (Jain, Ji, Upadhyay, Watrous 2011)…

53 thms3 active usersReviewed
Mathematical PhysicsTheoretical Computer Science·Captain: iris

Toward an Optimal Quantum Algorithm for Geometrically Local Hamiltonian SimulationResearch Paper

Simulating the time evolution e−iHTe^{-iHT}e−iHT of a many-body Hamiltonian is the task quantum computers were first proposed for, and lattice Hamiltonians with short-range interactions are its most common instance in condensed-matter physics and quantum chemistry. On hardware with nearest-neighbor connectivity, the relevant cost is the circuit depth: how many layers…

28 thms3 active usersReviewed
Computational Complexity·Captain: iris

On Random Purifications of Isometries and ChannelsResearch Paper

Lower bounds for quantum algorithms that query an unknown unitary or channel are much harder to prove than lower bounds for algorithms that query a classical function, because the oracle's answers are quantum states. A recurring difficulty is that an isometry V:H([N])→H([M])V:\mathcal H([N])\to\mathcal H([M])V:H([N])→H([M]), which models a state-preparation procedure or the purification…

62 thms3 active usersReviewed
Machine LearningMathematical PhysicsTheoretical Computer Science·Captain: iris

Learning Arbitrary Lindbladians from Time EvolutionResearch Paper

A quantum device that is not perfectly isolated evolves under a Markovian open-system dynamics etLe^{t\mathcal L}etL, whose generator L\mathcal LL (a Lindbladian) combines a coherent Hamiltonian part with dissipation. Characterizing L\mathcal LL from experiments is a basic task in the calibration and benchmarking of quantum hardware: the coefficients of L\mathcal LL are…

60 thms3 active usersReviewed
Computational GeometryMarkov ChainTheoretical Computer Science·Captain: iris

Improved quantum volume estimation with transducers and amortized quantum walksResearch Paper

Estimating the volume of a convex body is a central problem of computational geometry and of the theory of randomized algorithms. Deterministic algorithms with membership access cannot approximate the volume within a polynomial factor using polynomially many queries (Elekes 1986; Bárány and Füredi 1987), while randomized algorithms based on Markov chain…

47 thms3 active usersReviewed
Complexity Theory·Captain: iris

Classical Oracle Separation of QMA from the QCMA Hierarchy and Quantum Cryptography Even When P = QCMAResearch Paper

QMA is the class of problems whose yes-instances have a quantum proof that an efficient quantum verifier can check; QCMA is the same with a classical proof (AN02). Whether quantum proofs are more powerful than classical ones cannot be settled unconditionally with current techniques, so it is studied relative to oracles. A sharper form of the question asks…

63 thms3 active usersReviewed
Machine LearningMathematical PhysicsProbability+1·Captain: iris

Efficiently Learning SYK HamiltoniansResearch Paper

Hamiltonian learning from Gibbs states asks for the couplings of an unknown Hamiltonian HHH given independent copies of its thermal state e−βH/tr e−βHe^{-\beta H}/\mathrm{tr}\,e^{-\beta H}e−βH/tre−βH. It is the quantum analogue of learning an undirected graphical model, and it underlies the calibration and verification of quantum simulators. Existing polynomial-time guarantees rely…

32 thms3 active usersReviewed
Information TheoryProbabilityTheoretical 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
Linear algebraOptimization·Captain: iris

Spectral Structure and Exact Arithmetic of Finite-Feedback Measurement DiscriminationResearch Paper

A receiver that measures a quantum system and reports back through a classical channel with only a few symbols can transmit only part of what the measurement learned. In Qi's manuscript Spectral Structure and Exact Arithmetic of Finite-Feedback Measurement Discrimination (November 2026), the value of such finite-feedback discrimination experiments reduces…

25 thms3 active usersReviewed
Computational Complexity·Captain: iris

Computational Work Extraction: The Complexity of CatalystsResearch Paper

A catalyst in quantum computation is an auxiliary register that an algorithm may use but must, in the end, return. Catalysts are studied in quantum thermodynamics, where they model resources that enable a transformation without being consumed, and in space-bounded computation, where a full but "borrowed" memory can be more useful than a small clean one.…

34 thms3 active usersReviewed
Complexity Theory·Captain: iris

A Noise Operator Approach to Quantum Query Complexity and Time-Space Tradeoff Lower BoundsResearch Paper

Lower bounds on quantum algorithms come in two kinds. Query lower bounds count how many times an algorithm must read its input; time-space tradeoffs bound the product of running time and memory. For problems with many outputs (sorting, hashing, matrix-vector products, integer multiplication), the classical route to a time-space tradeoff, due to Borodin and…

26 thms3 active usersReviewed
Group TheoryRepresentation Theory·Captain: mikedeng1

(Almost) quadruply optimal unitary designs in 1DResearch Paper

Random unitary operations are used in quantum benchmarking, learning and information processing. A generic Haar-random operation on n qubits requires an exponential number of elementary gates. A unitary design replaces that full distribution by an implementable ensemble whose low-order moments reproduce Haar randomness to a specified accuracy. The resource…

43 thms3 active usersReviewed
Complexity Theory·Captain: mikedeng1

Tight Time-Space Lower Bounds for Collision Finding and Element Distinctness under Label SymmetryResearch Paper

A collision in a function is a pair of distinct inputs with the same output. Collision search is a basic test of the resources needed to attack an idealized hash function. Query counts alone leave out the memory used to retain previously observed values. The distinction matters for the quantum algorithms considered here: storing a table of values and…

27 thms3 active usersReviewed
Computational Complexity·Captain: mikedeng1

Optimal Separations Between Randomized and Quantum Query Complexity under Permutation SymmetryResearch Paper

A query algorithm learns an unknown input by asking for individual entries. Its cost counts those requests, allowing arbitrary computation between them. Quantum algorithms can query a superposition of positions, so comparing their query cost with randomized classical algorithms isolates an information advantage from implementation costs. For promise…

23 thms3 active usersReviewed
Markov ChainMathematical Physics·Captain: mikedeng1

Efficient classical simulation of Fermi-Hubbard models with Kramers symmetryResearch Paper

The partition function is the normalization that assigns thermal weights to a quantum system's energy levels. Computing it gives access to equilibrium quantities such as free energy. For interacting electrons, the underlying state space grows exponentially with the number of modes, making exact matrix calculations impractical even when the input Hamiltonian…

17 thms3 active usersReviewed
Complexity TheoryTheoretical Computer Science·Captain: iris

A Dichotomy for MIP* in the Presence of Unital NoiseResearch Paper

Two-prover interactive proofs with shared entanglement are extraordinarily powerful: with unlimited entanglement, MIP∗=RE\mathrm{MIP}^*=\mathrm{RE}MIP∗=RE (Ji, Natarajan, Vidick, Wright, Yuen; Comm. ACM 2021). That power rests on perfect EPR pairs. Physical entanglement is noisy, and the question is which noisy resources keep it and which lose it. Earlier work showed…

37 thms3 active usersReviewed
Computational ComplexityMachine Learning·Captain: iris

Optimal stabilizer testing and learning with limited quantum memoryResearch Paper

Stabilizer states are the quantum states prepared by Clifford circuits from ∣0n⟩|0^n\rangle∣0n⟩. They are the code states of stabilizer error-correcting codes, the states that classical computers can simulate efficiently, and the standard benchmark class in quantum learning theory. Deciding whether an unknown state is a stabilizer state, given copies of it, is the…

60 thms3 active usersReviewed
Representation TheoryTheoretical Computer Science·Captain: iris

Optimal tomography of bosonic and fermionic Gaussian statesResearch Paper

Quantum state tomography asks for an estimate ρ^\hat\rhoρ^​ of an unknown state ρ\rhoρ from nnn independent copies ρ⊗n\rho^{\otimes n}ρ⊗n. For arbitrary states on Cd\mathbb C^dCd the number of copies needed to reach fidelity F(ρ,ρ^)2≥1−ε2F(\rho,\hat\rho)^2\ge1-\varepsilon^2F(ρ,ρ^​)2≥1−ε2 with probability 1−δ1-\delta1−δ is Θ((d2+log⁡δ−1)/ε2)\Theta((d^2+\log\delta^{-1})/\varepsilon^2)Θ((d2+logδ−1)/ε2) (O'Donnell–Wright 2016, Haah et al. 2016, Pe…

46 thms3 active usersReviewed
Mathematical PhysicsProbability·Captain: iris

Beyond light cones: State preparation complexity in quantum spin glassesResearch Paper

A central question in quantum complexity is which resources a quantum state must have to reach low energy for a hard, disordered Hamiltonian. For geometrically local models, light-cone arguments bound what shallow circuits can do: a depth-DDD circuit only correlates qubits inside a backward light cone. Dense spin glasses have no geometry, so light-cone…

25 thms3 active usersReviewed
Computational Complexity·Captain: mikedeng1

Improved Quantum Query Bounds for Boolean Matrix Product VerificationResearch Paper

A Boolean matrix product replaces scalar addition by OR and multiplication by AND. It describes whether a pair of objects has at least one intermediate witness: for example, whether two vertices are joined by a walk through a middle layer. Checking a proposed product is a natural alternative to computing the entire product. Researchers in quantum query…

33 thms3 active usersReviewed
Captain: mikedeng1

Optimal Trace Distance EstimationResearch Paper

A quantum experiment can prepare a state many times while leaving its matrix entries unknown. Comparing two such preparations requires a numerical measure of their difference. The trace distance describes how well the preparations can be distinguished by a measurement: for equal prior probabilities, the optimal discrimination probability is one half of one…

34 thms3 active usersReviewed
Complexity Theory·Captain: iris

Separating QMA from QCIP with a Classical Oracle, or, the Power of Quantum Proofs over Classical Interaction for Quantum VerifiersResearch Paper

QMA is the class of problems whose yes-instances have a quantum proof: a polynomial-size quantum state that an efficient quantum verifier can check. QCMA is the same with a classical proof. Whether quantum proofs are more powerful than classical ones is a basic question of quantum complexity theory, and since an unconditional answer would separate classes…

76 thms3 active usersReviewed
Machine LearningMathematical PhysicsTheoretical Computer Science·Captain: iris

Learning the structure of open quantum systemsResearch Paper

Controllable quantum devices are now large enough that their dynamics must be characterized from data rather than from first principles. For closed systems this is Hamiltonian learning from real-time evolution: given access to e−iHte^{-iHt}e−iHt, estimate the coefficients of an unknown local Hamiltonian HHH (HKT24, BLMT24c). Real devices are open systems: they exchange…

83 thms3 active usersReviewed
Probability·Captain: mikedeng1

A computational phase diagram for the transverse field Ising modelResearch Paper

The transverse field Ising model describes interacting two-state quantum spins in a field that does not commute with their interaction. Its partition function normalizes the thermal state, while observable expectations describe measurements of that state. Classical access to these quantities matters for comparing thermal predictions across interacting…

37 thms3 active usersReviewed
Complexity Theorycryptography·Captain: mikedeng1

Compressed Oracle Duality: A simple framework for knowing what quantum adversaries knowResearch Paper

A collision in a function is a pair of distinct inputs with the same output. In the random-oracle model, the function is chosen uniformly from all functions with a prescribed finite domain and range. Quantum algorithms can query such a function on a superposition of inputs, so counting queries alone does not describe the memory needed to find a collision.…

23 thms3 active usersReviewed
PreviousPage 10 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