Quantum computer quest とその後まとめ

QmQ @gejiqmq

それから、時間的前後関係は判定が難しいけど、Kitaev, Moska, Brassardらが独立に可換隠れ部分群問題を定式化し、そのアルゴリズムを作った。これで素因数分解、離散対数、周期発見、多項式がシフトで写り合うか、などのアルゴリズムが統一的に理解された。

QmQ @gejiqmq

また、これらのアルゴリズムはユニタリ変換の推定問題のアルゴリズムとしても理解でき、Metrologyの理論的解析とも繋がってくる。ここまではかなり順調と言っていい。

QmQ @gejiqmq

問題はここから先。可換隠れ部分群が出来たので次は非可換隠れ部分群でしょ、となり、質問計算量としては多項式時間でできることも示された。ところが、実用的な非可換群で計算量ではなかなか多項式にならない。唯一の成功例がHallgrenのPellの方程式。

QmQ @gejiqmq

当初試みられたグラフ同型については、出来なさそう、という証拠がドンドンつみあがった。新たなアルゴリズムの仕組みとして期待された量子酔歩もイマイチうまくいっていない。元々のアイデアは、古典のMCMC(メトロポリス法みたいなもの)の量子化。プロセスの漸近分布を利用する。

QmQ @gejiqmq

その収束時間を量子で早くしたかったが、殆どの場合は平方根程度の、つまりGrover程度にしか早くならないことがわかってしまった。勿論、それでも速くなるので、役に立たないといったら言い過ぎではある。また、適用範囲が広いのもよい。ただ、量子計算機の個々のゲートの速度は、

QmQ @gejiqmq

すくなくとも当面の間は、遅い。ビットの転送も遅い。だから、アルゴリズムで相当稼がなといけないだろう。で、定常分布をつかうのではなく、目的地点への到達速度で勝負するアイデアが、実はかなりはやくから、あった。でも、人工的な設定はともかく、実用的なアルゴリズムには結実していない。

QmQ @gejiqmq

実用的な、と断ったのは、実用的でないやや人工的な問題でよければ指数加速の例があるので。この方向でのNoGo theoremはまだないと思うけれど、賢い連中が寄ってたかってこれでは、凡人には手が出ない。

QmQ @gejiqmq

自分が計算機科学にひっかかるような量子計算の研究に首をつっっこんだのは21世紀にはいってから。この時点で、アルゴリズムで指数的な加速を出そうなんて研究に手を出すのは、すでに勇気の要る状態だった。やっぱり、非可換隠れ部分群、あれはつまづきの元だったか。結構な代数の知識が要るので、

QmQ @gejiqmq

その難しげな雰囲気が研究者をアルゴリズム研究から遠ざけた嫌いはあるのではないか。このような状況でしっかり結果をだしたSean Hallgrenは本当に凄いけれど、例外的な成功例だった。多くの駿才が色んな結果をだしたけれど、中々実用的な問題につながらずに今にいたっている。

QmQ @gejiqmq

じゃあ、どうすればいいのか。新しい仕組みを思いつくけばいいが、当面は地道に今までのアイデアの拡張とか、ちょいとひいねってとか、やるしかないのかも。いつかは良い結果が出ると信じて。新規参入も促さないといけないけど、ここで大きな問題は、良いレビューがないことか。誰か書いて欲しい。。。

Kodack @iKodack

非可換隠れ部分群の問題の指数関数的高速化の成功例があるの知らなかった

Kodack @iKodack

非可換への拡張は経験上不可能でその証明も難しいみたいな状況だと思ってたんだけど、一個でも拡張できるなら普通にもっと増えて良さそうな気がする

シータ @Perfect_Insider

@gejikeiji すみません、小耳にはさんだことがあるJones 多項式の量子計算はこの流れとは独立なものなんでしょうか？

QmQ @gejiqmq

@Perfect_Insider jones polynomialの近似は独立した流れです。量子計算のある数学的表現でtopological quantum computationというものがあり、量子ゲートの操作が位相幾何学的な操作に対応するという表現で、見た目は全然ちがう

QmQ @gejiqmq

@Perfect_Insider けれど、通常の量子計算と等価であることが証明されているものです。この表現でみると、jones polynomialの近似ができることが見て取れます。kitaevやfreedmanが指摘し、それを通常のモデルに書き直したのがaharanov

Kodack @iKodack

昨日のTLを受けて、やっぱ直観的に量子情報でもっといろいろ高速化されてよさそうなのに経験上応用があんまり見つかってないのは、実体か公理みたいなとらえ方のどちらかに需要と折り合わせが悪い理由があるんだろうね、みたいな話をルームメイトの人とした

Kodack @iKodack

あと、現実的なスループットとかも考慮すると、やっぱ計算時間の高速化というよりかは過程に物理的な理由からくる制約を持ってきた方が古典に対する優位性をアピールしやすいんじゃないかとか

Kodack @iKodack

例えば量子測定は量子状態生成とかも見込んだトータルの効率という意味ではまだまだあんまよくないけど、細胞とかの物質に当てられる光子の数がリミットされたときに時間度外視で現実的な意味を持つ（多分）みたいに、

Kodack @iKodack

グローバーの探索も探索が早くなるというより、何らかの理由でオラクルが呼び出せる回数が決まっているとか、呼び出すたびにオラクルを利用するコストが指数関数的に上がるみたいな制約が入らざるをえないみたいなそういう需要を見つけるか、既存の需要をそういった問題に変換してしまう方が

Kodack @iKodack

実用的な用途を見つけるという意味ではより間口が広くなりそう的な

Kodack @iKodack

あと個人的にやっぱりアニールを用いた推定がどうしても少なからず微妙に見えるのは現実的に探索としてはデータ格納時にデータに構造を持たせて 使用を効率化するみたいな流れは現状見つかっている量子アルゴリズムとは 折り合いが悪く見えるからなので、

Kodack @iKodack

なんかそういう未整序であらざるを得ないみたいな需要があるのかとか、あるいは未整序以外での量子向きのデータ構造が存在する見込みがどの程度ありそうなのかみたいなのを知りたいなぁと思ったのであった

Kodack @iKodack

D-WAVEの実験とかで解析的にたどり着きにくいけれどもまだ見つかっていない量子的に加速されやすい問題の構造とかが見つかると良いですね

Keisuke Fujii @fgksk

@gejikeiji @Perfect_Insider 横から失礼します。Jones多項式の近似アルゴリズムの場合は、BQP完全なので、素因数分解等よりも古典計算機でできてしまう能性は低いという点で良いとおもいますが、一方でJones多項式のあの値を代入したときにあの精度で（続

Keisuke Fujii @fgksk

@gejikeiji @Perfect_Insider 近似できるということがどれくらい凄いのか、というのがいまいちピンと来ない気がします（もちろん凄いと思うのですが）。Jones多項式の厳密な計算は#Pになりますが、あのスケールでの多項式近似するというのは別問題なので。