| | |
| | |
Stat |
Members: 3645 Articles: 2'506'133 Articles rated: 2609
27 April 2024 |
|
| | | |
|
Article overview
| |
|
Constant-Space Quantum Interactive Proofs Against Multiple Provers | Tomoyuki Yamakami
; | Date: |
2 Sep 2013 | Abstract: | We present upper and lower bounds of the prover complexity of multiple-prover
quantum interactive proof systems whose verifiers are limited to two-way
quantum finite automata. We prove that a two-way communication model of
expected polynomial-time multiple-prover systems can recognize languages in
NEXP, the nondeterministic exponential-time class. This answers an open
question raised by Nishimura and Yamakami [J. Comput. System Sci, 75,
pp.255--269, 2009]. Our proofs are simple and intuitive, although they heavily
rely on an earlier result on multiple-prover interactive proof systems of Feige
and Shamir [J. Comput. System Sci., 44, pp.259--271, 1992]. | Source: | arXiv, 1309.0429 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
|
| |
|
|
|
| News, job offers and information for researchers and scientists:
| |