We study 1-way quantum finite automata (QFAs). First, we comparethem with their classical counterparts. We show that, if an automaton isrequired to give the correct answer with a large probability (greaterthan 7/9), then any 1-way QFAs can be simulated by a 1-way reversibleautomaton. However, quantum automata giving the correct answer withsmaller probabilities are more powerful than reversible automata.Second, we show that 1-way QFAs can be very space-efficient. Weconstruct a 1-way QFA that is exponentially smaller than any equivalentclassical (even randomized) finite automaton. We think that thisconstruction may be useful for design of other space-efficient quantumalgorithms. Third, we consider several generalizations of 1-way QFAs.Here, our goal is to find a model which is more powerful than 1-way QFAskeeping the quantum part as simple as possible
展开▼
