はじめに
Groverのアルゴリズムによる探索では、古典プログラムでは$O(N)$かかるところが$O(\sqrt{N})$のコストで計算できるとされる。
これが実際に動かしてみるとどのくらい早くなっているのか気になったので、Python（Qiskit）で実装して古典コンピュータでシミュレーションを行い、効果を検証してみた。
※Groverのアルゴリズムについては以前の記事に詳細を記載しています
※本記事にはAIで生成したコードが含まれます
1. 問題定義
今回はよく使われる 「4桁の数字パスワード（0000〜9999）」を対象に、Grover探索と古典的な全探索を比較してどのくらいの回数で検索できるか検証を行う。
2. 実装概要
Groverのアルゴリズムは、目的の状態（正解）を強調して測定確率を高める量子探索アルゴリズムである。
ここでは4桁のパスワード（0000～9999）を探索対象とし、量子ビットの重ね合わせ状態からターゲット状態のみを強調して探索を行う。
処理の全体構成は以下のようになる。
$$
\text{入力パスワード} \xrightarrow{\text{2進変換}} |x\rangle
\rightarrow \text{Grover反復 (Oracle + Diffusionで正解の増幅)}
\rightarrow \text{測定}
$$
ここで、
- Oracle（オラクル）：正解状態にのみ $-1$ を掛けて印をつける
- Diffusion（拡散）：全体の平均振幅を基準に、確率を反転・増幅する
これらを繰り返すことで、正解状態の測定確率が高まる。
3. コード
3.1 パスワードを量子状態に変換
def password_to_binary(password, min_pw, num_qubits):
index = password - min_pw
return format(index, f'0{num_qubits}b')
与えられたパスワードを探索空間のインデックスに変換し、
量子状態（ビット列）に変換する。
例えば探索範囲が $0000 \sim 9999$ のとき、探索空間の大きさは $$ N = 10000, \quad \text{必要な量子ビット数} = \lceil \log_2 N \rceil = 14 $$ となる。
したがって、各パスワードは $|00000000000000\rangle$ から $|10011100001111\rangle$ の間の状態として表現される。
なお、これが3桁だと探索範囲は$000 \sim 999$となり、
$$
N = 1000, \quad \text{必要な量子ビット数} = \lceil \log_2 N \rceil = 10
$$
となる。
3.2 Groverアルゴリズムの設定と実行
実際の探索を行う関数は以下の通り。
def search_password_demo(target_password, min_pw=0, max_pw=999, password_type=None):
# 基本パラメータ計算
password_range = max_pw - min_pw + 1
num_qubits = math.ceil(math.log2(password_range))
# 最適イテレーション数を計算
total_items = 2 ** num_qubits
theta = math.asin(math.sqrt(1 / total_items))
optimal_iterations = int((math.pi / (4 * theta)) - 0.5)
optimal_iterations = max(1, optimal_iterations)
# オラクルを作成
target_binary = password_to_binary(target_password, min_pw, num_qubits)
oracle = Statevector.from_label(target_binary)
...
# Groverアルゴリズムを実行
problem = AmplificationProblem(oracle, is_good_state=[target_binary])
grover = Grover(iterations=optimal_iterations, sampler=StatevectorSampler())
result = grover.amplify(problem)
ここで行っている主要処理は次の通り。
-
オラクル (Oracle)：
与えられたターゲット状態 $|x_{target}\rangle$ の振幅に $-1$ を掛けて反転する。
これが「正解だけを強調する」仕組みの肝となる。$$
O|x\rangle =
\begin{cases}
-|x\rangle, & (x = x_{target})\
|x\rangle, & (x \neq x_{target})
\end{cases}
$$ -
拡散操作 (Diffusion Operator)：
全体の平均振幅に対して、状態を反転させる操作。
正解状態の確率を高める効果を持つ。$$
D = 2|\psi\rangle\langle\psi| - I
$$ -
反復回数 (最適イテレーション数)：
Groverアルゴリズムの反復回数 $r$ は次式で近似される。$$
r \approx \frac{\pi}{4}\sqrt{N}
$$
これにより、$O(N)$ 必要だった古典探索が $O(\sqrt{N})$ に短縮される。
3.3 検索結果の確認
アルゴリズムを実行すると、最も確率の高い測定結果が result.top_measurement として得られる。
それを再び10進数のパスワードに戻して結果を表示する。
found_password = binary_to_password(result.top_measurement, min_pw)
正解に一致した場合は、次のように出力される。
✅ 検索完了!
---
発見されたパスワード: 2985
発見状態: |00101110101001⟩
検索成功: ✅ YES
実行時間: 799.8197 秒
使用イテレーション数: 100
古典的な線形探索であれば平均 $N/2 = 5000$ 回の試行が必要だが、
今回のGroverでは100回で探索できており、 約50倍の高速化 が得られた。
3.4 複数デモによる統計分析
ランダムなパスワードを複数回探索し、成功率や平均速度を統計的に評価する。
results = []
for i in range(num_demos):
target = random.randint(min_pw, max_pw)
result = search_password_demo(target, min_pw, max_pw, password_type)
results.append(result)
結果は下図のように Matplotlib により可視化される。
- 成功率の円グラフ
- 実行時間のヒストグラム
- 高速化率の棒グラフ
これにより、量子探索の安定性・効率性を視覚的に確認できる。
今回の結果では2回の実行を通じて、4桁のパスワードが100回のイテレーションで探索された。
処理時間は(古典コンピュータで)約12~13分で探索できることが判明し、イテレーション回数から理論的に50倍高速化できていることがわかる。
ちなみに探索範囲が3桁だと4秒/回ほどで探索でき、古典コンピュータでは必要な量子ビット数によって処理時間が大きく変化することが分かる。
一方、0000から9999までを古典アルゴリズムで4桁のパスワードを全探索した場合は0.003秒ほどで発見できた。
4. 結果と考察
Groverアルゴリズムの性能は探索空間の大きさ $N$ に対して
$$
T_\text{quantum} \sim O(\sqrt{N})
$$
で増加する。
本検証では、もともとの処理時間が短いので効果をあまり体感しにくい例だったが、4桁パスワード（$N=10^4$）に対して理論的に高速な探索が確認できた。
| 項目 | 古典探索 | Grover探索 | 高速化 |
|---|---|---|---|
| 試行回数 | 5,000(期待値) | 100 | 50倍 |
古典的な線形探索では平均 $N/2 = 5000$ 回の試行が必要なところ、
Grover探索では 100回程度の反復 で済み、理論値通り約50倍の高速化が得られた。
5. まとめ
GroverのアルゴリズムをPython＋Qiskitで実装することで、
理論上の量子探索速度の向上を実際に確認できた。
- Groverアルゴリズムは、4桁パスワードのような離散探索問題で明確な量子優位性を示す
- イテレーション回数は古典探索の $O(N)$ に対して $O(\sqrt{N})$ であり、理論と一致
- Qiskit の
GroverクラスとAmplificationProblemにより、短いコードで実験可能
6. 今後の展開
- 実際のハードウェアバックエンド（IBM Quantum）での動作確認
- ノイズや測定誤差を考慮した実機検証
- より大きな探索空間（6桁や英数字混合パスワード）への拡張