1-way quantum finite automata: strengths, weaknesses and generalizations

Details 1-way quantum finite automata: strengths, weaknesses and generalizations 1-way quantum finite automata: strengths, weaknesses and generalizations

1998-02-25

arxiv.org/abs/quant-ph/9802062v3

Physics

Quantum Physics

23 pages LaTeX, 1 figure, to appear at FOCS'98

Scientific paper

We study 1-way quantum finite automata (QFAs). First, we compare them with their classical counterparts. We show that, if an automaton is required to give the correct answer with a large probability (over 0.98), then the power of 1-way QFAs is equal to the power of 1-way reversible automata. However, quantum automata giving the correct answer with smaller probabilities are more powerful than reversible automata. Second, we show that 1-way QFAs can be very space-efficient. Namely, we construct a 1-way QFA which is exponentially smaller than any equivalent classical (even randomized) finite automaton. This construction may be useful for design of other space-efficient quantum algorithms. Third, we consider several generalizations of 1-way QFAs. Here, our goal is to find a model which is more powerful than 1-way QFAs keeping the quantum part as simple as possible.

Affiliated with

Also associated with

No associations

Rating

1-way quantum finite automata: strengths, weaknesses and generalizations 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 1-way quantum finite automata: strengths, weaknesses and generalizations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and 1-way quantum finite automata: strengths, weaknesses and generalizations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-283227