A Multiprover Interactive Proof System for the Local Hamiltonian Problem

DOI10.1145/2688073.2688094zbMATH Open1364.81078arXiv1409.0260OpenAlexW2102150964WikidataQ59792589 ScholiaQ59792589MaRDI QIDQ2989019FDOQ2989019

Thomas Vidick, Joseph Fitzsimons

Publication date: 19 May 2017

Published in: Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science (Search for Journal in Brave)

Abstract: 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 reply 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.

Full work available at URL: https://arxiv.org/abs/1409.0260

zbMATH Keywords

entanglement quantum interactive proofs local Hamiltonian

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum computation (81P68)

Cited In (2)

This page was built for publication: A Multiprover Interactive Proof System for the Local Hamiltonian Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2989019)