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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Corresponding authors
Rights and permissions
About this article
Cite this article
Ambainis, A., Beaudry, M., Golovkins, M. et al. Algebraic Results on Quantum Automata. Theory Comput Syst 39, 165–188 (2006). https://doi.org/10.1007/s00224-005-1263-x
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00224-005-1263-x