ノート:量子コンピュータ
出典: フリー百科事典『ウィキペディア（Wikipedia）』
この記事は一度削除されています。削除に関する議論はWikipedia:削除依頼/量子コンピュータをご覧ください。
「量子コンピュータはデジタルであるのか」という基本的な疑問がある。さて、量子コンピュータの研究は始まったばかりであり、皆は凄いものが出来ると考えているが、「量子コンピュータはデジタルであるのか」という疑問がどうしても残る。 DNAコンピュータは明らかにデジタルであり、2004年の段階でも既に計算が出来る。量子コンピュータはまだ計算が出来ないのである。 どちらに投資するほうが得かを考えると、私ならば「DNAコンピュータ」である。
- 第一に,物理学の立場に立つか計算機科学の立場に立つかによって異なりますが,理論計算機科学の立場から極端な言い方をすれば,実際に計算させるデバイスが存在するかどうかは理論屋にとっての問題ではありません. たとえば,非決定性Turing機械が実現可能であると考える人はほとんどいないと思われますが, その概念から定義されるNP完全性の概念は非常に有用です.
- 第二に,量子計算で扱う量子状態は有限個の状態を扱っており countable という意味でデジタル計算です.また確率振幅も効率的に計算可能であることが求められます[BV97].
- 第三に量子計算は n qubits で 2^n 個の重ね合わせ状態が作れますが, DNA 計算は n 通りの探索をするのに n 個の原子や分子を必要とするので， 事実上6.0 × 10^23 (1 mol) より大きな探索空間をとることができないという原理的な問題を抱えているように思います.70.174.150.78 2006年7月4日 (火) 06:42 (UTC)
- [BV97] Ethan Bernstein and Umesh Vazirani, " Quantum Complexity Theory", SIAM Journal on Computing, Vol.26, No.5, pp.1411--1473, Oct 1997.
計算量的安全性のほうにも書きましたが…。 gloverで秘密鍵暗号が何でもかんでも解けるという話はにわかには信じがたいです。 gloverのアルゴリズム提案以後も「量子コンピュータでも解けない事を目指して作られた暗号方式」は幾つも提案されてますし…。 最近の成果なのでしょうか。 あと、公開鍵暗号方式は（公開鍵をも秘密にする事で）かならず秘密鍵暗号方式としても 用いる事ができるので、 秘密鍵暗号が全て解けるのなら公開鍵暗号方式も全て解けるはずですが…。 その辺の事情をご教授願えれば幸いです。
- gloverアルゴリズムはO(root(n))で解くアルゴリズムだったのでは・・・・。O(log(n))とO(root(n))では効率が違うので・・・・。その辺に何か画期的な改良があったのでしょうか、是非知りたいです。 Sina 2004年7月18日 (日) 10:40 (UTC)
- 通りすがりのものですが、私もgloverのアルゴリズムはO(root(n))だったと思います。もちろんあれ以来何らかの革新があったのかも知れないですが、それならばgloverではなくなんらかの違う名前のアルゴリズムになっているはずなのでは？
-
- コメントありがとうございます（気が付くのが遅れました）。少し古い記事（5年前）ですけど、GroverアルゴリズムはO(root(n))であり、かつ最適であることが示されている、との記述もあったのでこの部分は修正したいと思います。ただ、秘密鍵暗号は一般の探索問題とは条件が違うので、さらに効率よく（多項式時間とかで）解けるのかもしれず、よくわかりません。詳しい方のコメントを頂けると幸いです・・・。Sina 2004年9月26日 (日) 11:20 (UTC)
Shorのアルゴリズムの解説内に素因数分解が準指数時間とありますが、 たしか2004年の春頃にインドの研究者グループによって多項式時間のアルゴリズムが 発見されていると思います。 文献詳細をすっかり忘れてしまったので修正できませんでしたが、どなたかご存知ありませんか。 Zon++ 2006年6月28日 (水) 14:27 (UTC)
- 素因数分解ではなく素数判定(自然数 n は素数か? (Yes/No))のことではないでしょうか？もしそうであれば素数判定の項に説明があります.すでにこの話はご存じでしたらすいません.70.174.150.78 2006年7月4日 (火) 06:42 (UTC)
-
- 回答ありがとうございます。ご指摘の通り、素数判定と混同していました。--Zon++ 2006年12月18日 (月) 15:12 (UTC)
