|
| related topics |
| {algorithm, log, probability} |
| {let, theorem, proof} |
| {time, systems, information} |
| {cos, sin, state} |
| {theory, mechanics, state} |
| {group, space, representation} |
| {measurement, state, measurements} |
| {states, state, optimal} |
| {cavity, atom, atoms} |
|
Quantum finite multitape automata
Andris Ambainis, Richard Bonner, Rusins Freivalds, Marats Golovkins, Marek Karpinski
abstract: Quantum finite automata were introduced by C.Moore, J.P. Crutchfield, and by
A.Kondacs and J.Watrous. This notion is not a generalization of the
deterministic finite automata. Moreover, it was proved that not all regular
languages can be recognized by quantum finite automata. A.Ambainis and
R.Freivalds proved that for some languages quantum finite automata may be
exponentially more concise rather than both deterministic and probabilistic
finite automata. In this paper we introduce the notion of quantum finite
multitape automata and prove that there is a language recognized by a quantum
finite automaton but not by a deterministic or probabilistic finite automata.
This is the first result on a problem which can be solved by a quantum computer
but not by a deterministic or probabilistic computer. Additionally we discover
unexpected probabilistic automata recognizing complicated languages.
- oai_identifier:
- oai:arXiv.org:quant-ph/9905026
- categories:
- quant-ph cs.CC
- comments:
- 14 pages, LaTeX
- arxiv_id:
- quant-ph/9905026
- created:
- 1999-05-07
Full article ▸
|
|
| related documents |
| 0505007v3 |
| 0511272v1 |
| 9706003v4 |
| 0201152v1 |
| 0302022v1 |
| 0207131v1 |
| 0011052v2 |
| 9903071v1 |
| 0010034v1 |
| 0206089v2 |
| 0306042v1 |
| 0210141v2 |
| 0504067v3 |
| 0106152v1 |
| 0109038v1 |
| 0008095v3 |
| 0304131v1 |
| 0403140v2 |
| 0010021v1 |
| 0010057v1 |
| 0609220v1 |
| 0410042v1 |
| 9907020v2 |
| 0607148v3 |
| 0609166v1 |
|