An Introduction to Quantum Complexity Theory (第6回『非平衡系の統計物理』シンポジウム)

スポンサーリンク

概要

• 論文の詳細を見る

• 1985年にD. Deutschは,いわゆる量子並列計算を行うことができるTuring機械として,量子Turing機械(QTMと略す)を導入した.その後,1994年にP. Shorが,QTMは多項式時間内に任意に小さな誤り確率で,整数を因数分解できることを示した.QTMに基づく計算量理論を量子計算量理論という.本論では,最初にQTMと,EQP,BQP,ZQP等の主要な量子計算量クラスの定義を述べる.次に,この分野ですでに知られている結果と,主要な未解決問題を紹介する.

• 物性研究刊行会の論文
• 1999-06-20

著者

• Nishino Tetsuro

  Department Of Communications And Systems Engineering The University Of Electro-communications

関連論文

• The Complexity of Threshold Circuits for Parity Functions
• A Relationship between the Number of Negations and the Circuit Size
• An Introduction to Quantum Complexity Theory (第6回『非平衡系の統計物理』シンポジウム)

スポンサーリンク