Quantum PCP Conjecture

The Quantum PCP Conjecture or qPCP conjecture is an open problem in quantum information theory, an unproven quantum analogue of the classical PCP theorem. It's often referred to as the Quantum PCP Theorem, but in fact it's not been verified, nor disproved yet; thus it remains a conjecture. It implies that calculating the energy of the Gibbs state of a quantum system in constant temperature is QMA-Complete.

Conjecture

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 $\mathrm {E} >0$ such that it is QMA-hard to approximate the ground state energy of the problem to an accuracy $\mathrm {E} N$.

The qPCP conjecture can be slightly generalized by considering 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 generalized qPCP conjecture would then be that it is QMA-hard to determine whether the ground state energy is $0$: given a promise that if it is not $0$, then it is at least $\mathrm {E} N$.

Sources

• Aharanov, Dorit; Arad, Itai; Vidick, Thomas (2013-09-28). "The Quantum PCP Conjecture". arXiv:1309.7495 [math.FA].

This article "Quantum PCP Conjecture" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:Quantum PCP Conjecture. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.

📰 Article(s) of the same category(ies)

• SCOP formalism
• ITU Focus Group on Quantum Information Technologies for Networks
• Ramanujan Machine
• Physical information

---