Article ID Journal Published Year Pages File Type
428521 Information Processing Letters 2014 5 Pages PDF
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
,