Quantum versus deterministic counter automata

AbstractThis paper focuses on quantum analogues of various models of counter automata, and almost completely proves the relation between the classes of languages recognizable by bounded error quantum ones and classical deterministic ones in every model of counter automata. It is proved that (i) there are languages that can be recognized by two-way quantum one-counter automata with bounded error, but cannot be recognized by two-way deterministic one-counter automata, (ii) under some reasonable restriction, every language that can be recognized by two-way deterministic one-counter automata can also be recognized by two-way reversible one-counter automata (and hence by bounded error two-way quantum one-counter automata), and (iii) for any fixed k, quantum ones and deterministic ones are incomparable in one-way k-counter automata