量子コンピュータとの比較
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/03/29 08:54 UTC 版)
「非決定性チューリングマシン」の記事における「量子コンピュータとの比較」の解説
量子コンピュータが NTM であるということをよく言われるが、これは間違っている。多項式時間の量子コンピュータの能力は多項式時間の NTM よりも低いと考えられている。つまり、これらのモデルについて、一方で解けるが、もう一方では解けないという問題が存在する。NTM で解けて量子コンピュータで解けないと予想される問題の例としてNP完全問題がある。
※この「量子コンピュータとの比較」の解説は、「非決定性チューリングマシン」の解説の一部です。
「量子コンピュータとの比較」を含む「非決定性チューリングマシン」の記事については、「非決定性チューリングマシン」の概要を参照ください。
- 量子コンピュータとの比較のページへのリンク