Quantum Multi-Prover Interactive Proof Systems

Title: Quantum Multi-Prover Interactive Proof Systems

Main Research Question: Can quantum computation provide a significant advantage over classical computation in the setting of multi-prover interactive proof systems?

Methodology: The researchers introduced a model of quantum multi-prover interactive proof systems, which is a natural extension of the single-prover quantum interactive proof systems. They aimed to determine if the quantum analogue has any gain over the classical counterpart in this setting.

Results: The researchers proved that the class of languages having quantum multi-prover interactive proof systems is equal to NEXP, implying that the quantum analogue has no gain over the classical counterpart. They also showed that, in case the prover does not have his private qubits, the class of languages having single-prover quantum interactive proof systems is also equal to NEXP.

Implications: These results provide the first exact characterizations of a classical time complexity class in quantum computational terms. They suggest that the power of quantum computation in the setting of multi-prover interactive proof systems is not significantly greater than that of classical computation. This could have implications for the development of quantum computing algorithms and the understanding of the power of quantum computation.

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