Loading article…
コンピュータサイエンスと量子物理学において、チャーチ＝チューリング＝ドイチュ原理（CTD原理）は、 1985年にデイヴィッド・ドイチュによって定式化されたチャーチ＝チューリングのテーゼのより強力な物理的な形です。[1]この原理は、汎用的なコンピューティングデバイスがあらゆる物理プロセスをシミュレートできることを述べています。
歴史
この原理は、有限の機械とプロセスに関して、1985年にドイチュによって述べられました。彼は、実数の概念を使用する古典物理学は、計算可能な実数しか表現できないチューリングマシンではシミュレートできないことに気づきました。ドイチュは、量子物理学の法則があらゆる物理プロセスを完全に記述できる と仮定して、量子コンピューターは実際にCTD原理に従う可能性があると提案しました。
古典的コンピュータに関するこの論文の初期のバージョンは、アラン・チューリングの友人であり学生であったロビン・ガンディによって1980年に発表されました。 [2] [3]
同様の論文は、アレクセイ・キタエフ、マイケル・J・ラーセン、ジェンハン・ワンと共著したトポロジカル量子コンピューティングの初期のレビューでマイケル・フリードマンによって述べられており、フリードマン・チャーチ・チューリングの論文として知られている。[4]
「量子力学（または量子場理論）のリソースを古典的な計算に追加するすべての「合理的な」計算モデルは、（効率的に）相互シミュレーション可能なクラスを生み出します。つまり、計算の量子理論は 1 つだけです。」
この論文は、計算可能性ではなく計算の複雑さに関する主張であるという点で、チャーチ＝チューリング＝ドイチュの論文とは異なります。
参照
注記
- ^ Nielsen, Michael (2004年4月16日). 「興味深い問題: チャーチ・チューリング・ドイツ原理」 . 2014年5月10日閲覧。
- ^ ガンディ、R. (1980)。チャーチのテーゼとメカニズムの原理。論理学と数学の基礎研究(101)、123–148
- ^ Kaznatcheev, Artem (2014). 「反証可能性とチャーチ＝チューリングのテーゼのガンディの変形」理論、進化、ゲームグループのブログ。2018年7月23日閲覧。
- ^ Freedman, Michael H.; Kitaev, Alexei; Larsen, Michael J.; Wang, Zhenghan (2002-09-20). 「トポロジカル量子計算」. arXiv : quant-ph/0101025 .
参考文献
- Deutsch, D. (1985). 「量子理論、チャーチ・チューリング原理、そして汎用量子コンピュータ」(PDF) . Proceedings of the Royal Society . 400 (1818): 97–117. Bibcode :1985RSPSA.400...97D. CiteSeerX 10.1.1.41.2382 . doi :10.1098/rspa.1985.0070. S2CID 1438116. 2016-03-09 に オリジナル(PDF)からアーカイブ。2011-08-17に取得。
さらに読む
- Deutsch, D. (1997)。「6: 普遍性と計算の限界」。The Fabric of Reality 。ニューヨーク: Allan Lane。ISBN 978-0-14-027541-4。
- Christopher G. Timpson 「量子コンピュータ：チャーチ＝チューリング仮説とチューリング原理」、Christof Teuscher、Douglas Hofstadter（編）Alan Turing：偉大な思想家の生涯と遺産、Springer、2004年、ISBN 3-540-20020-7、pp. 213–240
外部リンク
- Nielsen, Michael (2004-04-16). 「興味深い問題: チャーチ・チューリング・ドイチュ原理」