6533b7d0fe1ef96bd125abea

RESEARCH PRODUCT

Algebraic Results on Quantum Automata

Andris AmbainisArnolds ĶIkustsDenis ThérienMartin BeaudryMark MercerMarats Golovkins

subject

AlgebraSurface (mathematics)Class (set theory)Pure mathematicsAlgebraic theoryQuantum machineQuantum finite automataAlgebraic numberComputer Science::Formal Languages and Automata TheoryQuantum computerMathematicsAutomaton

description

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.

yearjournalcountryeditionlanguage
2004-01-01
https://doi.org/10.1007/978-3-540-24749-4_9