目的
Qiskit textbook の教材の 1 つにグローバー探索アルゴリズムというものがある。これは FTQC（誤り耐性付き量子コンピュタ）向けのアルゴリズムなので、現在の NISQ デバイス上では芳しい結果は得られないようだが、シミュレータと実機の両方で動作を見てみたので記事にしたい。
NISQ では厳しいこともあるのか、書籍やオンラインの教材では 2 量子ビットのことが多いが、今回は 3 量子ビット（シミュレータであれば 5 量子ビットまで確認した）で解が 2 つの場合を扱ってみた。
グローバー探索アルゴリズムとは？
まともな説明はリンク先の教材或はIBM Quantumで学ぶ量子コンピュータの pp.160-165 に譲ることにして、ここでは簡単な言及にとどめる。
「ある関数 f(x, y),\ x,y \in \{0, 1\} が与えられていて、正解の x,y に対しては 1 を、それ以外では -1 を返す」ということだけが分かっている場合に解をすべて求めたいという問題があるとする。この問題を効率的に求める量子アルゴリズムが「グローバー探索アルゴリズム」である。
量子版に書き直すと
上記の問題設定を量子版の記述に直すと、「オラクルと呼ばれるブラックボックス U が与えられていて、量子状態 \ket{\psi} に作用させる時、状態が正解であれば U \ket{\psi} = - \ket{\psi} となり、それ意外であれば U \ket{\psi} = \ket{\psi} となる」ことが分かっている場合に解をすべて求めたい、となる。
2 つの解を持つケースに挑む
可視化の容易さのために 2 量子ビットのケースを考える。計算基底としては \ket{00}, \ket{01}, \ket{10}, \ket{11} が存在しており、以下の図のようにこれらは互いに直交している。
ここで今回は解が \ket{01} と \ket{11} であるとする。
\ket{s} = \frac{1}{2} \sum_{x=0}^3 \ket{x} = \frac{1}{2} (\ket{00} + \ket{01} + \ket{10} + \ket{11}) という状態を考えた時にこれにオラクル U を作用させると、
\begin{align*}
U \ket{s} &= \frac{1}{2} (\ket{00} - \ket{01} + \ket{10} - \ket{11}) \\
&= \frac{1}{\sqrt{2}} \frac{\ket{00} + \ket{10}}{\sqrt{2}} - \frac{1}{\sqrt{2}} \frac{\ket{01} + \ket{11}}{\sqrt{2}} \\
& = \frac{1}{\sqrt{2}} \ket{✗} - \frac{1}{\sqrt{2}} \ket{✓}
\end{align*}
となる。ここで、\ket{✗} = \frac{1}{\sqrt{2}} (\ket{00} + \ket{10}) および \ket{✓} = \frac{1}{\sqrt{2}} (\ket{01} + \ket{11}) である。これらはそれぞれ不正解な状態たちがなす equiprobable（等確率で起こり得る）な重ね合わせ状態と、正解の状態たちがなす equiprobable な重ね合わせ状態である。
なお、\ket{s} = \frac{1}{\sqrt{2}} \ket{✗} + \frac{1}{\sqrt{2}} \ket{✓} と書けるので、オラクル U は \ket{s} の正解状態部分の位相を反転させる作用をしているのである。
アルゴリズムを適用する舞台の可視化
この \ket{✗} と \ket{✓} そして \ket{s} を図示すると以下のようになる。ここで平面として描いたものは不正解の状態 \ket{00} と \ket{10} が張る平面である。その上に重ね合わせ状態 \ket{✗} が乗っており、正解の重ね合わせ状態 \ket{✓} が直交している形である。\theta は \ket{s} と \ket{✗} がなす角度であり、量子ビットが n 個、正解の状態が n_{sol} 個とすると、\sin \theta = \sqrt{\frac{n_{sol}}{2^n}} となる。
\ket{s} = \frac{1}{\sqrt{2}} \ket{✗} + \frac{1}{\sqrt{2}} \ket{✓} であるので、初期状態で \ket{s} は \ket{✗} と \ket{✓} の張る平面内にあり、また既に見たように U \ket{s} もこの平面内にある。
グローバーのアルゴリズムの標準的な手続きによると、1 回の反復で 2\theta だけ \ket{✓} に近づくので、(\frac{\pi}{2} - \theta) / (2\theta) 回程度反復すると状態は \ket{✓} に最大限近づく。
その状態になったところで測定をすると概ね \ket{✓} = \frac{1}{\sqrt{2}} (\ket{01} + \ket{11}) に近い状態が観測される。実際には厳密には一致しないはずなので、正解の状態が等確率で重ね合わさったものと、真の \ket{✓} からの誤差として他の状態の重ね合わせも “僅か” ながら検出される。
とは言え、FTQC 向けのアルゴリズムなので実際に実機でアルゴリズムを実行すると、3 量子ビットの場合でもなかなか苦しく、理論上は “僅か” でも、現実的には “僅か” ではなく、以下のような感じになる。
このケースでは \ket{101} と \ket{111} を解としてオラクルを作成したのだが、測定すると \ket{011} も解のように見えていてなかなか際どい状態である。こうなってしまう理由としては、実機向けにトランスパイルした量子回路の深さが 60 を越えており、ゲートの作用ごとにエラーが蓄積するためである。
オマケ（5 量子ビットの場合）
最後に 5 量子ビットの場合のシミュレータの結果と実機の結果を見て終わりにしよう。今回は \ket{10101} と \ket{11111} を解とする。
反復回数は 3 であり、シミュレータの場合以下のように非常に理想的な形で解が求まっている。
なお、シミュレータ向けの状態でもトランスパイル後の回路の深さは 20 もあり、実機では絶望的である。一応調べたところ、857 もあった！
無意味を承知の上で実機上で実験すると、以下のように実質ランダムノイズを得る。
これがたまに聞く「回路の深さは数十くらいが限界。それ以上だと “計算できない”」の意味である。
まとめ
解の個数が複数の場合、アルゴリズムが難しくなるのではないだろうか？と思うかもしれないが、幸いにして複数の解は重ね合わせ状態として 1 つの状態で表されるので、何ら難しくなることはないことが分かった。
一方、アルゴリズムとしてはとても面白いが NISQ ではほとんど実用性がなく相当簡単な問題でないと解けない、つまり古典コンピュータによる総当たりで十分な状態であることが分かった。
他のケースを含め Jupyter Notebook の形で GitHub のこちらにコンテンツを用意しているので、興味があれば試して見られるのも良いと思う。
Discussion