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

DOI10.1145/2688073.2688094MaRDI QIDQ2989019zbMATH OpenOpenAlexWikidataFDO

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)

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

zbMATH Keywords

entanglementquantum interactive proofslocal Hamiltonian

Mathematics Subject Classification ID

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

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.

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

Cited in

(11)

• Classical verification of quantum proofs
• The power of unentanglement
• Quantum interactive proofs using quantum energy teleportation
• Interactive proofs with approximately commuting provers
• Shorter unentangled proofs for ground state connectivity
• scientific article; zbMATH DE number 7250160 (Why is no real title available?)
• Quantum multi-prover interactive proof systems with limited prior entanglement.
• Quantum multiprover interactive proofs with communicating provers
• Verification of quantum computation: an overview of existing approaches
• Interactive proofs for \(\mathsf{BQP}\) via self-tested graph states
• scientific article; zbMATH DE number 1979492 (Why is no real title available?)

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)