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

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

使用時間の推定: Eagle r3プロセッサで1分未満(注意: これは推定値です。実際の実行時間は異なる場合があります。)

学習成果​

このチュートリアルを完了すると、以下の内容を理解できることが期待されます:

  • 1つ以上の計算基底状態をマークするグローバーオラクルの構築方法
  • Qiskit回路ライブラリのgrover_operator()関数の使い方
  • 与えられた問題に対する最適なグローバー反復回数の決定方法
  • Qiskit Runtime Samplerプリミティブを使用したグローバーのアルゴリズムの実行方法

前提条件​

以下のトピックに事前に慣れておくことをお勧めします:

背景​

振幅増幅は、いくつかの古典アルゴリズムに対して二次的な高速化を実現するために使用できる汎用量子アルゴリズム、またはサブルーチンです。グローバーのアルゴリズムは、構造化されていない検索問題でこの高速化を実証した最初のアルゴリズムです。グローバーの検索問題を定式化するには、1つ以上の計算基底状態を興味のある状態としてマークするオラクル関数と、マークされた状態の振幅を増加させ、残りの状態を抑制する増幅回路が必要です。

ここでは、グローバーオラクルを構築し、Qiskit回路ライブラリのgrover_operator()を使用してグローバーの検索インスタンスを簡単にセットアップする方法を示します。ランタイムSamplerプリミティブにより、グローバー回路のシームレスな実行が可能になります。

要件​

このチュートリアルを始める前に、以下がインストールされていることを確認してください:

  • Qiskit SDK v2.0以降、visualizationサポート付き
  • Qiskit Runtime v0.22以降 (pip install qiskit-ibm-runtime)

セットアップ​

# Added by doQumentation — required packages for this notebook
!pip install -q matplotlib qiskit qiskit-ibm-runtime
# Built-in modules
import math

# Imports from Qiskit
from qiskit import QuantumCircuit
from qiskit.circuit.library import grover_operator, MCMTGate, ZGate
from qiskit.visualization import plot_distribution
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

# Imports from Qiskit Runtime
from qiskit_ibm_runtime import QiskitRuntimeService
from qiskit_ibm_runtime import SamplerV2 as Sampler

def grover_oracle(marked_states):
    """Build a Grover oracle for multiple marked states

    Here we assume all input marked states have the same number of bits

    Parameters:
        marked_states (str or list): Marked states of oracle

    Returns:
        QuantumCircuit: Quantum circuit representing Grover oracle
    """
    if not isinstance(marked_states, list):
        marked_states = [marked_states]
    # Compute the number of qubits in circuit
    num_qubits = len(marked_states[0])

    qc = QuantumCircuit(num_qubits)
    # Mark each target state in the input list
    for target in marked_states:
        # Flip target bit-string to match Qiskit bit-ordering
        rev_target = target[::-1]
        # Find the indices of all the '0' elements in bit-string
        zero_inds = [
            ind
            for ind in range(num_qubits)
            if rev_target.startswith("0", ind)
        ]
        # Add a multi-controlled Z-gate with pre- and post-applied X-gates (open-controls)
        # where the target bit-string has a '0' entry
        if zero_inds:
            qc.x(zero_inds)
        qc.compose(MCMTGate(ZGate(), num_qubits - 1, 1), inplace=True)
        if zero_inds:
            qc.x(zero_inds)
    return qc

小規模シミュレーター例​

このセクションでは、実際の量子ハードウェアで同じ問題を実行する前に、ローカルシミュレーターを使用してグローバーのアルゴリズムの各ステップを小規模で説明します。

ステップ1: 古典的な入力を量子問題にマッピング​

グローバーのアルゴリズムには、1つ以上のマークされた計算基底状態を指定するオラクルが必要です。ここで「マークされた」とは、位相が-1の状態を意味します。制御Zゲート、またはNN量子ビット上のマルチ制御一般化は、2N−12^{N}-1状態('1'*NNビット文字列)をマークします。バイナリ表現で1つ以上の'0'を持つ基底状態をマークするには、制御Zゲートの前後に対応する量子ビットにXゲートを適用する必要があります。これは、その量子ビットにオープン制御を持つことと同等です。次のコードでは、ビットストリング表現を通じて定義された1つ以上の入力基底状態をマークするオラクルを定義します。MCMTゲートは、マルチ制御Zゲートを実装するために使用されます。

特定のグローバーのインスタンス​

オラクル関数ができたので、グローバー検索の特定のインスタンスを定義できます。この例では、3量子ビット計算空間で利用可能な8つのうち2つの計算状態をマークします:

marked_states = ["011", "100"]

oracle = grover_oracle(marked_states)
oracle.draw(output="mpl", style="iqp")

Output of the previous code cell

グローバー演算子​

組み込みのQiskit grover_operator()は、オラクル回路を受け取り、オラクル回路自体とオラクルによってマークされた状態を増幅する回路で構成される回路を返します。ここでは、演算子内のゲートを確認するために回路のdecompose()メソッドを使用します:

grover_op = grover_operator(oracle)
grover_op.decompose().draw(output="mpl", style="iqp")

Output of the previous code cell

このgrover_op回路の繰り返し適用により、マークされた状態が増幅され、回路からの出力分布で最も可能性の高いビット文字列になります。最適な適用回数は、マークされた状態と可能な計算状態の総数の比率によって決定されます:

optimal_num_iterations = math.floor(
    math.pi
    / (4 * math.asin(math.sqrt(len(marked_states) / 2**grover_op.num_qubits)))
)

完全なグローバー回路​

完全なグローバー実験は、各量子ビットにアダマールゲートから始まります。すべての計算基底状態の均等な重ね合わせを作成し、その後、グローバー演算子(grover_op)を最適回数繰り返します。ここでは、QuantumCircuit.power(INT)メソッドを使用してグローバー演算子を繰り返し適用します。

qc = QuantumCircuit(grover_op.num_qubits)
# Create even superposition of all basis states
qc.h(range(grover_op.num_qubits))
# Apply Grover operator the optimal number of times
qc.compose(grover_op.power(optimal_num_iterations), inplace=True)
# Measure all qubits
qc.measure_all()
qc.draw(output="mpl", style="iqp")

Output of the previous code cell

ステップ2: 量子ハードウェア実行用に問題を最適化​

小規模シミュレーションでは、特定のハードウェアをターゲットにせずに回路をトランスパイルします。

pm = generate_preset_pass_manager(optimization_level=3)
circuit_isa = pm.run(qc)
circuit_isa.draw(output="mpl", idle_wires=False, style="iqp")

Output of the previous code cell

ステップ3: Qiskitプリミティブを使用して実行​

振幅増幅は、SamplerV2プリミティブでの実行に適したサンプリング問題です。ここでは、ローカルシミュレーションのためにqiskit.primitivesのStatevectorSamplerを使用します。

from qiskit.primitives import StatevectorSampler

sampler = StatevectorSampler()
result = sampler.run([circuit_isa], shots=10_000).result()
dist = result[0].data.meas.get_counts()

ステップ4: 後処理し、希望する古典形式で結果を返す​

plot_distribution(dist)

Output of the previous code cell

ハードウェア例​

ステップ1〜4​

グローバーのアルゴリズムは本質的にフォールトトレラントなアルゴリズムです — オラクルと拡散演算子の中核にあるマルチ制御Zゲートは、量子ビット数が増えるにつれて非常に急速に成長する2量子ビットゲート深度をもたらします(次のセクションで示します)。これは、今日のノイジーなハードウェアではアルゴリズムがうまくスケールしないことを意味します。このため、より大きな問題サイズを試みるのではなく、上記のシミュレーター例と同じ小規模でハードウェア実行を示します。

# -------------------------Step 1-------------------------
marked_states = ["011", "100"]

oracle = grover_oracle(marked_states)
grover_op = grover_operator(oracle)

optimal_num_iterations = math.floor(
    math.pi
    / (4 * math.asin(math.sqrt(len(marked_states) / 2**grover_op.num_qubits)))
)

qc = QuantumCircuit(grover_op.num_qubits)
qc.h(range(grover_op.num_qubits))
qc.compose(grover_op.power(optimal_num_iterations), inplace=True)
qc.measure_all()

# -------------------------Step 2-------------------------
service = QiskitRuntimeService()
backend = service.least_busy(
    operational=True, simulator=False, min_num_qubits=127
)

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)
circuit_isa = pm.run(qc)

# -------------------------Step 3-------------------------
sampler = Sampler(mode=backend)
sampler.options.default_shots = 10_000
sampler.options.environment.job_tags = ["TUT-GA"]
result = sampler.run([circuit_isa]).result()
dist = result[0].data.meas.get_counts()

# -------------------------Step 4-------------------------
plot_distribution(dist)

Output of the previous code cell

考察: 2量子ビットゲート深度のスケーリング​

グローバーのアルゴリズムがフォールトトレラントなアルゴリズムと見なされる主な理由は、量子ビット数が増えるにつれて回路の2量子ビットゲート深度が急速に成長することです。オラクルと拡散演算子の両方の中核にあるマルチ制御Zゲートは、制御量子ビット数に対して指数関数的に成長する数の2量子ビットゲートに分解されます。最適なグローバー反復回数自体がO(2n)O(\sqrt{2^n})として成長するという事実と組み合わされると、全体の2量子ビット深度はノイジーなハードウェアにとってすぐに非現実的になります。

以下では、量子ビット数を増やしながらグローバー回路を構築し、トランスパイルして、このスケーリングを示すために結果の2量子ビットゲート深度をプロットします。

import matplotlib.pyplot as plt

num_qubits_list = list(range(3, 10))
two_q_depths = []
backend = service.least_busy(
    operational=True, simulator=False, min_num_qubits=127
)
for n in num_qubits_list:
    # Mark a single state for simplicity
    marked = ["1" * n]
    oracle_n = grover_oracle(marked)
    grover_op_n = grover_operator(oracle_n)

    # Optimal number of iterations
    num_iters = math.floor(
        math.pi / (4 * math.asin(math.sqrt(len(marked) / 2**n)))
    )

    # Build the full Grover circuit
    qc_n = QuantumCircuit(n)
    qc_n.h(range(n))
    qc_n.compose(grover_op_n.power(num_iters), inplace=True)
    qc_n.measure_all()

    # Transpile to a basis gate set and count 2Q depth
    pm_n = generate_preset_pass_manager(backend=backend, optimization_level=3)
    qc_transpiled = pm_n.run(qc_n)

    # Compute depth restricted to 2-qubit operations
    depth_2q = qc_transpiled.depth(lambda x: x.operation.num_qubits == 2)

    two_q_depths.append(depth_2q)
    print(f"n={n}: optimal_iters={num_iters}, 2Q depth={depth_2q}")

# Plot
fig, ax = plt.subplots(figsize=(8, 5))
ax.plot(
    num_qubits_list,
    two_q_depths,
    "o-",
    linewidth=2,
    markersize=8,
    color="#6929C4",
)
ax.set_xlabel("Number of qubits", fontsize=13)
ax.set_ylabel("Two-qubit gate depth", fontsize=13)
ax.set_title("Grover's algorithm: 2Q depth scaling", fontsize=14)
ax.set_yscale("log")
ax.grid(True, alpha=0.3)
ax.set_xticks(num_qubits_list)
plt.tight_layout()
plt.show()
n=3: optimal_iters=2, 2Q depth=39
n=4: optimal_iters=3, 2Q depth=111
n=5: optimal_iters=4, 2Q depth=466
n=6: optimal_iters=6, 2Q depth=1646
n=7: optimal_iters=8, 2Q depth=3550
n=8: optimal_iters=12, 2Q depth=7989
n=9: optimal_iters=17, 2Q depth=14824

Output of the previous code cell

プロットが示すように、2量子ビットゲート深度は量子ビット数とともに非常に急速に — ほぼ指数関数的に — 成長します。これにより、グローバーのアルゴリズムは非常に小さな問題サイズを超えると、現在のノイジーな量子ハードウェアでは実用的でなくなります。このアルゴリズムは、誤り訂正によって深い回路を確実に実行できる将来のフォールトトレラント量子コンピューターの重要なターゲットであり続けます。

次のステップ​

おすすめ

この作業に興味を持った方には、以下の資料をお勧めします:

出典: IBM Quantum docs — 更新日 2026年5月8日
doQumentation の 英語版 — 更新日 2026年5月8日
この翻訳は 2026年4月9日 の英語版に基づいています
サイトや翻訳の問題?内容の問題? IBM Quantum docs で編集