A Caltech Library Service

A Multiprover Interactive Proof System for the Local Hamiltonian Problem

Fitzsimons, Joseph and Vidick, Thomas (2015) A Multiprover Interactive Proof System for the Local Hamiltonian Problem. In: ITCS'15 Innovations in Theoretical Computer Science. Association for Computing Machinery , New York, NY, pp. 103-112. ISBN 978-1-4503-3333-7.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


We give a quantum interactive proof system for the local Hamiltonian problem on n qubits in which (i) the verifier has a single round of interaction with five entangled provers, (ii) the verifier sends a classical message on O(log n) bits to each prover, who replies with a constant number of qubits, and (iii) completeness and soundness are separated by an inverse polynomial in $n$. As the same class of proof systems, without entanglement between the provers, is included in QCMA, our result provides the first indication that quantum multiprover interactive proof systems with entangled provers may be strictly more powerful than unentangled-prover interactive proof systems. A distinguishing feature of our protocol is that the completeness property requires honest provers to share a large entangled state, obtained as the encoding of the ground state of the local Hamiltonian via an error-correcting code. Our result can be interpreted as a first step towards a multiprover variant of the quantum PCP conjecture.

Item Type:Book Section
Related URLs:
URLURL TypeDescription Paper
Vidick, Thomas0000-0002-6405-365X
Additional Information:Copyright is held by the owner/author(s). Publication rights Licensed to ACM. This work was started while both authors were hosted by the Simons Institute in Berkeley, whose financial support we gratefully acknowledge. The second author is grateful to Dorit Aharonov and Umesh Vazirani for pressing him to expose the question investigated in this paper during an open problems session organized at the institute. Joseph Fitzimons' research is supported in part by the Singapore National Research Foundation under NRF Award No. NRFNRFF2013-01. Thomas Vidick's research was supported in part by the Simons Institute and the Ministry of Education, Singapore under the Tier 3 grant MOE2012-T3-1-009.
Funding AgencyGrant Number
Singapore National Research FoundationNRF-F2013-01
Simons InstituteUNSPECIFIED
Ministry of Education (Singapore)MOE2012-T3-1-009
Subject Keywords:Local Hamiltonian, Quantum Interactive Proofs, Entanglement
Record Number:CaltechAUTHORS:20150218-115725417
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:54948
Deposited By: Ruth Sustaita
Deposited On:20 Feb 2015 05:06
Last Modified:10 Nov 2021 20:39

Repository Staff Only: item control page