9
$\begingroup$

I have a few questions about Quantum PCP conjecture:

  1. What is the statement of the quantum PCP conjecture?

  2. What implications would Quantum PCP theorem have for simulating of Hamiltonians?

  3. Is it believed adopting Irit Dinur's proof of the classical PCP theorem is likely to lead to a proof of Quantum PCP conjecture?

  4. What background is needed to read articles about the problem?

The copy of the question on MO

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ Related question: what are good references to understanding the proof of the PCP theorem? $\endgroup$
    – Kaveh
    Commented Nov 7, 2010 at 5:47
  • 13
    $\begingroup$ There is no quantum PCP theorem. People are trying to prove it, but whether such a theorem exists (and maybe exactly what form it would take) are one of the big open questions in quantum computing. $\endgroup$
    – Peter Shor
    Commented Nov 7, 2010 at 12:33
  • 7
    $\begingroup$ Noah Rahman: Please link to the original question when crossposting. Otherwise not everyone would be aware that you already received a very good answer from Peter Shor. mathoverflow.net/questions/45106/quantum-pcp-theorem $\endgroup$
    – Tsuyoshi Ito
    Commented Nov 7, 2010 at 13:06
  • 3
    $\begingroup$ I wish I knew what is the best approach to proving or disproving a quantum PCP theorem. The problem is that if I knew it, I would have already proved or disproved it. $\endgroup$
    – Tsuyoshi Ito
    Commented Nov 7, 2010 at 13:57
  • 2
    $\begingroup$ Sorry, I'll close the question. I was told by someone to go post it here. but to answer Robin's question my research has to do with the applicability of these so called DMRG algorithms, and that's how I came across the QPCP conjecture (having presented to a seminar class earlier on Kitaev's various QMA-complete problems) $\endgroup$
    – Noah Rahman
    Commented Nov 7, 2010 at 18:48

2 Answers 2

Reset to default
9
$\begingroup$

As Shor said, there is no QPCP theorem (yet!). One conjecture (let us call it the QPCP conjecture) is this: consider a graph of N vertices, of degree O(1). Associate a qudit with each vertex, with Hilbert space dimension O(1). Let the Hamiltonian be a sum of terms for each edge, each such term acting just on the qudits on the vertices, with operator norm of each such term bounded by O(1), so that the operator norm of the Hamiltonian is O(N). Then, the conjecture is that there is some epsilon>0 such that it is QMA-hard to approximate the ground state energy of the problem to an accuracy epsilon N.

A slightly stronger conjecture is to consider the case in which each such term acting on an edge is a projector so that the ground state energy is non-negative, and the conjecture is that it is QMA-hard to determine whether the ground state energy is 0 given a promise that if it is not zero then it is at least epsilon N.

There are other versions of the conjecture too, but those are two interesting ones with the most natural relation to physics. An even stronger conjecture (hence probably an easier one to disprove if you believe that these conjectures are false) is to consider the case in which the Hamiltonian is a sum of commuting projectors.

Improve this answer
$\endgroup$
1
  • 7
    $\begingroup$ The classical PCP theorem says that all of these questions are at least NP-hard. $\endgroup$
    – Peter Shor
    Commented Nov 18, 2010 at 18:37
7
$\begingroup$

Basically everything that is known about the Quantum PCP conjecture has been collected in this survey by Dorit Aharonov, Itai Arad, and Thomas Vidick:

The Quantum PCP Conjecture

See also Thomas' blog post on the topic.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.