Qiskitで実装するGrover探索｜「あたり」を高速に見つける

量子アルゴリズム入門で「グローバーは探索を二次高速化する」と紹介しました。この記事はその実装版。Qiskitで実際にグローバー探索を組み、|11⟩ という「あたり」を高速に見つけるところまでやります。グローバーのアルゴリズムは1996年にLov Groverが発表したもので¹、量子計算が古典を上回ることを具体的に示した初期の代表例です。

何を作るのか

4通り（00, 01, 10, 11）の中から、あたりの1つを見つける問題を考えます。古典なら平均して約 N/2 回（ここでは2〜3回）試す必要がありますが、グローバーは O(√N) 回——ここではたった1回の反復で高確率に当てます²。

準備

pip install qiskit qiskit-aer

① オラクル: あたりに「印」をつける

オラクルは、あたりの状態の符号だけを反転させる回路です³。今回は |11⟩ をあたりにします。2量子ビットで「両方が1のときだけ位相を反転」＝制御Zゲート（cz）そのものです。

from qiskit import QuantumCircuit

def oracle_11():
    qc = QuantumCircuit(2, name="oracle")
    qc.cz(0, 1)      # |11⟩ にだけ -1 の位相をつける
    return qc

② 拡散演算子: 印を確率に増幅する

拡散（diffusion）演算子は「平均のまわりで振幅を反転」させ、印のついた状態の確率を持ち上げます⁴。定型的に H → X → 多制御Z → X → H で作ります。

def diffuser(n):
    qc = QuantumCircuit(n, name="diffuser")
    qc.h(range(n))
    qc.x(range(n))
    qc.h(n-1)
    qc.mcx(list(range(n-1)), n-1)   # 多制御X
    qc.h(n-1)
    qc.x(range(n))
    qc.h(range(n))
    return qc

③ 組み立てて実行

全体の流れは「重ね合わせを作る → (オラクル → 拡散) を反復 → 測定」です。4通り（N=4）であたり1個なら、最適な反復回数は約 (π/4)√N ≈ 1 回です⁵。

from qiskit_aer import AerSimulator

n = 2
qc = QuantumCircuit(n, n)
qc.h(range(n))                       # 全部を重ね合わせ（一様な初期状態）

qc.compose(oracle_11(), inplace=True)
qc.compose(diffuser(n), inplace=True)

qc.measure(range(n), range(n))

result = AerSimulator().run(qc, shots=1000).result()
print(result.get_counts())

実行すると {'11': 1000} のように、ほぼ100%であたりの 11 が出ます。一様だった確率（各25%）が、たった1回の反復で「あたりに集中」しました。

なぜ √N なのか（増幅の直感）

グローバーは1反復ごとに、あたりの振幅を一定角度ずつ回転させて増やします。角度が π/2 に届くまでの回数が、ちょうど約 √N に比例します。

• N=4 → 約1回
• N=100万 → 約1,000回（古典は平均50万回）

理論的背景：なぜ √N で、しかも最適なのか

もう一歩踏み込むと、グローバーは2次元平面内の回転として厳密に理解できます⁶。

状態全体を「あたりの状態 |good⟩」と「はずれの状態 |bad⟩」が張る2次元平面で考えます。一様な重ね合わせ |s⟩ は、|bad⟩ から角度 θ だけ傾いた位置にあり、あたりの数を M とすると sinθ = √(M/N) が成り立ちます。ここで 1回のグローバー反復（オラクル＋拡散）は、状態を |good⟩ に向かって角度 2θ だけ回転させます。オラクルによる反転と拡散による反転、2つの鏡（反射）の積が回転になる、というのが数学的な正体です。

|good⟩ に到達（角度 π/2）するのに必要な反復回数 k は、

k ≈ (π/2) / (2θ) = (π/4)·√(N/M)

となり、√N のスケーリングが導かれます。M=1、N=4 なら θ=30°、2θ=60°、1回転でちょうど90°に届く——だから「1回で当たる」わけです。

この「印→増幅」の枠組みは、あたりの初期振幅が未知でも使える**振幅増幅（amplitude amplification）**へと一般化され⁸、多くの量子アルゴリズムの部品になっています。

3量子ビットに拡張してみよう

n=3（N=8）にして、あたりを |111⟩ にするなら、オラクルを多制御Z（qc.h(2); qc.mcx([0,1],2); qc.h(2)）に変え、反復を2回に増やします（θ≈20.7°なので k≈2）。手を動かして、あたりの確率がどう変わるか観察してみてください。反復を3回・4回と増やすと確率が下がる（回りすぎる）ことも確かめると、理解が一段深まります。

まとめ

• グローバー＝「オラクルで印 → 拡散で増幅」を約√N回くり返す
• オラクルは位相反転（cz など）、拡散は「平均まわりの反転」
• 幾何学的には2次元平面内の回転で、1反復あたり 2θ（sinθ=√(M/N)）
• 反復は最適回数 (π/4)√(N/M) を超えると逆効果
• O(√N) は探索問題の理論的下限で、グローバーはオーダー最適

次の一歩 🌸

アルゴリズムの全体像は量子アルゴリズム入門、Qiskitの基礎に戻るならQiskit入門へどうぞ。

Footnotes

1. Grover, L. K. (1996). "A fast quantum mechanical algorithm for database search." Proceedings of the 28th Annual ACM Symposium on Theory of Computing (STOC '96), pp. 212–219. 未整序データからの探索を古典の O(N) から O(√N) へ改善した。 ↩

2. 古典では、構造のない N 件の探索は最悪 N 回・平均 N/2 回の問い合わせが必要（線形時間）。グローバーは O(√N) 回のオラクル問い合わせで済む「二次（quadratic）高速化」。指数的ではない点に注意。 ↩

3. ここでのオラクルは「あたりなら位相を −1 にする」位相オラクル（phase oracle）。ビットを反転するタイプのオラクルとは、補助量子ビットを |−⟩ にする位相キックバックで相互変換できる（ドイチュ・ジョザ参照）。 ↩

4. 拡散演算子は数式で D = 2|s⟩⟨s| − I（|s⟩ は一様重ね合わせ）。これは「平均値のまわりでの反転（inversion about the mean）」に等しく、各振幅 aᵢ を 2⟨a⟩ − aᵢ に写す。オラクルの符号反転と合わせると、2つの反射（鏡）の積＝回転になる。 ↩

5. 厳密な最適反復回数は k = round( (π/4)/θ − 1/2 )（sinθ=√(M/N)）で、近似的に (π/4)√(N/M)。k を超えると状態が |good⟩ を通り過ぎ、成功確率が周期的に上下する（over-rotation）。M が N に近いと θ が大きくなり、かえって回数が減る。 ↩ ↩²

6. この2次元回転の描像は Grover 探索の標準的な解析で、多くの教科書（例: Nielsen & Chuang, Quantum Computation and Quantum Information, Ch.6）で扱われる。状態が常に |good⟩–|bad⟩ 平面内に留まることが鍵。 ↩

7. Bennett, C. H., Bernstein, E., Brassard, G., & Vazirani, U. (1997). "Strengths and Weaknesses of Quantum Computing." SIAM J. Comput., 26(5), 1510–1523. ブラックボックス探索では Ω(√N) 回の問い合わせが必要という下界を示し、グローバーの最適性を保証した。 ↩

8. Brassard, G., Høyer, P., Mosca, M., & Tapp, A. (2000/2002). "Quantum Amplitude Amplification and Estimation." あたりの初期確率 a が未知でも成功確率を増幅でき、成功確率の推定（振幅推定）にも一般化される。モンテカルロ的な多くの量子アルゴリズムの基盤。 ↩