Algebraic Results on Quantum Automata

Autor:	Andris Ambainis, Arnolds Ķikusts, Denis Thérien, Martin Beaudry, Mark Mercer, Marats Golovkins
Rok vydání:	2004
Předmět:	Algebra Surface (mathematics) Class (set theory) Pure mathematics Algebraic theory Quantum machine Quantum finite automata Algebraic number Computer Science::Formal Languages and Automata Theory Quantum computer Mathematics Automaton
Zdroj:	Lecture Notes in Computer Science ISBN: 9783540212362 STACS
DOI:	10.1007/978-3-540-24749-4_9
Popis:	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, and a new QFA model whose definition is motivated by implementations of quantum computers using nucleo-magnetic resonance (NMR). In particular, we are interested in the new model since nucleo-magnetic resonance was used to construct the most powerful physical quantum machine to date. We give a complete characterization of the languages recognized by the new model and by Boolean combinations of the Brodsky-Pippenger model. Our results show a striking similarity in the class of languages recognized by the end-decisive QFAs and the new model, even though these machines are very different on the surface.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::4a166a899ad391071ce6c83943274d71 https://doi.org/10.1007/978-3-540-24749-4_9 Zobrazit plný text záznamu