Physics – Quantum Physics
Scientific paper
2007-01-20
Physics
Quantum Physics
10 pages, Preliminary version appears in the Proceedings of ACiD-2005, Texts in Algorithmics series of KCL publications, pp. 1
Scientific paper
Quantum finite automata derive their strength by exploiting interference in complex valued probability amplitudes. Of particular interest is the 2-way model of Ambainis and Watrous that has both quantum and classical states (2QCFA) [A. Ambainis and J. Watrous, Two-way finite automata with quantum and classical state, Theoretical Computer Science, 287(1), pp. 299-311, 2002], since it combines the advantage of the power of interference in a constant-sized quantum system with a 2-way head. This paper is a step towards finding the least powerful model which is purely classical and can mimic the dynamics of quantum phase. We consider weighted automata with the Cortes-Mohri definition of language recognition [C. Cortes and M. Mohri, Context-Free Recognition with Weighted Automata, Grammars 3(2/3), pp. 133-150, 2000] as a candidate model for simulating 2QCFA. Given any 2QCFA that (i) uses the accept-reject-continue observable, (ii) recognizes a language with one-sided error and (iii) the entries of whose unitary matrices are algebraic complex numbers, we show a method of constructing a weighted automaton over $\mathbb{C}$ that simulates it efficiently.
Panduranga Rao M. V.
Vinay V.
No associations
LandOfFree
Quantum Finite Automata and Weighted 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 Quantum Finite Automata and Weighted Automata, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum Finite Automata and Weighted Automata will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-652003