記事の内容

この記事では、グローバーのアルゴリズムの計算過程を一歩ずつ紹介します。

具体例をベースに数式変形をできるだけ丁寧に進めます！！
そして、勉強中に私が感じた、アルゴリズムの誤解しやすいところ、気になるところをできるだけ言語化します。
- アルゴリズムが答えをあらかじめ知っているように見える？
- オラクルでの正解だけ符号反転の計算量は？
- オラクルでの正解状態だけ符号反転。このとき、回路は正解を見つけたと言えるのか？
- 「量子情報」とは何か？
こうした問いの言語化こそ、入門者にとっての価値になることを期待しています。（もちろん、まだまだ私も勉強中です。厳密ではない、不正確な記述になってしまったところがありえます。承知の上でご利用ください。）

それでは、まずはアルゴリズムの紹介から始めます。

グローバーのアルゴリズム入門（3ビット完全解説付き）

1. グローバーのアルゴリズムとは？

グローバーのアルゴリズムは、量子コンピュータで特定の条件を満たす1つの解を、高速に見つけるアルゴリズムです。

問題設定（探索問題）

$N = 2^n$ 個の要素（$n$ビット）からなる集合 $S$ がある
その中に、条件を満たす「正解」の要素 $x^\ast$ がある
ブラックボックス関数 $f: {0,1}^n \rightarrow {0,1}$ によって判定できる：

f(x) = 
\begin{cases}
1 & \text{if } x = x^\ast \\
0 & \text{otherwise}
\end{cases}

グローバーの目的は：$f(x)=1$ となる $x^\ast$ を効率よく見つけること。

2. アルゴリズム全体の流れ

初期化：すべての状態を等確率で重ね合わせ
オラクル：正解状態に $-1$ の位相を与える
反転操作（ディフューザー）：振幅を平均から反転
繰り返し：上記の組み合わせを $O(\sqrt{N})$ 回
測定：正解が高確率で観測される

3. 数式で解説（n=3の場合）

ステップ1：初期状態の作成

まず、$|000\rangle$ に $H$（アダマール）ゲートを各ビットに適用：

|s\rangle = H^{\otimes 3} |000\rangle

アダマール変換 $H$ は以下の変換を行う（1量子ビット）：

H|0\rangle = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle), \quad H|1\rangle = \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)

したがって、

|s\rangle = \frac{1}{\sqrt{8}} \sum_{x \in \{0,1\}^3} |x\rangle

つまり、$|000\rangle$ 〜 $|111\rangle$ の全状態を均等に重ね合わせた状態です。

ステップ2：オラクルによる位相反転

オラクルは関数 $f(x)$ に基づいて次のように定義される：

U_f |x\rangle = (-1)^{f(x)} |x\rangle

つまり、$x = x^\ast$ のときだけ符号が反転します。

例：$x^\ast = 101$ の場合

U_f \left( \frac{1}{\sqrt{8}} \sum_x |x\rangle \right) = \frac{1}{\sqrt{8}} \left( \sum_{x \neq 101} |x\rangle - |101\rangle \right)

ステップ3：反転操作（ディフューザー）

この操作は、「平均からの差を反転させる」ことで、正解状態の振幅を増やします。

数学的定義：

U_s = 2|s\rangle\langle s| - I

これは「すべての状態からの平均」に対する反転を行うユニタリ演算です。

作用例：

U_s \left( \sum_x a_x |x\rangle \right) = \sum_x \left( 2\bar{a} - a_x \right) |x\rangle

ただし、$\bar{a} = \frac{1}{N} \sum_x a_x$ は平均振幅。

ステップ4：1回目の繰り返し後の状態（例：x*=101）

初期状態：

|\psi_0\rangle = \frac{1}{\sqrt{8}} \sum_x |x\rangle

オラクル適用：

|\psi_1\rangle = \frac{1}{\sqrt{8}} \left( \sum_{x \neq 101} |x\rangle - |101\rangle \right)

ディフューザー適用：

振幅の平均 $\bar{a}$ を計算：
- 正解以外の振幅：$\frac{1}{\sqrt{8}}$
- 正解：$-\frac{1}{\sqrt{8}}$
- 合計振幅：$7 \cdot \frac{1}{\sqrt{8}} - \frac{1}{\sqrt{8}} = \frac{6}{\sqrt{8}}$
- 平均振幅：

\bar{a} = \frac{1}{8} \cdot \left( 6 \cdot \frac{1}{\sqrt{8}} \right) = \frac{3}{4\sqrt{8}}

各振幅を $a_x \mapsto 2\bar{a} - a_x$ に変換

正解状態（x=101）の振幅：

a_{101}^{\text{new}} = 2\bar{a} - (-\frac{1}{\sqrt{8}}) = 2 \cdot \frac{3}{4\sqrt{8}} + \frac{1}{\sqrt{8}} = \frac{3}{2\sqrt{8}} + \frac{1}{\sqrt{8}} = \frac{5}{2\sqrt{8}}

非正解状態の振幅（他の7個）：

a_{x\neq 101}^{\text{new}} = 2\bar{a} - \frac{1}{\sqrt{8}} = 2 \cdot \frac{3}{4\sqrt{8}} - \frac{1}{\sqrt{8}} = \frac{3}{2\sqrt{8}} - \frac{1}{\sqrt{8}} = \frac{1}{2\sqrt{8}}

→ 正解の振幅が増え、非正解の振幅が減った！

ステップ5：繰り返すことで正解の確率が増加

グローバーの繰り返し回数 $R$ はおおよそ：

R = \left\lfloor \frac{\pi}{4} \sqrt{2^n} \right\rfloor

3ビットの場合：

R = \left\lfloor \frac{\pi}{4} \cdot \sqrt{8} \right\rfloor = \left\lfloor \frac{\pi}{4} \cdot 2.828 \right\rfloor = 2

ステップ6：測定すれば高確率で x* が得られる！

振幅が最も高くなっている状態は $x^\ast$。
測定すれば、ほぼ確実にそのビット列が得られます。

4. まとめ

グローバーのアルゴリズムは、探索問題の解を $O(\sqrt{N})$ で見つける量子アルゴリズム
オラクルとディフューザーを組み合わせ、振幅を操作して正解状態を増幅
3ビットの場合でも、計算の流れと意味がすべて数式で追える

補足　勉強していて気になったところ

「正解の中身」はわからないのに正解を発見できるということの核心

グローバーのアルゴリズムの核心は、

「正解を知る必要はなくても、“正解かどうか”だけを教えてくれる関数（=「オラクル」と呼ぶ）を使い、量子干渉によって正解状態の確率振幅を増幅できる」

→ これによって、正解の中身を知らずに「どれが正解か」を高確率（ほとんど1）で見つけられる。

アルゴリズムの概要

ステップ1：全状態の重ね合わせを準備
ステップ2：オラクル（Oracle）により正解状態だけが符号反転
ステップ3：ディフューザー（Diffuser）で干渉を起こす
ステップ4：上の2つを繰り返す（√N回）

いや、答えをあらかじめ知っているように見える？

オラクル関数を具体的に構成するとき、正解の具体的な値を使用しているように見えます。つまり、正解の値をあらかじめ知っているようです。

この考えのどこが間違っているのでしょうか。

シミュレーションでオラクル回路を手動で組むときには、勉強用目的で構成する。ゆえに、正解を知っている前提でアルゴリズムを作る。

しかし、理論上のグローバーのアルゴリズムでは、オラクルは与えられた「判定関数」であり、その中身を知らずに使う前提です。

本物の量子回路では、正解を指定するコードは使えるか？

使えない。正解はわからない前提。

ではどうする？

問題固有の判定関数 f(x) をユニタリな量子回路として構成する。

正解の情報は？

回路の中に、相対的な位相の違いとして表現されている。

オラクルでの正解状態だけ符号反転このとき、回路は正解を見つけた、と言えるのか？

この処理は情報を読み出すものではなく、あくまで干渉を起こすための準備です。

ポイント：
この時点では、正解の確率はまだほとんど変わっていません。

位相が変わっただけで、測定確率に直結しません。
位相の違いは、単一の測定結果には現れない（不可視）

量子力学において、位相の違いは単体では観測できません。観測可能な量（測定確率）は振幅の絶対値の二乗です。

量子状態は、振幅と位相を持った複素ベクトルで表現されます。だから、位相の違いは、状態の違い（情報の違い）と言えます。よって、位相の違いが干渉（計算過程）に影響を与え、計算結果の差異をうみます。

量子情報とは?

観測される前の世界において、「どのように重ね合わされ、干渉しうるか」に関する構造的情報のこと。

その意味で、「観測者には見えないが回路が使える情報」がまさに相対位相であり、コヒーレンスなのです。

量子情報とは、量子状態の数学的構造（ヒルベルト空間内のベクトル）を介して、物理系が保持・伝達・変換しうる情報のことであり、観測・干渉・エンタングルメントなど量子特有の操作と不可分なもの。

「測定前の状態に内在する、干渉には効くが観測では直接見えない情報」の例

相対位相

干渉には現れるが観測には現れない。量子状態の構造的な違いを決定する

量子コヒーレンス

相対位相が保たれている状態。干渉が可能であることの指標。

オフダイアゴナル要素

密度行列で位相を表す。$ρ01$、$ρ10$などがゼロでない＝位相がある

計算量について誤解しやすいところ　オラクルでの正解だけ符号反転の計算量は？

オラクル関数 𝑓(𝑥)をユニタリ回路に実装したときのゲート数に依存する。
通常、ビット数$n$に依存。

$O(n)$ ~ $O(n^2)$となる。（※多制御ゲートの分解方法に依存）

ゆえに、グローバーのアルゴリズムの最適性$O(√N)$は、オラクルが1回でコスト定数（または低次）で呼べるという前提で議論されます。

関連記事