Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1007/978-3-642-13523-1_14 | UC |
Keywords | Field | DocType |
mm-quantum finite automaton,quantum automaton,s. aaronson,probabilistic finite automaton,postselection finite quantum automaton,quantum finite automaton,quantum computation,probabilistic automaton,classical computing device,quantum computing device,regular language,finite automata,quantum computer,computational complexity | Discrete mathematics,Quantum finite automata,Automata theory,Nondeterministic finite automaton,Nested word,Deterministic finite automaton,Theoretical computer science,DFA minimization,Mathematics,Quantum cellular automaton,ω-automaton | Conference |
Volume | ISSN | ISBN |
6079 | 0302-9743 | 3-642-13522-6 |
Citations | PageRank | References |
1 | 0.35 | 18 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Oksana Scegulnaja-Dubrovska | 1 | 1 | 1.03 |
| Lelde Lace | 2 | 35 | 11.36 |
| Rūsiņš Freivalds | 3 | 249 | 20.26 |