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

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

背景

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

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

要件

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

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

セットアップ

# Added by doQumentation — required packages for this notebook
!pip install -q 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ゲート、または$N$量子ビット上のマルチ制御一般化は、$2^{N}-1$状態('1'*$N$ビット文字列)をマークします。バイナリ表現で1つ以上の'0'を持つ基底状態をマークするには、制御Zゲートの前後に対応する量子ビットにXゲートを適用する必要があります。これは、その量子ビットにオープン制御を持つことと同等です。次のコードでは、まさにそれを行うオラクルを定義し、ビット文字列表現を通じて定義された1つ以上の入力基底状態をマークします。MCMTゲートは、マルチ制御Zゲートを実装するために使用されます。

# To run on hardware, select the backend with the fewest number of jobs in the queue
service = QiskitRuntimeService()
backend = service.least_busy(
    operational=True, simulator=False, min_num_qubits=127
)
backend.name

'ibm_brisbane'

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

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

marked_states = ["011", "100"]

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

marked_states = ["011", "100"]

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

marked_states = ["011", "100"]

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

グローバー演算子

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

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

この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")

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

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)

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

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

振幅増幅は、Samplerランタイムプリミティブでの実行に適したサンプリング問題です。

Qiskit Runtime SamplerV2のrun()メソッドは、primitive unified blocks (PUBs)のイテラブルを取ることに注意してください。サンプラーの場合、各PUBは(circuit, parameter_values)形式のイテラブルです。ただし、最低限、量子回路のリストを取ります。

# To run on local simulator:
#   1. Use the StatevectorSampler from qiskit.primitives instead
sampler = Sampler(mode=backend)
sampler.options.default_shots = 10_000
result = sampler.run([circuit_isa]).result()
dist = result[0].data.meas.get_counts()

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

plot_distribution(dist)

チュートリアル調査

このチュートリアルに関するフィードバックを提供するため、この短い調査にご協力ください。お客様の洞察は、コンテンツ提供とユーザーエクスペリエンスの改善に役立ちます。

調査へのリンク