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
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
Complexity TheoryQuantum Error Correction·Captain: mikedeng1

The color code, the surface code, and the transversal CNOT: NP-hardness of minimum-weight decodingResearch Paper

A quantum error-correcting code stores information in a subspace detected by commuting parity checks. A syndrome records which checks report an error. A decoder must turn that information into a recovery operation. Since a quantum computer generates check outcomes throughout its operation, the classical computation required for recovery is part of its…

16 thms3 active usersReviewed
Complexity TheoryProbability·Captain: mikedeng1

Nearly Linear Sample Bounds for Testing Product-State Satisfiability of Dense Quantum kkk-SATResearch Paper

A constraint satisfaction problem asks whether one assignment can meet every local requirement in a large system. Property testing asks a different question: can a small random induced subsystem distinguish a satisfiable instance from one requiring many constraint deletions? The distinction matters when the number of variables is large but the allowed error…

18 thms3 active usersReviewed
Captain: mikedeng1

Optimal Tolerant Testing of Lindbladian DissipationResearch Paper

A quantum device can change because of coherent Hamiltonian motion or because of coupling to its environment. Distinguishing these contributions matters when assessing whether physical noise lies below a prescribed tolerance. Reconstructing every interaction would answer a substantially larger question than such a test requires. Bao, Cai and Shang study the…

21 thms3 active usersReviewed
Probability·Captain: mikedeng1

Near-Optimal Mixedness Testing with Pauli MeasurementsResearch Paper

An experimenter may need to determine whether a prepared quantum system is maximally mixed without reconstructing its entire state. The restriction on available measurements matters: measuring each qubit separately gives a different information budget from a measurement that jointly processes many qubits or many copies. Mixedness testing asks for a decision…

19 thms3 active usersReviewed
Quantum Mechanics·Captain: mikedeng1

Sharp universal death of entanglement threshold for Pauli HamiltoniansResearch Paper

A quantum system in thermal equilibrium can retain correlations that cannot be reproduced by mixing independently prepared single-qubit states. For researchers studying quantum many-body systems and classical descriptions of quantum states, a basic question is when sufficiently high temperature rules out this entanglement uniformly over an interaction…

18 thms3 active usersReviewed
Computational ComplexityProbability·Captain: mikedeng1

BQP⊆IP Does Not RelativizeResearch Paper

A quantum computation can produce an answer that a classical computer cannot efficiently reproduce. An interactive proof asks whether a classical verifier can nevertheless check that answer by exchanging messages with an unrestricted prover. The verifier must accept correct claims with high probability and reject incorrect claims regardless of the prover’s…

25 thms3 active usersReviewed
Probability·Captain: mikedeng1

Local random quantum circuits converge to the Porter-Thomas distribution in polynomial depthResearch Paper

Random circuit sampling asks for samples from the bitstring distribution produced by a given quantum circuit acting on the all-zero input. Analyses of this task and its experimental benchmarks use statistical predictions about random circuits. A central prediction concerns how the probability of one fixed output varies when the circuit is sampled…

18 thms3 active usersReviewed
Complexity Theory·Captain: iris

Quantum State Search with Classical Interactive AdviceResearch Paper

Unstructured search over 2n2^n2n items needs Θ(2n/2)\Theta(2^{n/2})Θ(2n/2) quantum queries (Grover; Bennett, Bernstein, Brassard and Vazirani), and a prover who knows the marked item removes that cost by sending its nnn-bit address. The question behind this mission is whether classical communication helps in the same way when the hidden object is a quantum state.

39 thms3 active usersReviewed
Complexity Theory·Captain: iris

Strong Selective and List-Decoding Direct Product Theorems for Quantum Query ComplexityResearch Paper

A direct product theorem says that solving kkk independent instances of a problem is kkk times as hard as solving one, and that an algorithm with fewer resources fails on the kkk-fold problem with probability exponentially close to 111 in kkk. The second, "strong" form is what lower-bound applications need. Time-space tradeoffs in the style of Borodin and Cook cut a…

48 thms3 active usersReviewed
Information TheoryTheoretical Computer Science·Captain: iris

Structural Lower Bounds with Persistent Quantum MemoryResearch Paper

How many copies of an unknown quantum state does a learner need to estimate many expectation values Tr⁡(ρGj)\operatorname{Tr}(\rho G_j)Tr(ρGj​) at once? The answer depends sharply on the learner's quantum memory. A learner that measures each copy and keeps only classical records can need exponentially more copies than one that stores many copies and measures them jointly (C…

27 thms3 active usersReviewed
CombinatoricsInformation TheoryTheoretical Computer Science·Captain: iris

Binary code rate bounds via classical-quantum channelsResearch Paper

A binary error-correcting code of length nnn is a set C⊆{0,1}n\mathcal C\subseteq\{0,1\}^nC⊆{0,1}n of codewords. Its minimum distance dmin⁡(C)d_{\min}(\mathcal C)dmin​(C), the least Hamming distance between two distinct codewords, guarantees correction of every pattern of fewer than dmin⁡/2d_{\min}/2dmin​/2 bit flips, wherever they occur. How many codewords such a guarantee allows is measured by the asymp…

25 thms3 active usersReviewed
Complexity TheoryGraph TheoryTheoretical Computer Science·Captain: iris

Algorithmic Wave-Particle Duality: Pathfinding in Welded Trees is HardResearch Paper

The welded trees problem is the standard example of an exponential quantum speedup for a problem defined by a graph given only through a neighbor oracle. Childs, Cleve, Deotto, Farhi, Gutmann and Spielman showed in 2003 (doi:10.1145/780542.780552) that a continuous-time quantum walk started at the entrance of a randomly welded pair of binary trees reaches…

34 thms3 active usersReviewed
Machine Learning·Captain: iris

Online Shadow Tomography Matching the Classical BoundsResearch Paper

Shadow tomography asks how many copies of an unknown quantum state are needed to estimate many expectation values Tr(Aρ)\mathrm{Tr}(A\rho)Tr(Aρ) to accuracy ε\varepsilonε, without learning the whole state (Aaronson, 2018). In the online version the observables arrive one at a time, each chosen by an adversary who has seen all earlier answers. The question sits between…

38 thms3 active usersReviewed
Complexity Theorycryptography·Captain: iris

Unitary Complexity in Polynomial SpaceResearch Paper

Classical complexity theory studies functions on bit strings; many quantum tasks are instead unitary transformations: implement a given unitary on an arbitrary input state. The unitary synthesis problem of Aaronson and Kuperberg (AK07) asks whether every sequence of unitaries can be implemented by polynomial-size quantum circuits once the circuits may query…

73 thms3 active usersReviewed
Mathematical PhysicsProbabilityStatistical Mechanics·Captain: iris

Parisi formula and product-state optimization of quantum mixed p-spin HamiltoniansResearch Paper

Random Hamiltonians with many-body interactions are the quantum counterpart of classical mean-field spin glasses. They are a test bed for two questions in quantum information: how close product states come to the true ground state, and which optimization problems are easy on average though hard in the worst case. For worst-case two-local Hamiltonians,…

77 thms3 active usersReviewed
Complexity TheoryGraph TheoryTheoretical Computer Science·Captain: iris

Quantum Advantage in Local Certification of Graph PropertiesResearch Paper

In local certification, an untrusted prover (Merlin) assigns a certificate to every node of a network. The nodes then exchange messages with their neighbours for a fixed number of rounds and each node decides to accept or reject; the network accepts when all nodes accept. The resource measured is the certificate size per node. This model underlies…

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

Algorithmic Aspects of the Fermi–Hubbard ModelResearch Paper

The Fermi–Hubbard model is the standard minimal model of interacting electrons on a lattice. Each site holds up to two electrons (spin up and spin down); electrons hop between neighbouring sites with amplitude tijt_{ij}tij​, pay an energy UiU_iUi​ when two of them share a site, and feel a chemical potential μi\mu_iμi​. Its phase diagram (Mott insulators, antiferromagnetism,…

37 thms3 active usersReviewed
Complexity TheoryOptimizationTheoretical Computer Science·Captain: iris

What can be Computed with Indefinite Causal Structure?Research Paper

Quantum mechanics allows the order in which operations act to be in superposition. The process matrix formalism of Oreshkov, Costa and Brukner (OCB12) describes such situations: several laboratories each apply a local quantum operation, and a process matrix WWW fixes how their inputs and outputs are wired, without assuming a global causal order. Araújo, Feix,…

34 thms3 active usersReviewed
Condensed Matter PhysicsMathematical Physics·Captain: iris

Weakly interacting fermionic Gibbs states are Gaussian mixtures and classically simulableResearch Paper

Simulating interacting fermions at finite temperature is a central computational problem of condensed matter physics, quantum chemistry and nuclear physics, and general interacting fermionic problems are computationally hard in the worst case. Free fermions are the classical exception: their Gibbs states are fermionic Gaussian states, which are determined…

19 thms3 active usersReviewed
CombinatoricsRepresentation TheoryTheoretical Computer Science·Captain: iris

Compressed Permutation Oracles RevisitedResearch Paper

Random permutations and ideal ciphers model the primitives inside sponge hashing (SHA-3) and the Davies–Meyer compression function (SHA-1, SHA-2). A quantum adversary may query them in superposition, in both directions, which makes the information gained by its queries hard to track. For random functions, Zhandry's compressed oracle represents an oracle's…

33 thms3 active usersReviewed
PreviousPage 7 of 41Next

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