0000000000072869

AUTHOR

Arnolds ĶIkusts

showing 3 related works from this author

Probabilities to Accept Languages by Quantum Finite Automata

1999

We construct a hierarchy of regular languages such that the current language in the hierarchy can be accepted by 1-way quantum finite automata with a probability smaller than the corresponding probability for the preceding language in the hierarchy. These probabilities converge to 1/2.

Discrete mathematicsTheoretical computer scienceNested wordFinite-state machineHierarchy (mathematics)Computer scienceComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)Turing machinesymbols.namesakeNonlinear Sciences::Exactly Solvable and Integrable SystemsRegular languageProbabilistic automatonAnalytical hierarchysymbolsComputer Science::Programming LanguagesQuantum finite automataQuantum algorithmNondeterministic finite automaton
researchProduct

Algebraic Results on Quantum Automata

2004

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 th…

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

Regulāru valodu pazīšana ar galīgu kvantu automātu

2007

Fizika materiālzinātne matemātika un statistikaMatemātikaDiscrete mathematics and mathematical informaticsDiskrētā matemātika un matemātiskā informātika
researchProduct