前回は、量子ビットが「0と1の両方を含んだ状態＝重ね合わせ状態」を取ることができ、その状態を物理的にどう作っているかを見た。今回は、その構造が計算にどう使えるかを、Groverのアルゴリズムという例を通して見る。
問題の設定：構造のない探索
ここでは、典型的な探索問題を考える。N個の候補のうち、正解が1つだけあるとする。どれが正解かは、関数 f(x) を通して判定できるようになっており、f(x) = 1 のときだけそのxが正解である。それ以外のxに対しては f(x) = 0 である。f(x) の中身はわからないが、与えられたxに対してf(x)を計算する手段（ブラックボックスとしての関数呼び出し）はあるという前提で進める。
このような問題では、xのどれが正解かを知る手がかりがない。f(x)の値を実際に調べてみるまで、どれが1になるかわからない。候補xには特に法則性も構造もなく、順に調べていくしかない。こうした問題を「構造のない探索（unstructured search）」と呼ぶ。
この探索に対して、量子アルゴリズムはどのような構造を持っているかを具体的に見るため、以下では候補数N = 16、すなわちxが4ビット（0000～1111）で表されるような例を使って進めていく。
Groverのアルゴリズムの基本構造
量子アルゴリズムのGrover探索では、まず4つの量子ビットを重ね合わせ状態に準備する。Hadamardゲートによって、すべての構成（0000～1111）を一度に含む状態が作られる。この状態は、すべてのxに対して同時にf(x)を問い合わせる準備が整っている、という意味で、構造的に非常に効率がいい。
この重ね合わせ状態に対して、「f(x)=1となる構成だけに印をつける」操作が行われる。印をつけるとは、具体的には、その構成に対応する成分の振幅の符号を -1 に反転させることを意味する。この符号反転は、「クエリ」と呼ばれる操作で、重ね合わせ全体に対して一度で適用される。
このあと、もう一つの操作（振幅反転、いわゆる拡散演算）が続く。これは、振幅全体の平均に対して対象となる成分を反転させる操作で、印のついた構成の振幅だけを強調する効果がある。
この2つの操作（印付け＋振幅反転）を1ステップとし、それを複数回繰り返すことで、正解の構成の振幅だけが高まり、最終的に観測によってそれが高確率で得られるようになる。Groverのアルゴリズムでは、この繰り返し回数が、Nではなくその平方根 √N に比例することが知られている。
Grover回路の実装：oracleの構造
Groverの中心となるのは、f(x)=1 のときだけ特別な変化を与える「oracle」と呼ばれる部分である。実装では、量子回路の入力として4つの量子ビットが用意され、それに加えて補助ビットが1つ用意される。補助ビットは、主系の状態が正解xに一致したときにだけ変化するように制御されている。たとえば、すべての量子ビットが特定の値を取っているときに補助ビットに反転が起きるよう、複数の制御条件を満たすと作用するゲートを構成する。こうした多条件の制御は、たとえば前回紹介したHadamardゲートのような基本的な操作と同様に、いくつかのシンプルなゲートを組み合わせて実現できる。ここで言うゲートとは、量子ビットの状態を操作するための基礎的な処理単位であり、古典回路における論理ゲートに似た役割を果たす。
たとえば、正解が1001のときには、xが1001を示す構成でのみ補助ビットの状態を反転させるような制御構造を作る。補助ビットをうまく初期化しておけば、この反転は、主系の該当する構成だけに符号をかける効果として現れる。さらに、この補助ビットを特別な状態（たとえば |0⟩と |1⟩ の差で構成された状態）に初期化しておくと、回路上の操作がその成分にだけ符号をかける仕組みになる。これにより、主となる構成に-1の印をつけることができる。これが「印をつける」ことの物理的な実装である。
この操作は、すべてのxに対して並列に行われる。重ね合わせ状態のそれぞれの成分に対して、「そのxが正解であるか」を問う構成を持っていることで、正解にのみ符号反転が生じる。印がついたからといって、答えが観測可能になるわけではなく、このあとに続く振幅反転によって、正解の構成の振幅を強調していく必要がある。
古典との比較：構造の違いが、計算量の違いになる
古典的にも、同様に「f(x)に1回アクセスすること」を“1クエリ”と数える。候補xを順番に試すだけなら、平均してN/2、最悪でN回のクエリが必要になる。
これに対してGroverでは、印付けと振幅反転のセットを1ステップとし、それを√N回繰り返すだけで正解の振幅が十分に高まる。これは、各ステップによって状態が少しずつ「正解の方向」へと移動していく構造を持っているからである。構成全体を動かすような操作が可能であることが、探索に必要なクエリの数そのものを削減している。
つまり、古典では個別のxに順番にf(x)を適用するしかなく、構造のない探索ではO(N)の回数がかかる。それに対して量子では、全構成を一度に扱い、干渉によって正解の構成だけを浮かび上がらせることで、O(√N)の回数で済む。この差は、アルゴリズムの構造そのものの違いから生じている。
Groverは探索問題を解いているのか
Groverのアルゴリズムでは、「f(x)=1となる構成だけに印をつける」操作が行われる。これはすでに述べたように1クエリに相当し、重ね合わせ状態に含まれるそれぞれのxに対して、f(x)の値に応じて符号を反転させる。
ただしこの操作では、どのxが正解かを一つずつ調べたわけではないにもかかわらず、最初から正解の構成にだけ変化が起きる。もし古典でも、xを指定しないまま、正解の構成にだけ作用するような操作を許せば、探索などせずとも1クエリで正解を得ることができてしまう。
Groverでは、印をつけただけでは答えは得られず、その後に干渉操作を繰り返すことで、正解の構成が観測されやすくなるように変化していく。しかし、最初の1クエリの時点で、すでに正解の構成だけが他と区別されている。これは、正解を一つずつ試して判定するという探索の前提とは明らかに構造が異なる。
本当にこれは「探索」と言えるのか？それとも、すでに正解を持った構成を干渉によって浮かび上がらせているだけなのか？
量子計算の研究者スコット・アーロンソンは、Groverの構造についてこう述べている：
Groverのアルゴリズムは、巧みに探索して速くなるのではない。そもそも探索などしていないことで速くなっている。
まとめ
Groverのアルゴリズムは、重ね合わせ状態に含まれる構成の中から、正解にだけ印をつけ、その構成の振幅だけを繰り返し強調していくという仕組みを持っている。ここまでに見たように、その印は符号の反転というかたちで加えられ、それを平均に対する反転操作と組み合わせることで、干渉が生じ、正解構成の振幅が高まっていく。
ただし、振幅が変わったからといって、それだけで答えが得られるわけではない。印をつけた構成が「現れる」には、最終的に観測という操作が必要になる。そして観測とは、単に振幅を見ることではなく、量子状態を読み取る物理的な過程である。
次回はこの「観測とはなにか」、そしてその前段階である「干渉によって構成がどう変形されていくか」を丁寧に見ていく。Groverのアルゴリズムは、計算というよりも、「どの構成が観測されるか」を設計する操作として成り立っている。その仕組みを、具体的な振幅の変化や読み出しの実装も含めて追っていくことにする。
コメント