Quantum versus Classical Pushdown Automata in Exact Computation

• Murakami Yumiko

  Nara Institute of Science and Technology

• Nakanishi Masaki

  Nara Institute of Science and Technology

• Yamashita Shigeru

  Nara Institute of Science and Technology

• Watanabe Katsumasa

  Nara Institute of Science and Technology

Abstract

Even though quantum computation is useful for solving certain problems, classical computation is more powerful in some cases. Thus, it is significant to compare the abilities of quantum computation and its classical counterpart, based on such a simple computation model as automata. In this paper we focus on the quantum pushdown automata which were defined by Golovkins in 2000, who showed that the class of languages recognized by quantum pushdown automata properly contains the class of languages recognized by finite automata. However, no one knows the entire relationship between the recognitive abilities of quantum and classical pushdown automata. As a part, we show a proposition that quantum pushdown automata can deterministically solve a certain problem that cannot be solved by any deterministic pushdown automata.

Journal

• IPSJ Digital Courier

  IPSJ Digital Courier 1 426-435, 2005

  Information Processing Society of Japan

Keywords

• General Economics, Econometrics and Finance

Details

• CRID: 1390001205224125696
• NII Article ID: 130000022371
• DOI: 10.2197/ipsjdc.1.426
• ISSN: 13497456
• Web Site: http://www.jstage.jst.go.jp/article/ipsjdc/1/0/1_0_426/_pdf
• Text Lang: en
• Data Source:
  • JaLC
  • Crossref
  • CiNii Articles
• Abstract License Flag: Disallowed