Quantum versus Classical Pushdown Automata in Exact Computation

• Item type: Journal(1)
• 公開日: 2005-10-15
• タイトル: Quantum versus Classical Pushdown Automata in Exact Computation
• タイトル / 言語: en
• タイトル: Quantum versus Classical Pushdown Automata in Exact Computation
• 言語: eng
• キーワード / 主題Scheme: Other
• キーワード / 主題: 特集：量子計算と量子情報
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• その他タイトル / その他のタイトル: 計算理論
• 著者所属: Nara Institute of Science and Technology
• 著者所属: Nara Institute of Science and Technology
• 著者所属: Nara Institute of Science and Technology
• 著者所属: Nara Institute of Science and Technology
• 著者所属(英): en
• 著者所属(英): Nara Institute of Science and Technology
• 著者所属(英): en
• 著者所属(英): Nara Institute of Science and Technology
• 著者所属(英): en
• 著者所属(英): Nara Institute of Science and Technology
• 著者所属(英): en
• 著者所属(英): Nara Institute of Science and Technology
• 著者名: Yumiko, Murakami; Masaki, Nakanishi; Shigeru, Yamashita; Katsumasa, Watanabe
• 著者名(英): Yumiko, Murakami; Masaki, Nakanishi; Shigeru, Yamashita; Katsumasa, Watanabe
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 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.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 46, 号 10, p. 2471-2480, 発行日 2005-10-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764