[HTML][HTML] Interactive proofs with quantum finite automata

H Nishimura, T Yamakami - Theoretical Computer Science, 2015 - Elsevier
H Nishimura, T Yamakami
Theoretical Computer Science, 2015Elsevier
Following an early work of Dwork and Stockmeyer on interactive proof systems whose
verifiers are two-way probabilistic finite automata, the authors initiated in 2004 a study on the
computational power of quantum interactive proof systems whose verifiers are particularly
limited to quantum finite automata. As a follow-up to the authors' early journal publication [J.
Comput. System Sci., vol. 75, pp. 255–269, 2009], we further investigate the quantum nature
of interactions between provers and verifiers by studying how various restrictions on …
Abstract
Following an early work of Dwork and Stockmeyer on interactive proof systems whose verifiers are two-way probabilistic finite automata, the authors initiated in 2004 a study on the computational power of quantum interactive proof systems whose verifiers are particularly limited to quantum finite automata. As a follow-up to the authors' early journal publication [J. Comput. System Sci., vol. 75, pp. 255–269, 2009], we further investigate the quantum nature of interactions between provers and verifiers by studying how various restrictions on quantum interactive proof systems affect the language recognition power of the proof systems. In particular, we examine three intriguing restrictions that (i) provers always behave in a classical fashion, (ii) verifiers always reveal to provers the information on their next moves, and (iii) the number of interactions between provers and verifiers is bounded.
Elsevier
Showing the best result for this search. See all results