International Symposium on Mesoscopic Superconductivity and Spintronics (MS+S)
QUANTUM PUSHDOWN AUTOMATA THAT CAN DETERMINISTICALLY SOLVE A CERTAIN PROBLEM
Yumiko Murakami, Masaki Nakanishi, Shigeru Yamashita, Katsumasa Watanabe
Abstract
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.