One-way quantum finite automata together with classical states: Equivalence and Minimization

Details One-way quantum finite automata together with classical states: Equivalence and Minimization One-way quantum finite automata together with classical states: Equivalence and Minimization

2009-09-08

arxiv.org/abs/0909.1428v4

Physics

Quantum Physics

31 pages, 6 figures

Scientific paper

In this paper, we develop a new computing model of 1QFA, namely, {\it one-way quantum finite automata together with classical states} (1QFAC for short). In this model, a component of classical states is added, and the choice of unitary evolution of quantum states at each step is closely related to the current classical state. 1QFAC can accept all regular languages with no error, and in particular, 1QFAC can accept some languages with essentially less number of states than {\em deterministic finite automata} (DFA). The main technical results are as follows. (1) We prove that the set of languages accepted by 1QFAC with bounded error consists precisely of all regular languages. (2) We show that, for any prime number $m\geq 2$, there exists a regular language $L^0(m)$ whose minimal DFA needs $O(m)$ states and that can not be accepted by the 1QFA proposed by Moore and Crutchfield and by Kondacs and Watrous, but there exists 1QFAC accepting $L^0(m)$ with only constant classical states and $O(\log(m))$ quantum basis states. Analogous results for multi-letter automata are also established. (3) By a bilinearization technique we prove that any two 1QFAC ${\cal A}_1$ and ${\cal A}_2$ are equivalent if and only if they are $(k_{1}n_{1})^2+ (k_{2}n_{2})^2-1$-equivalent, and there exists a polynomial-time $O([(k_{1}n_{1})^2+ (k_{2}n_{2})^2]^4)$ algorithm for determining their equivalence, where $k_{1}$ and $k_{2}$ are the numbers of classical states of ${\cal A}_1$ and ${\cal A}_2$, as well as $n_{1}$ and $n_{2}$ are the numbers of quantum basis states of ${\cal A}_{1}$ and ${\cal A}_{2}$, respectively. (4) We show that the minimization problem of 1QFAC is in EXPSPACE. As a corollary of this result, we obtain that the minimization problem of MO-1QFA is also in EXPSPACE. Finally, we draw some conclusions and point out open problems to be addressed in the future.

Affiliated with

Also associated with

No associations

Rating

One-way quantum finite automata together with classical states: Equivalence and Minimization does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with One-way quantum finite automata together with classical states: Equivalence and Minimization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and One-way quantum finite automata together with classical states: Equivalence and Minimization will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-107933