Design and simulation of two-way quantum finite automata

Abstract

In this thesis, we review classical finite state automata, (FSAs and TWAs) and 2- way quantum finite state automata (2QFAs). We examine fundamental theorems and their proofs. We develop a software simulator of quantum finite state automata. We introduce the simulator and by the help of the simulator, we examine some non-regular languages like {0n1n n > 0} (type 2) and {0n1n2n n > 0} (type 1). We also propose a new technique to enhance the language recognition probability of 2QFAs. This method may allow some languages to be recognized with bounded error, if we have an algorithm for the unbounded error version. A sample construction for such a case is inspected in detail. Using this technique, we enhance the complexity of a 2QFA which originally recognize string s with error probability of 1/2, beyond a well known 2QFA in the literature for the same language.