Quantum Multi-Prover Interactive Proof Systems

Title: Quantum Multi-Prover Interactive Proof Systems

Main Research Question: How strong is a quantum analogue of multi-prover interactive proof systems?

Methodology: The researchers used the formal treatment of quantum computation to construct a quantum multi-prover interactive protocol. They assumed that provers could share at most polynomially many prior-entangled qubits.

Results: The researchers proved that the class of languages having quantum multi-prover interactive proof systems is necessarily contained in non-deterministic exponential time (NEXP). This implies that, under the assumption of limited prior entanglement, the class of languages having quantum multi-prover interactive proof systems is equal to NEXP. They also showed that, in the case a prover does not have his private qubits, the class of languages having quantum single-prover interactive proof systems is also equal to NEXP.

Implications: This research suggests that quantum multi-prover interactive proof systems might be weaker than classical ones, especially when provers are allowed to share prior-entangled qubits. It also provides a basis for further exploration into the power and limitations of quantum interactive proof systems.

Link to Article: https://arxiv.org/abs/0102013v5 Authors: arXiv ID: 0102013v5