メインコンテンツへスキップ

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

このセクションでは、グローバーのアルゴリズムについて説明します。 まず位相クエリゲートとその構築方法について説明し、続いてグローバーのアルゴリズム自体の説明を行います。 最後に、このアルゴリズムが探索問題にどのように自然に応用されるかについて簡単に説明します。

位相クエリゲート​

グローバーのアルゴリズムは、位相クエリゲートと呼ばれる演算を使用します。 関数 ff に対して以前に説明した通常の方法で定義される通常のクエリゲート UfU_f とは対照的に、関数 ff に対する位相クエリゲートは次のように定義されます。

Zf∣x⟩=(−1)f(x)∣x⟩Z_f \vert x\rangle = (-1)^{f(x)} \vert x\rangle

これはすべての文字列 x∈Σnx\in\Sigma^n に対して成り立ちます。

演算 ZfZ_f は、次の図が示すように、1 つのクエリゲート UfU_f を使って実装できます。

A quantum circuit implementing a Z_f gate using one query gate together with the phase kickback phenomenon

この実装は位相キックバック現象を利用しており、∣−⟩\vert -\rangle 状態に初期化されたワークスペース量子ビットが 1 つ必要です。 この量子ビットは実装完了後も ∣−⟩\vert - \rangle 状態のままであり、（例えば後続の ZfZ_f ゲートを実装するために）再利用するか、単に破棄することができます。

演算 ZfZ_f に加えて、nn ビット OR 関数に対する位相クエリゲートも使用します。これは各文字列 x∈Σnx\in\Sigma^n に対して次のように定義されます。

OR(x)={0x=0n1x≠0n\mathrm{OR}(x) = \begin{cases} 0 & x = 0^n\\[0.5mm] 1 & x \neq 0^n \end{cases}

明示的に述べると、nn ビット OR 関数に対する位相クエリゲートは次のように動作します。

ZOR∣x⟩={∣x⟩x=0n−∣x⟩x≠0n.Z_{\mathrm{OR}} \vert x\rangle = \begin{cases} \vert x\rangle & x = 0^n \\[0.5mm] - \vert x\rangle & x \neq 0^n. \end{cases}

明確にしておきますと、これは ZORZ_{\mathrm{OR}} が標準基底状態に対して動作する方法です。任意の状態に対する挙動は、この式から線形性によって決定されます。

演算 ZORZ_{\mathrm{OR}} は、まず OR 関数のブール回路から始め、次に量子アルゴリズムの基礎レッスンで説明した手順を用いて UORU_{\mathrm{OR}} 演算（すなわち、nn ビット OR 関数の標準クエリゲート）を構築し、最後に上述の位相キックバック現象を用いて ZORZ_{\mathrm{OR}} 演算を構築することで、量子回路として実装できます。 演算 ZORZ_{\mathrm{OR}} は関数 ff に依存しないため、クエリゲートを持たない量子回路で実装できることに注目してください。

アルゴリズムの説明​

2 つの演算 ZfZ_f と ZORZ_{\mathrm{OR}} が揃ったので、グローバーのアルゴリズムを説明できます。

このアルゴリズムは数 tt を参照します。これはアルゴリズムが実行する反復の回数（したがって関数 ff へのクエリの回数）です。 この数 tt はここで説明するグローバーのアルゴリズムでは指定されておらず、どのように選択するかについては後でレッスン内で説明します。

グローバーのアルゴリズム
  1. nn 量子ビットのレジスタ Q\mathsf{Q} をゼロのみの状態 ∣0n⟩\vert 0^n \rangle に初期化し、Q\mathsf{Q} の各量子ビットにアダマール演算を適用します。
  2. ユニタリ演算 G=H⊗nZORH⊗nZfG = H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} Z_f をレジスタ Q\mathsf{Q} に tt 回適用します。
  3. Q\mathsf{Q} の量子ビットを標準基底測定で測定し、得られた文字列を出力します。

ステップ 2 で反復される演算 G=H⊗nZORH⊗nZfG = H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} Z_f は、このレッスンの残りの部分を通じてグローバー演算と呼びます。 n=7n=7 の場合のグローバー演算の量子回路表現を以下に示します。

A quantum circuit representation of the Grover operation

この図では、ZfZ_f 演算は ZORZ_{\mathrm{OR}} よりも大きく描かれています。これは、ZfZ_f がより計算コストの高い演算であることを非公式に視覚的に示唆するためです。 特に、クエリモデルで作業する場合、ZfZ_f は 1 回のクエリを必要とするのに対し、ZORZ_{\mathrm{OR}} はクエリを必要としません。 代わりに関数 ff のブール回路を持ち、それを ZfZ_f の量子回路に変換する場合、得られる量子回路は ZORZ_{\mathrm{OR}} の回路よりも大きく複雑になることが合理的に予想されます。

n=7n=7、t=3t=3 の場合のアルゴリズム全体の量子回路図を以下に示します。 tt の値が大きい場合は、測定の直前にグローバー演算のインスタンスを追加するだけで対応できます。

A quantum circuit for Grover's algorithm when t=3

グローバーのアルゴリズムは、次のように探索問題に応用できます。

  • ステップ 2 の数 tt を選択します（これについてはレッスンの後半で説明します）。
  • 選択した tt を用いて、関数 ff に対してグローバーのアルゴリズムを実行し、文字列 x∈Σnx\in\Sigma^n を得ます。
  • 文字列 xx で関数 ff にクエリを実行し、有効な解であるかどうかを確認します。
    • f(x)=1f(x) = 1 であれば、解が見つかったことになるので、停止して xx を出力できます。
    • それ以外の場合、f(x)=0f(x) = 0 であれば、場合によっては異なる tt の選択で手順を再実行するか、諦めて「解なし」と出力することを決めることができます。

グローバーのアルゴリズムの仕組みを分析することで、t=O(N)t = O(\sqrt{N}) と設定することで（解が存在する場合）高い確率で探索問題の解が得られることがわかります。