Measure Once 1-way Quantum Finite Automata with Quantum Nondeterminism
M. V. Panduranga Rao, V. Vinay

IISc-CSA-TR-2005-9
(July 2005)

Available formats: (none)

Filed on July 17, 2005
Updated on February 4, 2007


We generalize the Measure-Once 1-way Quantum Finite Automata of Moore and
Crutchfield [C. Moore and J. P. Crutchfield, Quantum Automata and Quantum
Grammars, Theor. Comput. Sci., 237(1-2), 275-306, 2000] and Kondacs and Watrous
[A. Kondacs and J. Watrous, On the Power of Quantum Finite State Automata,
Proceedings IEEE FOCS, pp. 66-75, 1997] by introducing quantum nondeterminism.
We adapt a tiling complexity technique of Condon et al. [A. Condon, L. Hellerstein, S. Pottle and A. Wigderson, SIAM J. Comput., 27(3):739-762, 1998] to our model and show
that even with this additional power, it can only regular languages with bounded
error.


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

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