Quantum Multi-Prover Interactive Proof Systems

Title: Quantum Multi-Prover Interactive Proof Systems

Research Question: Can quantum computation provide an advantage in the setting of multi-prover interactive proof systems, which are a natural extension of single-prover systems?

Methodology: The researchers introduced a model of quantum multi-prover interactive proof systems by naturally extending the model of single-prover systems. They then proved that the class of languages that have quantum multi-prover interactive proof systems equals to NEXP, indicating that the quantum analogue has no gain to the classical counterpart in this setting.

Results: The researchers showed that in cases where the prover does not have his private qubits, the class of languages that have single-prover quantum interactive proof systems also equals to NEXP. This means that the quantum analogue provides no advantage over the classical counterpart in these cases either.

Implications: These results suggest that the power of quantum computation in the setting of multi-prover interactive proof systems is not greater than that of classical computation. This is in contrast to the single-prover case, where quantum computation has been shown to provide an advantage. The findings may have implications for the development of quantum algorithms and the understanding of the power of quantum computation in general.

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