グローバーの探索

今日は、誰もが本当に困っている問題を扱おう。並べ替えられていない大量の候補の中から、条件に合う1個を探す問題だ。
たとえば、電話帳から「この電話番号の持ち主は誰か」を調べるとする。電話帳は名前の五十音順に並んでいて、番号順には並んでいない。この場合、どう探すことになるかな。

その推論はふつうのコンピュータについては完全に正しくて、証明もされている。N 件の総当たり探索は、N に比例する回数がどうしても必要だ。
ところが1996年、ロブ・グローバーが量子コンピュータでこれを 約√N 回に減らす方法を見つけた。N が100万なら、100万回ではなく約1000回。1兆件なら100万回だ。

いい問いの立て方だ。答えはこうだよ。私たちは当たりが「どれ」かを知らないが、当たりを「見分ける箱」は持っている。電話番号の例なら、名前を1つ渡されて「この人の番号は探している番号か」と聞けば、はい・いいえは即答できる。これがオラクルだ。前回と同じ道具だね。

聞いても、箱には答えられないんだ。箱が持っているのは照合の手順であって、答えの一覧表ではない。電話帳の例で言えば、1枚の板に電話帳と探す番号を刻みつけたようなものだね。渡された名前の欄と探す番号を1桁ずつ照らし合わせる手順が、板の上に回路として書いてある。錠前と同じだよ。錠前は、差し込まれた鍵が正しいかどうかを一瞬で完璧に判定する。でも錠前に「正しい鍵の形を教えて」と頼むことはできない。暗号の鍵探しも、パズルの答え探しも同じ形をしている――1つの候補を確かめるのは一瞬、でも正しい1つを見つけるのは大仕事。世の中の難問の多くがこのタイプで、グローバーの方法はこの「照合の箱」だけを頼りに、たった2手を何度も繰り返す。

その通りの準備でいい。ここから2手を繰り返す。
【第1手・反転】オラクルに聞いて、当たりの行の矢印だけを正反対の向きにする。前回の位相キックバックがそのまま使える。当たりを名指しできなくても、重ね合わせの全候補を箱に通せば、照合に引っかかった行だけが反転する――照合の手順さえあれば、この操作は組めるんだ。

教えられないんだ、2つの理由で。第一に、箱のどこにも「当たりは◯番」と計算する部分がない。反転は行ごとに「この行は照合に引っかかったか」で起きるだけで、当たりの番号はどこにも書き出されない。教えたくても、教える中身を箱は持っていないんだ。第二に、きみが言った通り、印は向き（位相）で書かれている――いわば見えないインクだ。測っても確率に現れない以上、外から読む方法がない。
できる唯一のことは、この見えない印を、干渉で長さという見える形に変換していくこと――それだけなんだ。

その通り。候補2個なら H 1発で印を読み切れる。その N 行版を担うのが第2手――ただし N が大きいと1発では変換しきれず、少しずつ進めることになる。
【第2手・平均のまわりの折り返し】全部の矢印の平均を計算して、それを鏡だと思って、すべての矢印を平均の反対側へ折り返す。式で書けば、新しい値＝2×平均 − 元の値。平均より下にあったものは同じだけ上に、上にあったものは同じだけ下に移る。

それが、そう単純でもないんだ。反転と折り返しは、どちらも矢印を回す操作だからね。回転を続ければ、いつか行き過ぎて戻ってくる――回しすぎると、育てた矢印がまた縮んでいく。ブランコを押すタイミングを間違えると勢いが落ちるのと同じだよ。ふつうの探索なら探し続けて損をすることはないのだから、ここも「探索」ではなく干渉である証拠だね。
ちょうどよい回数は決まっていて、約 0.785×√N 回――円周率πの4分の1が0.785だ。N が100万なら785回くらい。この回数で当たりの確率がほぼ1になり、それを過ぎると下がり始める。

いい問いだ、そこが「同時に計算」の正確な中身だよ。
まず、箱に入る物は1つだけだ。量子ビットのかたまりが1つあって、その状態が1つ。N行の表というのは、そのたった1つの状態を書き下した姿であって、N個の物が詰まっているわけではない。
そしてゲートは、表全体への書き換え規則だ。行が4行でも100万行でも適用は1回で、かかる時間は照合の手順の複雑さぶんだけ。候補の数には比例しない。
では、なぜ1回通しただけで行ごとに違う結果が出るのか。量子力学の法則が線形だからだ――「AとBを足したものを入れたら、Aの結果とBの結果を足したものが出てくる」という性質だよ。箱は行1つずつを正しく照合するように組んであるだけで、あとは法則のほうが重ね合わせを勝手に分配してくれる。こちらは場合分けを1度もしていないのに、全行ぶんの照合が済んでいる――手品の種はここなんだ。

それは、やりたくてもできないんだ。ゲートの実体は、装置に電磁波のパルスを一瞬当てることだったね。パルスは波全体に一度に働く。矢印の表というのは、たった1つの波の成分帳簿だから、成分を1つずつ触るボタンは、装置のどこにも存在しない。「1行ずつ順番に」は、この機械にはそもそもできない芸当なんだよ。

いい比較だね。決定的な違いは設備の数だ。CPU並列は候補の数だけ物理的な機械が要る。候補が2¹²⁸個なら、宇宙の原子を全部使ってもコアが足りない。量子の側は、候補が2倍になっても量子ビットが1個増えるだけ。なぜそんなに安いのか――候補たちが「N台の機械」ではなく、1つの波のN個の成分だからだ。さっき言ったとおり、成分ごとの処理を装置がやっているのではなく、法則のほうが勝手に分配してくれるからね。

そこを見逃さないのが大事だ。まず素朴なやり方から言うと、問い合わせのたびに電話帳ぜんぶを回路に焼き直すことになる。100万件なら100万件ぶんの部品だ。しかもグローバーは√N回くり返すから、合計するとふつうの総当たりより高くつく。「量子コンピュータはデータベース検索が速い」がほとんど神話だと言われるのは、この計算のせいなんだよ。
そこで考えられているのが QRAM（量子RAM）という装置だ。RAMというのは、ふつうのコンピュータの記憶装置のこと。「何番地の中身をくれ」と言うと、その番地に入れてある中身を出してくれる箱だと思えばいい。その量子版を作ろう、という構想だね。

そこに気づけば十分だ。手間は消えたのではなく、装置の側へ移った。装置ぜんたいが100万個規模になるんだ。しかも、それだけの部品を誤りから守り続けられるのか――QRAMが実際に作れるのかどうかは、いまも決着がついていない。あくまで構想の段階だよ。

その見立てで合っている。ただ、分かれ目がひとつある。一度きりの調べものなら、並べ替えは損になる。全部の行を読んで並べ替える手間のほうが、端から順に照合していく手間より大きいからね。逆に何度も引くなら、並べ替えたほうが勝つ。手間を最初に一度だけ払えば、あとは1件あたり20回で済む。これはふつうのコンピュータの完勝で、世の中のデータベースはみなこれをやっている。
ついでに、量子の側の言い分も言っておこう。オラクルは、行どうしを比べない。1つの行を渡されて「照合に引っかかるか」を答えるだけだ。並べ替えというのは行どうしの大小を使う作業だから、この箱にとって並び順は最初から関係がない。だから重ね合わせにそのまま通せるんだ。

そうだ。だから本当の出番は、並べ替えるべき一覧表が、そもそも存在しない問題のほうなんだ。
たとえば、暗号の鍵を総当たりで探す問題だ。候補は2¹²⁸通り。これは「並べ替えるのが大変」なのではなく、書き出すことすらできない。宇宙にそれだけの紙がない。索引も辞書も作りようがなくて、できるのは鍵を1つ決めて錠前に差してみることだけだ。
こういう問題は世の中にいくらでもある。「条件を満たす組み合わせを探せ」「この計算結果になる入力を探せ」――どれも候補を一覧にできず、1つずつ試すしかない。その世界で N 回が √N 回になる。グローバーの居場所は、電話帳ではなくこちら側なんだよ。

そこが、電話帳と鍵探しの決定的な違いだよ。板に刻むものが、まるで違うんだ。
電話帳で刻んでいたのはデータそのものだった。「0番は鈴木さんで、番号はこれこれ」「1番は大谷さんで――」と、1件ずつが互いに無関係だから、規則で書けない。100万件なら100万件ぶんを刻むしかない。
ところが鍵探しで刻むのは手順のほうだ。「渡された鍵で暗号文を復号して、意味のある文になるか調べよ」――これは計算の手順を1つ書けば済む。候補が2⁶⁴通りだろうと2¹²⁸通りだろうと、板の大きさはまったく変わらない。暗号1つぶんの回路で足りるんだ。

そういうことだ。候補の数を決めるのは、装置の大きさではなく量子ビットの本数。だから宇宙の原子より多い候補を、手のひらに載るチップが相手にできる。
逆に言えば、電話帳がやっかいだったのは、量子のせいではない。規則で書けないデータを、まるごと持ち込もうとしたからだ。世の中で本当に困っている大きな問題は、たいてい候補を規則で作れて、正しいかどうかも計算で判定できる。表を持たなくていいから、板は小さいままでいられるんだよ。

そのまとめで十分だよ。効き目の大きさも、数字で押さえておこう。グローバーの加速は、回数が N から √N になる2次加速で、指数加速ではない。鍵の候補が2¹²⁸通りある暗号なら、総当たりが2⁶⁴回くらいに減る――深刻ではあるけれど、鍵の長さを2倍にすれば元の強さに戻る。しかもこの2次加速が限界であることも証明されていてね。構造のない総当たり探索を、量子コンピュータでこれ以上速くする方法は存在しない。何も構造のない問題にも効く汎用の道具だからこそ、効き目もそこまでにとどまるんだ。
――では、本当に世界を揺るがしたアルゴリズムはどれか。それは、問題に隠れている構造を干渉で暴き出すものだ。次のステージでは、インターネットの安全を支えている暗号を根こそぎにする力を持つ、ショアのアルゴリズムを扱うよ。