Efficient two-way quantum finite state automata

Abstract

The discovery of quantum algorithms which are exponentially more e fficient than the best known classical algorithms for similar tasks has spurred researchers to compare the relative powers of the classical and quantum versions of several computational models to better understand the causes and limitations of the apparent power of quantum computing. One model for which such comparative analyses have led to interesting results is that of nite automata. Among the various types of quantum nite automata, we concentrate on the strongest family, namely, two{way quantum nite automata (2qfa's). Kondacs and Watrous proved that 2qfa's are more powerful than their classical counterparts by describing a method for constructing 2qfa's that recognize the non{regular language Leq = fanbnj n > 0g for any given error bound > 0. Machines built according to this method have O(( 1 )2) states, and they halt after O(( 1 )jwj) steps, where w is the input string. In this thesis, we examine ways of reducing the dependence of these cost functions on the desired error bound. We present more e cient constructions to recognize the same language. One of our methods produces machines which halt in O(jwj) time (i.e. the running time does not depend on the error bound) and which have O(( 1 ) 2 c ) states for any given constant c > 1. Other methods, yielding machines whose state complexities are polylogarithmic in 1 , and which halt in O(log( 1 )jwj) time, are also presented..