Quantum computer quest とその後まとめ

Keisuke Fujii @fgksk

@gejikeiji @Perfect_Insider 拡張されたTutte多項式の結果においても多くのパラメータに対してBQP完全性がしめされていますが、物理的に親近感のあるPotts模型分配関数に帰着できる領域では、はやりBQP完全性はしめせず、

Keisuke Fujii @fgksk

@gejikeiji @Perfect_Insider 古典の既存のアルゴリズムに比べてどの程度凄いのかというのがいまいちピントきません。最近、アハラノフらの論文と同じノリで、イジング分配関数の多項式精度近似がBQP完全であることを、量子アルゴリズムを構成して示しましたが、

Keisuke Fujii @fgksk

@gejikeiji @Perfect_Insider やはり、物理的な結合定数の領域ではBQP完全性がしめせなかったので、MCMCとか既存の古典のフィールドで知られているものと比べてどれくらい優位かというのが、わからなかったです。

Keisuke Fujii @fgksk

@gejikeiji @Perfect_Insider 結局、Jones多項式、Tutte多項式、分配関数において量子アルゴリズムは、古典の有益な方法が知られていないパラメタ領域においてそれなりの評価ができるアルゴリズムであり、それが凄いのかはよくわからないが、BQP完全なので

Keisuke Fujii @fgksk

@gejikeiji @Perfect_Insider 古典ではできなさそうなことはできている。というのが現状のようなきがします。分配関数や、身近な物理量の近似評価をする量子アルゴリズムとかであれば探せば結構いろいろあるとおもいます。

Keisuke Fujii @fgksk

@gejikeiji @Perfect_Insider ただ、このタスクは量子でできるけど、古典ではどうだ？という上から目線で、古典の側からは、それを計算してどうなるの？的な感じになってしまうのではないかと思っています。例えば、複素パラメータのイジング分配関数とか。。。

Keisuke Fujii @fgksk

@gejikeiji @Perfect_Insider そうすると、本当に凄い（と古典の人にも思ってもらえる）量子アルゴリズム、というのは古典でよく研究されてて、多項式的には解けない問題を解け、ということになりやはり厳しい制約ですね。

Keisuke Fujii @fgksk

@gejikeiji @Perfect_Insider 量子で出来るタスク（解ける問題）を見つけ、いままでその問題は古典では問題視されなかったが、それが古典においても重要になる、といった局面が作り出せれば、良いと思うのですが。