Quantum versus Classical Pushdown Automata in Exact Computation
スポンサーリンク
概要
- 論文の詳細を見る
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.
- 一般社団法人 情報処理学会の論文
著者
-
Murakami Yumiko
Nara Institute Of Science And Technology
-
Yamashita Shigeru
Nara Inst. Sci. And Technol. Ikoma‐shi Jpn
-
Nakanishi Masaki
Nara Inst. Sci. And Technol. Ikoma‐shi Jpn
-
Watanabe Katsumasa
Nara Institute of Science and Technology
関連論文
- Bit Length Optimization of Fractional Part on Floating to Fixed Point Conversion for High-Level Synthesis(Logic and High Synthesis)(VLSI Design and CAD Algorithms)
- Look Up Table Compaction Based on Folding of Logic Functions(Special Section on VLSI Design and CAD Algorithms)
- Robust Quantum Algorithms Computing OR with ε-Biased Oracles(Quantum Computing,Foundations of Computer Science)
- Bit-Length Optimization Method for High-Level Synthesis Based on Non-linear Programming Technique(System Level Design,VLSI Design and CAD Algorithms)
- Quantum Biased Oracles (特集:量子計算と量子情報)
- DDMF : An Efficient Decision Diagram Structure for Design Verification of Quantum Circuits under a Practical Restriction
- An Efficient and Effective Algorithm for Online Task Placement with I/O Communications in Partially Reconfigurable FPGAs(System Level Design,VLSI Design and CAD Algorithms)
- Quantum versus Classical Pushdown Automata in Exact Computation (特集:量子計算と量子情報)
- An efficient middle-level framework for quantum circuit simulation on multiple simulator platforms (コンピュータシステム)
- SPFD-Based Flexible Transformation of LUT-Based FPGA Circuits(VLSI Design Technology and CAD)
- Automatic Generation of Java-Based, Database-Independent Query API
- Automatic Generation of Java-Based, Database-Independent Query API
- Secure Processor Architecture for High-Speed Verification of Memory Integrity
- Automata with Quantum and Classical Resources (特集:量子計算と量子情報)
- Quantum Walks on the Line with Phase Parameters
- Quantum Biased Oracles
- Quantum versus Classical Pushdown Automata in Exact Computation
- Quantum Biased Oracles