1208.6092 (Tomoyuki Yamakami)
Tomoyuki Yamakami
We examine characteristic features of reversible and quantum computations in the presence of supplementary external information, known as advice. In particular, we present a simple, algebraic characterization of languages recognized by one-way reversible finite automata augmented with deterministic advice. With a further elaborate argument, we prove a similar but slightly weaker result for bounded-error one-way quantum finite automata with advice. An immediate application of those properties leads to containments and separations among various language families that are further assisted by appropriate advice. We further demonstrate the power of randomized advice and quantum advice when given to one-way quantum finite automata.
View original:
http://arxiv.org/abs/1208.6092
No comments:
Post a Comment