Physics – Quantum Physics
Scientific paper
2012-02-13
Physics
Quantum Physics
23pages, comments and suggestions are welcome
Scientific paper
{\it Two-way quantum automata with quantum and classical states} (2QCFA) were introduced by Ambainis and Watrous in 2002. In this paper we study state succinctness of 2QCFA. For any fix $m\in {\mathbb{Z}}^+$, we show that i) there is a promise problem $A^{meq}$ which can be solved by 2QCFA in polynomial expected running time with one-sided error with constant numbers of quantum and classical states, whereas the sizes of the corresponding {\it deterministic finite automata} (DFA), {\it two-way nondeterministic finite automata} (2NFA) and polynomial expected running time {\it two-way probabilistic finite automata} (2PFA) are at least $2m+2$, $\sqrt{\log{m}}$ and $\sqrt[3]{(\log m)/b}$; ii) there exists a language $L^{mtwin}$ which can be recognized by 2QCFA in exponential expected running time with one-sided error with constant numbers of quantum and classical states, whereas the sizes of the corresponding DFA, 2NFA and polynomial expected running time 2PFA are at least $2^m$, $\sqrt{m}$ and $\sqrt[3]{m/b}$; where b is a constant number.
Li Lvzhou
Qiu Daowen
Zheng Shenggen
No associations
LandOfFree
State succinctness of two-way finite automata with quantum and classical states 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 State succinctness of two-way finite automata with quantum and classical states, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and State succinctness of two-way finite automata with quantum and classical states will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-681285