ToDo:
http://d.hatena.ne.jp/ytqwerty/20080207#p1
たぶんSATとか解けちゃうから量子計算機ぽくは無いかなぁというか もしもボックスがあったらに近いというか まぁ宇宙消失はそういう話だったと思うのでまぁいいのか。
(11:11)
| 前 | 2008年 2月 |
次 | ||||
| 日 | 月 | 火 | 水 | 木 | 金 | 土 |
| 1 | 2 | |||||
| 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 10 | 11 | 12 | 13 | 14 | 15 | 16 |
| 17 | 18 | 19 | 20 | 21 | 22 | 23 |
| 24 | 25 | 26 | 27 | 28 | 29 | |
全てリンクフリーです。 コード片は自由に使用していただいて構いません。 その他のものはGPL扱いであればあらゆる使用に関して文句は言いません。 なにかあれば下記メールアドレスへ。
えっ、量子計算機ってSAT解けないんですか！？
因数分解や検索ができるならSATもできるように思えるのですが……まるでわかってなくてごめんなさい。
QubitFuck(仮称)が全然違うのはその通りですごめんなさい。
解けるアルゴリズムは知られてないと思います。量子計算機は NP 完全な問題は解けないと考えられていて、因数分解や RSA は NP だが NP 完全ではないと考えられてるかと思います。
あと検索の方は計算量クラスは変えないかと。
そもそも、SATみたいなNP完全問題を量子多項式時間で解けることがわかったら、その結果だけでゲーデル賞とかチューリング賞ものですね。量子計算機を実現できるかどうか関係なく。
賞に関しては Peter Shor は素因数分解でなんちゃら賞(今見たらゲーデル賞ですか)とか取ってるようですね。