Quantum Finite Automata and Weighted Automata
Loading...
Date
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Description
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.
10 pages, Preliminary version appears in the Proceedings of ACiD-2005, Texts in Algorithmics series of KCL publications, pp. 123-134, 2005
10 pages, Preliminary version appears in the Proceedings of ACiD-2005, Texts in Algorithmics series of KCL publications, pp. 123-134, 2005