Quantum Pushdown Automata

Details Quantum Pushdown Automata Quantum Pushdown Automata

2001-02-09

arxiv.org/abs/quant-ph/0102054v1

LNCS, 2000, vol. 1963, pp. 336-346

Physics

Quantum Physics

Conference SOFSEM 2000, extended version of the paper

Scientific paper

Quantum finite automata, as well as quantum pushdown automata (QPA) were first introduced by C. Moore and J. P. Crutchfield. In this paper we introduce the notion of QPA in a non-equivalent way, including unitarity criteria, by using the definition of quantum finite automata of Kondacs and Watrous. It is established that the unitarity criteria of QPA are not equivalent to the corresponding unitarity criteria of quantum Turing machines. We show that QPA can recognize every regular language. Finally we present some simple languages recognized by QPA, not recognizable by deterministic pushdown automata.

Affiliated with

Also associated with

No associations

Rating

Quantum Pushdown Automata does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Quantum Pushdown Automata, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum Pushdown Automata will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-613558