|
|||||
|
|
Algebraic Results on Quantum Automata |
|
| Authors: | Andris Ambainis Martin Beaudry Marats Golovkins Arnolds Kikusts Mark Mercer Denis Therien |
| Affiliation: | (1) Department of Combinatorics and Optimization and Institute for Quantum Computing, University of Waterloo, 200 University Avenue West, Waterloo, Ontario, N2L 2T2, Canada;(2) Departement d'Informatique 2500, Boul. Universite, Sherbrooke, Quebec, J1K 2R1, Canada;(3) Computer Science Division, University of California, Berkeley, CA 94720, USA;(4) Institute of Mathematics and Computer Science, University of Latvia, Raina bulv. 29, Riga, Latvia;(5) School of Computer Science, McGill University, 3480 rue University, Montreal, Quebec, H3A 2A7, Canada |
| Abstract: | We use tools from the algebraic theory of automata to investigate the class of languages recognized by two models of Quantum Finite Automata (QFA): Brodsky and Pippenger's end-decisive model (which we call BPQFA) and a new QFA model (which we call LQFA) whose definition is motivated by implementations of quantum computers using nucleo-magnetic resonance (NMR). In particular, we are interested in LQFA since NMR was used to construct the most powerful physical quantum machine to date. We give a complete characterization of the languages recognized by LQFA and by Boolean combinations of BPQFA. It is a surprising consequence of our results that LQFA and Boolean combinations of BPQFA are equivalent in language recognition power. |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |