「世界初の実用量子コンピュータのデモが行われる」記事へのコメント

素朴な疑問

[fiercewinds (22740)]

量子コンピュータて、非決定性TMを実現できるのかな？

Re:素朴な疑問

[tyv (21837)]

非決定性TMって、決定性TMの二乗くらいの力しかないんじゃなかったでしたっけ？

--
Can you over the wall?

Re:素朴な疑問

[fiercewinds (22740)]

NPの定義って、「非決定性TMで多項式ステップで解ける問題の集合」だよ。

Pに対してどうか、つうのは判らないけど、NPに対しては劇的な効果がある（はず）。

Re:素朴な疑問

[tyv (21837)]

いいかげんに勉強したので、知識がごちゃごちゃになってるみたいです

＃先生にばれたら殺されるなぁ

--
Can you over the wall?

Re:素朴な疑問

[sakamoto (8009)]

BQP(確率限定量子コンピュータ多項式時間計算可能問題のクラス)とNP の包含関係はまだわかってませんが、予想としては真の包含関係があるとは思われてないようです。

で、N 個のパターンマッチングから最適解を探す場合、決定性のコンピュータではO(N)時間、非決定性のコンピュータでは O(log N)時間ですが、量子コンピュータではO(√N)時間のアルゴリズムが知られています。

--
-- 哀れな日本人専用(sorry Japanese only) --

Re:素朴な疑問

[Anonymous Coward]

もっと素朴な疑問として、デモ機が量子コンピュータであることはどうやって確かめるのかな？
問題の複雑さと計算時間だけで証明できるの？

Re:素朴な疑問

[Artane. (1042)]

そこは、不確定性原理を量子コンピュータの実在の虚実にも適用すれば無問題(´▽`)…アレ？

Re:素朴な疑問

[Anonymous Coward]

「シュレーディンガーの猫」と同じで、蓋を開けてみるまでわかりません。