Quantum multiprover interactive proofs with communicating provers

DOI10.1137/090777724MaRDI QIDQ3190692zbMATH OpenOpenAlexFDO

Authors Michael Ben-Or, Avinatan Hassidim, Haran Pilpel

Publication date 18 September 2014

Published in SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

multiproverquantum complexity

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12)

Abstract: Multi Prover Interactive Proof systems (MIPs)were first presented in a cryptographic context, but ever since they were used in various fields. Understanding the power of MIPs in the quantum context raises many open problems, as there are several interesting models to consider. For example, one can study the question when the provers share entanglement or not, and the communication between the verifier and the provers is quantum or classical. While there are several partial results on the subject, so far no one presented an efficient scheme for recognizing NEXP (or NP with logarithmic communication), except for [KM03], in the case there is no entanglement (and of course no communication between the provers). We introduce another variant of Quantum MIP, where the provers do not share entanglement, the communication between the verifier and the provers is quantum, but the provers are unlimited in the classical communication between them. At first, this model may seem very weak, as provers who exchange information seem to be equivalent in power to a simple prover. This in fact is not the case - we show that any language in NEXP can be recognized in this model efficiently, with just two provers and two rounds of communication, with a constant completeness-soundness gap.

Recommendations

• Constant-space quantum interactive proofs against multiple provers
• Quantum multi-prover interactive proof systems with limited prior entanglement.
• scientific article; zbMATH DE number 1979492
• A multiprover interactive proof system for the local Hamiltonian problem (extended abtract)
• Interactive proofs with approximately commuting provers

Cited in

(19)

• Quantum multi-prover interactive proof systems with limited prior entanglement.
• Constant-space quantum interactive proofs against multiple provers
• Rank-one quantum games
• On the power of quantum, one round, two prover interactive proof systems
• On the power of many one-bit provers
• A multiprover interactive proof system for the local Hamiltonian problem (extended abtract)
• scientific article; zbMATH DE number 5899305 (Why is no real title available?)
• Interactive proofs with approximately commuting provers
• Pointer Quantum PCPs and Multi-Prover Games
• Quantum hedging in two-round prover-verifier interactions
• scientific article; zbMATH DE number 7378343 (Why is no real title available?)
• Quantum proof systems for iterated exponential time, and beyond
• Improved soundness for QMA with multiple provers
• Interactive proofs with competing teams of no-signaling provers
• scientific article; zbMATH DE number 6292749 (Why is no real title available?)
• STACS 2005
• Debates with small transparent quantum verifiers
• Unbounded violations of bipartite Bell inequalities via operator space theory
• Large violation of Bell inequalities with low entanglement

This page was built for publication: Quantum multiprover interactive proofs with communicating provers

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