Physics – Quantum Physics
Scientific paper
2008-10-03
Physics
Quantum Physics
26 pages
Scientific paper
A central problem in quantum computational complexity is how to prevent entanglement-assisted cheating in multi-prover interactive proof systems. It is well-known that the standard oracularization technique completely fails in some proof systems under the existence of prior entanglement. This paper studies two constructions of two-prover one-round interactive proof systems based on oracularization. First, it is proved that the two-prover one-round interactive proof system for PSPACE by Cai, Condon, and Lipton still achieves exponentially small soundness error in the existence of prior entanglement between dishonest provers (and more strongly, even if dishonest provers are allowed to use arbitrary no-signaling strategies). It follows that, unless the polynomial-time hierarchy collapses to the second level, two-prover systems are still advantageous to single-prover systems even when only malicious provers can use quantum information. Second, it is proved that the two-prover one-round interactive proof system obtained by oracularizing a three-query probabilistically checkable proof system becomes sound in a weak sense even against dishonest entangled provers with the help of a dummy question. As a consequence, every language in NEXP has a two-prover one-round interactive proof system of perfect completeness, albeit with exponentially small gap between completeness and soundness, in which each prover responds with only two bits. In other words, it is NP-hard to approximate within an inverse-polynomial the value of a classical two-prover one-round game, even when provers are entangled and each sends a two-bit answer to a verifier.
Ito Tsuyoshi
Kobayashi Hirotada
Matsumoto Keiji
No associations
LandOfFree
Oracularization and Two-Prover One-Round Interactive Proofs against Nonlocal Strategies does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Oracularization and Two-Prover One-Round Interactive Proofs against Nonlocal Strategies, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Oracularization and Two-Prover One-Round Interactive Proofs against Nonlocal Strategies will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-410235