量子コンピュータも巡回セールスマン問題は得意ではない？！

ネットの記事を見ていて、

「今の『量子に焼きなまし法』の量子コンピュータには巡回セールスマン問題が解けない。」

という記事がありました。

実際、解けるか解けないかで言ったら、解けるはずです。

でも、巡回セールスマン問題は本物の量子コンピュータでも得意ではないはずです。

従来型コンピュータよりも早く解けるかも疑問です。

最大の理由は、「巡回セールスマン問題には、ヒントが少なすぎる。」から。

私の理解が間違っているかもしれませんが、量子コンピュータは、たとえば、

「f(x,y)という方程式で、xとyが取りうる値を量子ビットで表現できる場合に、

　f(x,y)=Z　（Zはあらかじめ分かっている値、定数）

　となるx,yが存在するか？」

という問題が得意です。

従来のコンピュータは、

「総当たりで計算していって一致したら教えるね」

という感じなのに対して、

量子コンピュータは一回の計算で

「たぶんある。これくらいの可能性である。」

と答えてくれる感じです。

なので、巡回セールスマン問題でも、「この時間内に帰ってこれる経路はあるかな？」といった問題なら、有限の試行回数で解を比較的早く出せると思います。

但し、制約事項の複雑さによって得意不得意が出ると思います。

必要な量子ビット数も爆発的に増えますし・・・

まぁ実際には、アルゴリズムの考え方が全く違うのでこんなに簡単な話ではないのですが、ざっくり間違っていないと思います。

では(^^)／~~~~~