本記事は、親記事である"量子振幅増幅と量子数値積分"のために、その前提知識であるグローバーのアルゴリズムの解説を行うものです。このアルゴリズムは、量子重ね合わせを利用して、古典アルゴリズムには不可能な速度で無秩序データリストから特定のものを検索することが可能です。このアルゴリズムの基幹をなすのが、オラクル演算子です。この演算子は、目的とする状態にのみπの位相を与える演算子です。まず、全ビットが0の初期状態を用意し、最初のn量子ビットにWalsh-Hadamardゲートを、アンシラビットにXゲートを掛けます。その後、オラクルを掛けます。それは図1のようにn量子ビットを制御ビットにアンシラビットを標的ビットに解となる状態のみを反転させるn+1ビット制御NOTゲートを作用させることで実現できます。
図1 オラクル演算子の量子回路。〇と●は検索したい状態によって変わります。
その後、グローバーの反復演算子を作用させます。これは $ G=H_n(2\mid 0 \rangle \langle 0 \mid - I)H_n$となる演算子です。解となる状態を$\mid \Psi_0 \rangle$、そうでない状態を$\mid \Psi_1 \rangle$とすると、これによって状態は$sin\sqrt{2^n}/2\mid \Psi_0 \rangle + cos\sqrt{2^n}/2\mid \Psi_1 \rangle$と変換されます。従って、オラクルとグローバーの反復演算子の積を$\pi \sqrt{2^n}/4$回かけることで目的の状態の存在確率が1になります。
図2 グローバーのアルゴリズムにおける量子回路。
主な流れは以下のようになります。
1, 作業用量子ビットn個、アンシラ量子ビット1個を用意します。
2, 操作$A=H_{n}X_{n+1}$をn+1量子ビットからなる初期状態$\mid 0 \rangle_{n+1}$に作用させます。
3, 解となる状態のみの位相を逆転させるオラクル演算子$O$、$G=H_n(2\mid 0 \rangle_n \langle 0 \mid _n - I)H_n$の積$OG$を$\pi \sqrt{2^n}/4$回作用させます。
4, 観測します。
実際に6量子ビットからなる状態$\mid 101000 \rangle$を検索する際の存在確率の変化を図3に示します。均等な存在確率が目的とする状態に$OG$を掛けるほどに偏り、最終的にそれのみになるのがわかります。これは量子振幅増幅アルゴリズムのもとになっています。
図3 $OG$を作用させた回数と存在確率の関係。