Document Open Access Logo

Pointer Quantum PCPs and Multi-Prover Games

Authors Alex B. Grilo, Iordanis Kerenidis, Attila Pereszlényi

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2016.21.pdf
  • Filesize: 478 kB
  • 14 pages

Document Identifiers

Author Details

Alex B. Grilo
Iordanis Kerenidis
Attila Pereszlényi

Cite As Get BibTex

Alex B. Grilo, Iordanis Kerenidis, and Attila Pereszlényi. Pointer Quantum PCPs and Multi-Prover Games. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 21:1-21:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.MFCS.2016.21

Abstract

The quantum PCP (QPCP) conjecture states that all problems in QMA, the quantum analogue of NP, admit quantum verifiers that only act on a constant number of qubits of a polynomial size quantum proof and have a constant gap between completeness and soundness. Despite an impressive body of work trying to prove or disprove the quantum PCP conjecture, it still remains widely open. The above-mentioned  proof verification statement has also been shown equivalent to the QMA-completeness of the Local Hamiltonian problem with constant relative gap. Nevertheless, unlike in the classical case, no equivalent formulation in the language of multi-prover games is known.

In this work, we propose a new type of quantum proof systems, the Pointer QPCP, where a verifier first accesses a classical proof that he can use as a pointer to which qubits from the quantum part of the proof to access. We define the Pointer QPCP conjecture, that states that all problems in QMA admit quantum verifiers that first access a logarithmic number of bits from the classical part of a polynomial size proof, then act on a constant number of qubits from the quantum part of the proof, and have a constant gap between completeness and soundness. We define a new QMA-complete problem, the Set Local Hamiltonian problem, and a new restricted class of quantum multi-prover games, called CRESP games. We use them to provide two other equivalent statements to the Pointer QPCP conjecture: the Set Local Hamiltonian problem with constant relative gap is QMA-complete; and the approximation of the maximum acceptance probability of CRESP games up to a constant additive factor is as hard as QMA. Our new conjecture is weaker than the original QPCP conjecture and hence provides a natural intermediate step towards proving the quantum PCP theorem. Furthermore, this is the first equivalence between a quantum PCP statement and the inapproximability of quantum multi-prover games.

Subject Classification

Keywords
  • computational complexity
  • quantum computation
  • PCP theorem

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Dorit Aharonov, Itai Arad, Zeph Landau, and Umesh Vazirani. The detectability lemma and quantum gap amplification. In Proceedings of the \engordnumber41 Annual ACM Symposium on Theory of Computing (STOC '09), pages 417-426, 2009. Google Scholar
  2. Dorit Aharonov, Itai Arad, and Thomas Vidick. Guest column: the quantum PCP conjecture. SIGACT News, 44(2):47-79, 2013. Google Scholar
  3. Dorit Aharonov and Lior Eldar. The commuting local Hamiltonian problem on locally expanding graphs is approximable in NP. Quantum Information Processing, 14(1):83-101, January 2015. Google Scholar
  4. Dorit Aharonov and Tomer Naveh. Quantum NP - A Survey, 2002. URL: http://arxiv.org/abs/arXiv:quantum-ph/0210077.
  5. Itai Arad. A Note About a Partial No-go Theorem for Quantum PCP. Quantum Info. Comput., 11(11-12):1019-1027, November 2011. URL: http://dl.acm.org/citation.cfm?id=2230956.2230966.
  6. Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. Journal of the ACM, 45(3):501-555, May 1998. Google Scholar
  7. Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: A new characterization of NP. Journal of the ACM, 45(1):70-122, January 1998. Google Scholar
  8. Fernando G. S. L. Brandão and Aram W. Harrow. Product-state approximations to quantum ground states. In Proceedings of the \engordnumber45 Annual ACM Symposium on Theory of Computing (STOC '13), pages 871-880, 2013. Google Scholar
  9. Toby S. Cubitt and Ashley Montanaro. Complexity classification of local Hamiltonian problems. In Proceedings of the \engordnumber55 IEEE Annual Symposium on Foundations of Computer Science (FOCS '14), pages 120-129, 2014. Google Scholar
  10. Irit Dinur. The PCP Theorem by Gap Amplification. Journal of the ACM, 54(3), June 2007. Google Scholar
  11. Lior Eldar and Aram W. Harrow. Local Hamiltonians with no low-energy trivial states, 2015. URL: http://arxiv.org/abs/1510.02082, URL: http://arxiv.org/abs/arXiv:quantum-ph/1510.02082.
  12. Joseph Fitzsimons and Thomas Vidick. A multiprover interactive proof system for the local Hamiltonian problem. In Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, (ITCS '15), pages 103-112, 2015. Google Scholar
  13. Sevag Gharibian, Yichen Huang, Zeph Landau, and Seung Woo Shin. Quantum Hamiltonian complexity. Foundations and Trends in Theoretical Computer Science, 10(3):159-282, 2015. Google Scholar
  14. Sean Hallgren, Daniel Nagaj, and Sandeep Narayanaswami. The local Hamiltonian problem on a line with eight states is QMA-complete. Quantum Info. Comput., 13(9-10):721-750, September 2013. Google Scholar
  15. Zhengfeng Ji. Classical verification of quantum proofs. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 885-898, 2016. Google Scholar
  16. Julia Kempe, Alexei Kitaev, and Oded Regev. The complexity of the local Hamiltonian problem. SIAM Journal on Computing, 35(5):1070-1097, May 2006. Google Scholar
  17. Julia Kempe and Oded Regev. 3-local Hamiltonian is QMA-complete. Quantum Info. Comput., 3(3):258-264, 2003. Google Scholar
  18. A. Kitaev, A. Shen, and M. N. Vyalyi. Classical and quantum computation. Graduate studies in mathematics. American mathematical society, 2002. URL: http://opac.inria.fr/record=b1100148.
  19. Anand Natarajan and Thomas Vidick. Constant-soundness interactive proofs for local hamiltonians. CoRR, abs/1512.02090, 2015. URL: http://arxiv.org/abs/1512.02090.
  20. Roberto Oliveira and Barbara M. Terhal. The complexity of quantum spin systems on a two-dimensional square lattice. Quantum Info. Comput., 8(10):900-924, 2008. Google Scholar
  21. Tobias J Osborne. Hamiltonian complexity. Reports on Progress in Physics, 75(2):022001, 2012. Google Scholar
  22. Ran Raz. A parallel repetition theorem. SIAM Journal on Computing, 27(3):763-803, June 1998. Google Scholar
  23. Ran Raz. Quantum information and the PCP theorem. In Proceedings of \engordnumber46 Annual IEEE Symposium on Foundations of Computer Science (FOCS '05), 2005. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact