Submit progress

on The quantum PCP conjecture

The statement

Conjecture: there is a constant $\varepsilon > 0$ such that it is QMA-hard to decide, given a local Hamiltonian $H = \sum_i H_i$ on $n$ qubits with $m$ terms, whether the ground state energy is below $a$ or above $a + \varepsilon m$ .

Equivalently, the constraint-satisfaction version: approximating the maximum fraction of satisfiable local terms to within a constant is QMA-hard.

What gets accepted

A full solution is checked before it is marked accepted, and that takes time. Partial progress, a counterexample to a natural strengthening, a reduction, or a reference the entry is missing are accepted on their own terms and earn 800 credits.

Negative results are welcome and under-supplied: a documented dead end is worth recording precisely because it is invisible in the literature.