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?

  • $\begingroup$ That's probably more appropriate for cstheory.stackexchange.com $\endgroup$ – Yuval Filmus Nov 7 '10 at 0:23
  • $\begingroup$ If I post it there, should I delete this? $\endgroup$ – Noah Rahman Nov 7 '10 at 2:55
  • $\begingroup$ @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. $\endgroup$ – Aaron Sterling Nov 7 '10 at 13:15
  • $\begingroup$ Copy on cstheory $\endgroup$ – Kaveh Oct 13 '13 at 0:48

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. (EDITED June 2013: Quantum 3-SAT is indeed QMA complete. See this recent paper.)

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$.


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.


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?

  • 2
    $\begingroup$ Scott Aaronson seems to be much more optimistic on that matter: scottaaronson.com/blog/?p=139 $\endgroup$ – Anthony Leverrier Nov 7 '10 at 16:13
  • 5
    $\begingroup$ @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? $\endgroup$ – Peter Shor Nov 7 '10 at 16:24
  • 2
    $\begingroup$ @Peter: Well, I'm not sure there is sufficient data to answer that, but I guess it should be below 99%. $\endgroup$ – Anthony Leverrier Nov 7 '10 at 16:47
  • 2
    $\begingroup$ @Anthony: I wasn't actually expecting an answer. ;-) $\endgroup$ – Peter Shor Nov 7 '10 at 16:55
  • 1
    $\begingroup$ @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. $\endgroup$ – Peter Shor Nov 7 '10 at 17:31

One more comment:

The quantum PCP conjecture implies that calculating the energy of the Gibbs state of a quantum system in constant temperature is QMA-Complete. This answers the question:

what implications does its proof have for simulation of Hamiltonians?

Given a Hamiltonian $H$, the Gibbs state is defined by: $$\rho_{\mathrm{gibbs}} = \frac{1}{Z}\exp(-H/T)$$ where the normalization factor $Z=\operatorname{Tr}(\exp(-H/T))$.

It is known that the Gibbs state minimizes the free energy (H - TS): $$\rho_{\mathrm{gibbs}}=\operatorname{argmin}_{\rho \succeq 0, \operatorname{Tr}(\rho)=1} \operatorname{Tr}(H\rho) + T \cdot \operatorname{Tr}(\rho \ln \rho)$$

Let $\rho_{\min}$ be one of the pure ground states of $H$, with energy $E_0$. Since $\rho_{\min}$ is a pure state, $Tr(\rho \ln \rho)=0$.
Therefore, $$\operatorname{Tr}(H\rho_{\mathrm{gibbs}}) + T \cdot Tr(\rho_{\mathrm{gibbs}} \ln \rho_{\mathrm{gibbs}}) \leq \operatorname{Tr}(H \rho_{min}) = E_0.$$

Since $\operatorname{Tr}(\rho \ln \rho) \leq n \ln d$, where $n$ is the number of qudits (of dimension $d$ in the systems,

$$\operatorname{Tr}(H\rho_{gibbs}) \leq E_0 + T n \ln d .$$ By choosing $T = O\left(\frac{\epsilon}{\ln d}\right)$ one gets an additive approximation of $\epsilon n \leq \epsilon m$ to the ground energy, which is $QMA$-hard by the quantum PCP conjecture ($m$ is the number of terms in the Hamiltonian, therefore it is at least linear in the number of qubits in the system).

I believe this result is a folklore, and clearly also holds in the classical setting. I learned about it from the following paper: Brandão, F. G., & Harrow, A. W. (2013, June). Product-state approximations to quantum ground states. In Proceedings of the 45th annual ACM symposium on Symposium on theory of computing (pp. 871-880). ACM.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.