Quantum Pushdown Automata |
| |
| Authors: | Daowen Qiu |
| |
| Institution: | (1) Department of Computer Science and Technology, State Key Laboratory of Intelligent Technology and Systems, Tsinghua University, 100084 Beijing, People's Republic of China;(2) Department of Computer Science, Zhongshan University, Guangzhou, 510275, People's Republic of China |
| |
| Abstract: | Quantum automata are mathematical models for quantum computing. We analyze the existing quantum pushdown automata, propose a q quantum pushdown automata (qQPDA), and partially clarify their connections. We emphasize some advantages of our qQPDA over others. We demonstrate the equivalence between qQPDA and another QPDA. We indicate that qQPDA are at least as powerful as the QPDA of Moore and Crutchfield with accepting words by empty stack. We introduce the quantum languages accepted by qQPDA and prove that every  -q quantum context-free language is also an  -q quantum context-free language for any  (0, 1) and (0, 1). |
| |
| Keywords: | quantum computation Hilbert spaces pushdown automata |
| 本文献已被 SpringerLink 等数据库收录！ |
|
