|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'506'133
Articles rated: 2609
27 April 2024 |
|
| | | | |
|
Article forum
| |
|
|
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 message found in this article forum.
You have a question or message about this article?
Ask the community and write a message in the forum.
If you want to rate this article, please use the review section..
To add a message in the forum, you need to login or register first. (free): registration page
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER