6533b7cffe1ef96bd1258ca0

RESEARCH PRODUCT

Probabilities to Accept Languages by Quantum Finite Automata

Andris AmbainisArnolds ĶIkustsRichard F. BonnerRusins Freivalds

subject

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

description

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.

yearjournalcountryeditionlanguage
1999-01-01
https://doi.org/10.1007/3-540-48686-0_17