Quantum PCP Theorem - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T14:06:11Z http://mathoverflow.net/feeds/question/45106 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/45106/quantum-pcp-theorem Quantum PCP Theorem Noah Rahman 2010-11-06T21:55:15Z 2010-11-07T15:11:02Z <p>Although I think I know the answers to these, I'd just like to collect them all in one place.</p> <p>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?</p> http://mathoverflow.net/questions/45106/quantum-pcp-theorem/45167#45167 Answer by Peter Shor for Quantum PCP Theorem Peter Shor 2010-11-07T13:03:49Z 2010-11-07T15:11:02Z <p>The quantum PCP conjecture (<em>nobody has proved it, so you can't call it a theorem</em>) is possibly (<em>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 <strong>the</strong> quantum PCP conjecture</em>) given below. Here $k$, $c$, and $d$ are small fixed integer constants, and $\epsilon$ is a constant between 0 and 1.</p> <blockquote> <p>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}$.</p> </blockquote> <p>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. </p> <p>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$.</p> <p><strong>Begin(rant)</strong></p> <p>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.</p> <p><strong>End(rant)</strong></p> <p>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?</p>