Quantum finite automata and weighted automata
M. V. Panduranga Rao and V. Vinay

IISc-CSA-TR-2004-9
(October 2004)

Available formats: [ps] [ps.gz]

Filed on October 1, 2004
Updated on July 17, 2005


Two way quantum finite automata derive their strength by exploiting complex valued probability amplitudes and interference therein.
This paper is a step towards finding the least powerful model which is purely classical and can capture the dynamics of quantum phase.
We give a classical simulation of a restriction of the 2-way Finite Automata with Quantum and Classical States (2QCFA) of Ambainis and
Watrous [A. Ambainis, J. Watrous, Two-way finite automata with quantum and classical state, Theoretical Computer Science, 287(1): 299-311 (2002)]
using weighted automata over the real semiring.


Please bookmark this technical report as http://aditya.csa.iisc.ernet.in/TR/2004/9/.

Problems ? Contact techrep@csa.iisc.ernet.in
[Updated at 2009-10-22T06:42Z]