QUANTUM PUSHDOWN AUTOMATA THAT CAN DETERMINISTICALLY SOLVE A CERTAIN PROBLEM
Yumiko Murakami, Masaki Nakanishi, Shigeru Yamashita +1 more
Golovkins introduced the quantum counterpart of pushdown automata (quantum pushdown automata, QPAs), including unitary criteria, in 2000. Golovkins showed that QPAs can recognize some non-context-free languages probabilistically, which indicates that QPAs might be more powerful than the classical counterpart in a bounded error scenario , namely than probabilistic pushdown automata. In this paper, we show that QPAs might be more powerful even in a deterministic case . That is, we show that there exists a QPA that deterministically solves a certain problem which might not be solved by deterministic pushdown automata.
International Symposium on Mesoscopic Superconductivity and Spintronics (MS+S)•Aug 1, 2005•0 citations