Physics – Quantum Physics
Scientific paper
2009-11-17
Physics
Quantum Physics
39 pages, 1 figure, some linguistic mistakes have been corrected, and Section 6 has been added
Scientific paper
In this paper we study a generalized model named one-way general quantum finite automata} (1gQFA), in which each symbol in the input alphabet induces a trace-preserving quantum operation, instead of a unitary transformation. Two different kinds of 1gQFA will be studied: measure-once one-way general quantum finite automata} (MO-1gQFA), and measure-many one-way general quantum finite automata (MM-1gQFA). We prove that MO-1gQFA recognize, with bounded error, precisely the set of all regular languages. We prove that MM-1gQFA also recognize only regular languages with bounded error. Thus, MM-1gQFA and MO-1gQFA have the same language recognition power, which is greatly different from the conventional case in which the number of times the measurement is performed in the computation generally affects the language recognition power of one-way QFA. Finally, we present a sufficient and necessary condition for two MM-1gQFA to be equivalent.
Li Lvjun
Li Lvzhou
Mateus Paulo
Qiu Daowen
Wu Lihua
No associations
LandOfFree
Characterizations of one-way general quantum finite automata 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 Characterizations of one-way general quantum finite automata, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Characterizations of one-way general quantum finite automata will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-650478