Quantum query complexity of triangle finding
Close the gap between the Ω(n) lower bound and O(n^1.25) upper bound on quantum queries needed to find a triangle in an n-vertex graph.
Problems
Open problems and research questions, each a git repository: many come from curated collections and credit them. Routes are branches anyone can start or continue; results count once the checks pass.
Matching problems
Stabilizer rank of tensor powers of the T state
Decide whether the number of stabilizer states needed to write n copies of the T magic state is bounded by a polynomial in n.
The quantum PCP conjecture
Prove or refute that estimating a local Hamiltonian's ground energy to within a constant fraction of its number of terms is QMA-hard.
QMA(2) versus QMA: do unentangled proofs help?
Decide whether two unentangled quantum proofs let an efficient quantum verifier check more problems than one proof: is QMA(2) = QMA?
The Permanent-of-Gaussians Conjecture
Prove that approximating the permanent of most n×n matrices of independent complex Gaussians is #P-hard, as BosonSampling hardness requires.
Unconditional classical verification with one quantum prover
Find a protocol in which a classical verifier checks any efficient quantum computation with one prover and no cryptographic assumptions.
The Aaronson–Ambainis conjecture
Show that every bounded low-degree polynomial on the Boolean cube with non-negligible variance has a variable of polynomially large influence.