専門家である松本さん@gejikeiji による量子アルゴリズムに関するツイートまとめ

最近の量子アルゴリズム研究に関する動向。
15
根来誠 QuEL @makoto_ne56

少しでも量子コンピューター研究の現状を伝えたいと思っているのですが、私がここでいくら吠えても説得力はないでしょう。Nature誌の記事を読んで頂ければ少し納得頂けるのではないかと思います↓ Quantum computer quest nature.com/news/physics-q…

2015-01-05 21:45:54
QmQ @gejiqmq

上のツイートで引かれた解説でもそうなんですが、Grover searchをデータベースサーチの為といのは誤解で、古典的な確率的アルゴリズムの加速に用いる。適応範囲は極めて広く、余程の事情がない限り適応できるといっていい。加速の度合いは平方根程度ではあるけど。

2015-01-06 23:56:24
QmQ @gejiqmq

新しいアルゴリズムの開発が待たれるのはその通りなのだけれども、素因数分解しかない、とかいうのはかなり事実に反する。pellの方程式もあるし、可換隠れ部分群は全部いける。いたいのは、非可換隠れ部分群が思ったよりダメだったことか。

2015-01-06 23:59:03
QmQ @gejiqmq

今は兎に角アイデアが尽き果ててる感じ。そもそもpeter shorが前世紀の内にアルゴリズムに興味なくしたのは結構痛かったか。量子酔歩もはかばかしくなく。。。。ただ、1990年代後半の量子アルゴリズムはshorとgroverだけじゃない、活発で実りの多い時期でした。

2015-01-07 00:05:05
QmQ @gejiqmq

人的には、Kitaev, Brassard, Hoyer, Tapp, Moscaあたり。Brassardは量子鍵配布でも有名ですが。まず、Grover検索が成功確率の増幅である事が理解され、さらにスピードの調節ができるように一般化されたこと。これで応用がぐっと広がった。

2015-01-07 00:13:04
QmQ @gejiqmq

応用先は古典及び量子アルゴリズムの成功確率の増幅。これで例えば離散対数はexactに多項式時間になった。shorのオリジナルでは、計算時間は高い確率で多項式なだけ。また、古典的確率的アルゴリズムの加速は極めて広範に行えるようになった。

2015-01-07 00:17:52
QmQ @gejiqmq

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

2015-01-07 00:21:59
QmQ @gejiqmq

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

2015-01-07 00:29:16
QmQ @gejiqmq

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

2015-01-07 00:36:48
QmQ @gejiqmq

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

2015-01-07 00:42:40
QmQ @gejiqmq

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

2015-01-07 00:46:03
QmQ @gejiqmq

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

2015-01-07 00:50:05
QmQ @gejiqmq

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

2015-01-07 00:52:24
QmQ @gejiqmq

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

2015-01-07 00:58:14
QmQ @gejiqmq

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

2015-01-07 01:01:36
QmQ @gejiqmq

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

2015-01-07 01:09:05