## Quantum PCP Theorem

Although I think I know the answers to these, I'd just like to collect them all in one place.

What is the quantum PCP theorem, what implications does its proof have for simulation of Hamiltonians and is following Irit Dinur's reproof of the classical version the best/only current mode of attack (and if so why?) What is the sort of math/physics/theoretical CS background needed to approach this problem?

-
 That's probably more appropriate for cstheory.stackexchange.com – Yuval Filmus Nov 7 2010 at 0:23 If I post it there, should I delete this? – Noah Rahman Nov 7 2010 at 2:55 @Noah: Please don't delete this question, as the answer currently posted is a good one. In the cstheory FAQ, we ask people not to crosspost there and here simultaneously, and to link the questions to each other. That way people don't do double work. – Aaron Sterling Nov 7 2010 at 13:15

The quantum PCP conjecture (nobody has proved it, so you can't call it a theorem) is possibly (there are a few different ways of generalizing the classical PCP theorem to the quantum regime, and I don't believe any of them deserves the name of the quantum PCP conjecture) given below. Here $k$, $c$, and $d$ are small fixed integer constants, and $\epsilon$ is a constant between 0 and 1.

There is a polynomial time algorithm that does the follows: The input is a $k$-local Hamiltonian $H$ with $n$ terms each of total energy 1; the ground state energy of $H$ is either $0$ or greater than $1/n^c$. The output is a new $k$-local Hamiltonian $H'$, with $O(n^{d})$ terms. If the ground-state energy of $H$ is $0$, then $H'$ will also have ground-state energy $0$. If the ground-state energy of $H$ is at least $1/n^c$, then $H'$ will have ground-state energy at least $\epsilon n^{d}$.

If you're using qubits, you should probably take $k=4$, by Bravyi's results on Quantum $k$-SAT. Certainly $k\geq 4$, unless Quantum 3-SAT is QMA-complete.

This would be an incredibly important development in the theory of quantum computing, but I'm not sure whether a proof has any practical implications for simulation of Hamiltonians. What it would show is that it is QMA-complete to tell whether an $n$-term local Hamiltonian has energy $0$ or at least $\epsilon n$.

Begin(rant)

Asking whether method $X$ is the best way to attack a big open mathematical conjecture is not a question anybody can answer. If you asked in this forum, for example, what is the best way to prove the Riemann hypothesis, and what mathematics you needed to learn in order to do this, your question would probably be promptly closed.

End(rant)

If I had to guess whether a quantum generalization of PCP was even true, I'd probably guess "no." It seems like an incredibly strong statement to me. On the other hand, the classical PCP theorem was also an incredibly strong statement. But just because a miracle happens in the classical regime, should you really be expecting the same miracle in the quantum regime?

-
Scott Aaronson seems to be much more optimistic on that matter: scottaaronson.com/blog/?p=139 – Anthony Leverrier Nov 7 2010 at 16:13
@Anthony: Note that Scott's blog entry was four years ago. I have a Bayesian probability calculation for you. Scott said that he was 99% sure it was true, and also said that he was 85% sure that, should enough people make it a priority, it was achievable in a year or so. Given that several very smart people tried hard to prove it in the last four years (I won't give names here), and failed, with what probability should Scott currently believe the quantum PCP theorem is true? – Peter Shor Nov 7 2010 at 16:24
@Peter: Well, I'm not sure there is sufficient data to answer that, but I guess it should be below 99%. – Anthony Leverrier Nov 7 2010 at 16:47
@Anthony: I wasn't actually expecting an answer. ;-) – Peter Shor Nov 7 2010 at 16:55
@Noah, I don't think one pessimistic researcher proves there's a climate of prevailing pessimism. When you're trying to retrace Dinur's proof, you do appear to come across some pretty tough obstacles, but I don't know of any other feasible-looking ideas about how to approach the question, so maybe we're just looking under the lamppost. – Peter Shor Nov 7 2010 at 17:31