Quantum PCP and Hamiltonian complexity

6 problems

• Classical efficiency of 2D gapped ground-state energy estimation

  Open

  For one-dimensional systems with an energy gap, a classical computer can provably find the ground energy quickly. Whether the same holds for two-dimensional gapped systems is unknown.

• Entanglement area law for gapped ground states in two dimensions

  Open

  In one dimension it is proven that ground states of systems with an energy gap hold entanglement only across region boundaries, which is why they are easy to compute. The same statement in two dimensions is widely believed but unproved.

• Is the commuting local Hamiltonian problem in NP

  Open

  When all energy terms of a quantum system commute, deciding whether it has zero ground energy looks closer to a classical problem. It is proven to have short classical proofs in several special cases but not in general.

• Existence of good quantum locally testable codes

  Partially resolved

  A locally testable code lets a checker detect a corrupted message by looking at a few randomly chosen checks, with failure probability growing with the amount of corruption. Quantum versions with good size and error tolerance would be a step toward the quantum PCP conjecture, and their existence is open.

• No low-energy sampleable states conjecture

  Open

  Some quantum systems are now known to have no simple low-energy states that a shallow circuit can make. A stronger claim, that no low-energy state can even be sampled by a classical computer, is unproved.

• The quantum PCP conjecture for local Hamiltonians

  Open

  Computing the ground energy of a quantum system exactly enough is known to be as hard as any problem a quantum computer can check. The conjecture says that even an estimate with a fixed fractional error stays that hard.