記事の内容
この記事では、グローバーのアルゴリズムの計算過程を一歩ずつ紹介します。
- 具体例をベースに数式変形をできるだけ丁寧に進めます！！
- そして、勉強中に私が感じた、アルゴリズムの誤解しやすいところ、気になるところをできるだけ言語化します。
- アルゴリズムが答えをあらかじめ知っているように見える？
- オラクルでの正解だけ符号反転の計算量は？
- オラクルでの正解状態だけ符号反転。このとき、回路は正解を見つけたと言えるのか？
- 「量子情報」とは何か？
- こうした問いの言語化こそ、入門者にとっての価値になることを期待しています。（もちろん、まだまだ私も勉強中です。厳密ではない、不正確な記述になってしまったところがありえます。承知の上でご利用ください。）
それでは、まずはアルゴリズムの紹介から始めます。
グローバーのアルゴリズム入門（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回でコスト定数（または低次）で呼べるという前提で議論されます。
関連記事