Quantum Multi-Prover Interactive Proof Systems: Difference between revisions
Created page with "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 interact..." |
No edit summary |
||
| (2 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
Title: Quantum Multi-Prover Interactive Proof Systems | Title: Quantum Multi-Prover Interactive Proof Systems | ||
Research Question: | Main Research Question: How strong is a quantum analogue of multi-prover interactive proof systems? | ||
Methodology: The researchers | 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 showed that in | 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: | 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/ | Link to Article: https://arxiv.org/abs/0102013v5 | ||
Authors: | Authors: | ||
arXiv ID: | arXiv ID: 0102013v5 | ||
[[Category:Computer Science]] | [[Category:Computer Science]] | ||
[[Category:Quantum]] | [[Category:Quantum]] | ||
[[Category:Prover]] | [[Category:Prover]] | ||
[[Category:Interactive]] | [[Category:Interactive]] | ||
[[Category:Proof]] | [[Category:Proof]] | ||
[[Category:Systems]] | |||
Latest revision as of 02:03, 24 December 2023
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