グローバーのアルゴリズム

本記事は、親記事である"量子振幅増幅と量子数値積分"のために、その前提知識であるグローバーのアルゴリズムの解説を行うものです。このアルゴリズムは、量子重ね合わせを利用して、古典アルゴリズムには不可能な速度で無秩序データリストから特定のものを検索することが可能です。このアルゴリズムの基幹をなすのが、オラクル演算子です。この演算子は、目的とする状態にのみπの位相を与える演算子です。まず、全ビットが0の初期状態を用意し、最初のn量子ビットにWalsh-Hadamardゲートを、アンシラビットにXゲートを掛けます。その後、オラクルを掛けます。それは図1のようにn量子ビットを制御ビットにアンシラビットを標的ビットに解となる状態のみを反転させるn+1ビット制御NOTゲートを作用させることで実現できます。


図1 オラクル演算子の量子回路。〇と●は検索したい状態によって変わります。


その後、グローバーの反復演算子を作用させます。これはG=Hn(200I)HnG=H_n(2\mid 0 \rangle \langle 0 \mid - I)H_n となる演算子です。解となる状態をΨ0\mid \Psi_0 \rangle 、そうでない状態をΨ1\mid \Psi_1 \rangle とすると、これによって状態はsin2n/2Ψ0+cos2n/2Ψ1sin\sqrt{2^n}/2\mid \Psi_0 \rangle + cos\sqrt{2^n}/2\mid \Psi_1 \rangle と変換されます。従って、オラクルとグローバーの反復演算子の積をπ2n/4\pi \sqrt{2^n}/4 回かけることで目的の状態の存在確率が1になります。

図2 グローバーのアルゴリズムにおける量子回路。


主な流れは以下のようになります。


1, 作業用量子ビットn個、アンシラ量子ビット1個を用意します。

2, 操作A=HnXn+1A=H_{n}X_{n+1} をn+1量子ビットからなる初期状態0n+1\mid 0 \rangle_{n+1} に作用させます。

3, 解となる状態のみの位相を逆転させるオラクル演算子OOG=Hn(20n n0I)HnG=H_n(2\mid 0 \rangle_n ~_n\langle 0 \mid - I)H_n の積OGOGπ2n/4\pi \sqrt{2^n}/4 回作用させます。

4, 観測します。


実際に6量子ビットからなる状態001000\mid 001000 \rangle を検索する際の存在確率の変化を図3に示します。均等な存在確率が目的とする状態にOGOG を掛けるほどに偏り、最終的にそれのみになるのがわかります。このアルゴリズムは検索時間をO(2n)O(\sqrt{2^n}) に抑えることが可能であるため、第2世代以降の量子計算機において最も優れた検索アルゴリズムになると期待されています。このグローバーのアルゴリズムが量子振幅増幅アルゴリズムのもとになっています。



図3 OGOG を作用させた回数と存在確率の関係。

Hikaru Wakaura
個人研究者の若浦 光です。量子アルゴリズムの実装結果や論文の紹介などを載せていきます。 mail: hikaruwakaura@gmail.com
Comments
Hikaru Wakaura
個人研究者の若浦 光です。量子アルゴリズムの実装結果や論文の紹介などを載せていきます。 mail: hikaruwakaura@gmail.com
Related posts

blueqat Inc.

Shibuya Scramble Square 39F 2-24-12, Shibuya, Shibuya-ku, Tokyo
Contact: info@blueqat.com