Tsuyoshi Ito: Parallelization of entanglement-resistant multi-prover interactive proofs

Tsuyoshi Ito, Institute for Quantum Computing (IQC)

Abstract

Multi-prover interactive proof systems with entangled provers are one of the topics intensively studied in quantum computational complexity theory in relation to quantum nonlocality. 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. In this talk, we show 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.