Thomas Vidick: A Multiprover Interactive Proof System for the Local Hamiltonian Problem
1Thomas Vidick (Caltech)
A Multiprover Interactive Proof System for the Local Hamiltonian Problem
QuICS Workshop on the Frontiers of Quantum Information and Computer Science (October 1, 2015)
In this talk I will introduce a variant of the “quantum PCP conjecture” formulated in terms of multiplayer games, and provide a first step toward the proof of the new conjecture.
For this, I will describe a quantum interactive proof system for the local Hamiltonian problem on n qubits in which the verifier has a single round of interaction with three entangled provers, receiving only a constant number of qubits from each prover. Completeness and soundness of this protocol are separated by an inverse polynomial in n, and the conjecture is that this can be improved to a constant.
This 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 a simple error-correcting code.
Based on joint work with Joseph Fitzsimons of the Centre for Quantum Technologies.