A multiprover interactive proof system for the local Hamiltonian problem (extended abtract)

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

Authors: Joseph Fitzsimons, Thomas Vidick 

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

Recommendations

• Quantum multi-prover interactive proof systems with limited prior entanglement.
• scientific article; zbMATH DE number 1979492
• Using entanglement in quantum multi-prover interactive proofs
• Quantum multiprover interactive proofs with communicating provers
• Classical verification of quantum proofs

zbMATH Keywords

entanglementquantum interactive proofslocal Hamiltonian

Mathematics Subject Classification ID

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

Cited In (10)

• Shorter unentangled proofs for ground state connectivity
• Title not available (Why is that?)
• Verification of quantum computation: an overview of existing approaches
• Quantum multi-prover interactive proof systems with limited prior entanglement.
• The power of unentanglement
• Interactive proofs with approximately commuting provers
• Quantum multiprover interactive proofs with communicating provers
• Title not available (Why is that?)
• Classical verification of quantum proofs
• Interactive proofs for \(\mathsf{BQP}\) via self-tested graph states

This page was built for publication: A multiprover interactive proof system for the local Hamiltonian problem (extended abtract)

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