TY - GEN
T1 - Postselection finite quantum automata
AU - Scegulnaja-Dubrovska, Oksana
AU - Lace, Lelde
AU - Freivalds, Rusiņš
PY - 2010
Y1 - 2010
N2 - Postselection for quantum computing devices was introduced by S.Aaronson[2] as an excitingly efficient tool to solve long standing problems of computational complexity related to classical computing devices only. This was a surprising usage of notions of quantum computation. We introduce Aaronson's type postselection in quantum finite automata. There are several nonequivalent definitions of quantumfinite automata. Nearly all of them recognize only regular languages but not all regular languages. We prove that PALINDROMES can be recognized by MM-quantum finite automata with postselection. At first we prove by a direct construction that the complement of this language can be recognized this way. This result distinguishes quantum automata from probabilistic automata because probabilistic finite automata with non-isolated cut-point 0 can recognize only regular languages but PALINDROMES is not a regular language.
AB - Postselection for quantum computing devices was introduced by S.Aaronson[2] as an excitingly efficient tool to solve long standing problems of computational complexity related to classical computing devices only. This was a surprising usage of notions of quantum computation. We introduce Aaronson's type postselection in quantum finite automata. There are several nonequivalent definitions of quantumfinite automata. Nearly all of them recognize only regular languages but not all regular languages. We prove that PALINDROMES can be recognized by MM-quantum finite automata with postselection. At first we prove by a direct construction that the complement of this language can be recognized this way. This result distinguishes quantum automata from probabilistic automata because probabilistic finite automata with non-isolated cut-point 0 can recognize only regular languages but PALINDROMES is not a regular language.
UR - https://www.scopus.com/pages/publications/79956313467
U2 - 10.1007/978-3-642-13523-1_14
DO - 10.1007/978-3-642-13523-1_14
M3 - Conference paper
AN - SCOPUS:79956313467
SN - 3642135226
SN - 9783642135224
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 115
EP - 126
BT - Unconventional Computation - 9th International Conference, UC 2010, Proceedings
T2 - 9th International Conference on Unconventional Computation, UC 2010
Y2 - 21 June 2010 through 25 June 2010
ER -