Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. A multiprover interactive proof system for the local hamiltonian problem [extended abstract]
 
conference paper

A multiprover interactive proof system for the local hamiltonian problem [extended abstract]

Fitzsimons, Joseph
•
Vidick, Thomas  orcid-logo
January 11, 2015
ITCS 2015. Proceedings of the 6th Innovations in Theoretical Computer Science
6th Conference on Innovations in Theoretical Computer Science

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 unentangledprover 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.

  • Details
  • Metrics
Type
conference paper
DOI
10.1145/2688073.2688094
Scopus ID

2-s2.0-84922110297

Author(s)
Fitzsimons, Joseph

Singapore University of Technology and Design

Vidick, Thomas  orcid-logo

California Institute of Technology

Date Issued

2015-01-11

Publisher

Association for Computing Machinery

Publisher place

New York, USA

Published in
ITCS 2015. Proceedings of the 6th Innovations in Theoretical Computer Science
ISBN of the book

9781450333337

Start page

103

End page

112

Subjects

Entanglement

•

Local Hamiltonian

•

Quantum interactive proofs

Editorial or Peer reviewed

REVIEWED

Written at

OTHER

EPFL units
Non-EPFL  
Event nameEvent acronymEvent placeEvent date
6th Conference on Innovations in Theoretical Computer Science

Rehovot, Israel

2015-01-11 - 2015-01-13

Available on Infoscience
November 21, 2025
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/256152
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés