1-way quantum finite automata: strengths, weaknesses and generalizations
| dc.creator | Ambainis, A. | |
| dc.creator | Freivalds, R. | |
| dc.date | 1998-02-25 | |
| dc.date | 1998-09-30 | |
| dc.date.accessioned | 2026-07-07T06:14:49Z | |
| dc.date.available | 2026-07-07T06:14:49Z | |
| dc.description | We study 1-way quantum finite automata (QFAs). First, we compare them with their classical counterparts. We show that, if an automaton is required to give the correct answer with a large probability (over 0.98), then the power of 1-way QFAs is equal to the power of 1-way reversible automata. However, quantum automata giving the correct answer with smaller probabilities are more powerful than reversible automata. Second, we show that 1-way QFAs can be very space-efficient. Namely, we construct a 1-way QFA which is exponentially smaller than any equivalent classical (even randomized) finite automaton. This construction may be useful for design of other space-efficient quantum algorithms. Third, we consider several generalizations of 1-way QFAs. Here, our goal is to find a model which is more powerful than 1-way QFAs keeping the quantum part as simple as possible. | |
| dc.description | 23 pages LaTeX, 1 figure, to appear at FOCS'98 | |
| dc.identifier | https://arxiv.org/abs/quant-ph/9802062 | |
| dc.identifier | http://arxiv.org/abs/quant-ph/9802062 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/93607 | |
| dc.subject | Quantum Physics | |
| dc.subject | Computational Complexity | |
| dc.title | 1-way quantum finite automata: strengths, weaknesses and generalizations | |
| dc.type | text |