Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
428521 | Information Processing Letters | 2014 | 5 Pages |
Abstract
•We study classical multi-prover interactive proofs which are sound also against entangled provers.•Such interactive proofs have been studied widely in quantum complexity theory.•We prove such interactive proofs can be parallelized to two rounds by adding one prover.
Multi-prover interactive proof systems are said to be entanglement-resistant if the soundness holds even when provers are allowed to share an arbitrary quantum state before the interaction starts. This letter proves that every entanglement-resistant multi-prover interactive proof system can be parallelized to two rounds without ruining its entanglement resistance at the expense of adding one prover.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Tsuyoshi Ito,