Efficient probability amplification in two-way quantum finite automata

In classical computation, one only needs to sequence identical copies of a given probabilistic automaton with one-sided error p<1 to run on the same input in order to obtain a two-way machine with error bound ϵ. For two-way quantum finite automata (2qfa’s), this straightforward approach does not yield efficient results; the number of machine copies required to reduce the error to ϵ can be as high as . In their celebrated proof that 2qfa’s can recognize the non-regular language , Kondacs and Watrous use a different probability amplification method, which yields machines with states, and with runtime , where w is the input string. In this paper, we examine significantly more efficient techniques of probability amplification. One of our methods produces machines which decide L in O(|w|) time (i.e. the running time does not depend on the error bound) and which have states for any given constant c>1. Other methods, yielding machines whose state complexities are polylogarithmic in , including one which halts in time, are also presented.