On a Computing Model Based on Optical Interference
M. V. Panduranga Rao
IISc-CSA-TR-2005-10
(July 2005) Available formats: [ps] [ps.gz]
Filed on July 17, 2005
Updated on July 21, 2006
We propose a computing model, the Two-Way Optical Interference Automata (2OIA),
that makes use of the phenomenon of optical interference.
We introduce this model to investigate the increase in power, in terms of language recognition, of a classicalDeterministic Finite Automaton (DFA) when endowed with the facility of optical interference.
The question is in the spirit of Two-Way Finite Automata With Quantum and Classical States (2QCFA)
[A. Ambainis and J. Watrous, Two-way Finite Automata With Quantum and Classical States, Theoretical Computer Science, 287 (1), 299-311, (2002)] wherein the classical DFA
is augmented with a quantum component of constant size.
We test the power of 2OIA against the languages mentioned in the above paper.
We give efficient 2OIA algorithms to recognize languages for which
2QCFA machines have been shown to exist, as well as languages whose status vis-a-vis 2QCFA
has been posed as open questions. Finally we show the existence of a language that
cannot be recognized by any 2OIA but can be recognized by a Turing machine in
polynomial time.
Please bookmark this technical report as http://aditya.csa.iisc.ernet.in/TR/2005/10/.Problems ? Contact techrep@csa.iisc.ernet.in
[Updated at 2009-10-22T06:42Z]