Grover 알고리즘

사용 시간 예측: Eagle r3 프로세서에서 1분 미만 (참고: 이는 예측치이며 실제 실행 시간은 다를 수 있습니다.)

학습 목표

이 튜토리얼을 완료하면 다음 내용을 이해할 수 있습니다:

• 하나 이상의 계산 기저 상태를 표시하는 Grover 오라클을 구성하는 방법
• Qiskit Circuit 라이브러리의 grover_operator() 함수 사용 방법
• 주어진 문제에 대한 최적 Grover 반복 횟수를 결정하는 방법
• Qiskit Runtime Sampler 프리미티브를 사용하여 Grover 알고리즘을 실행하는 방법

사전 준비 사항

다음 주제를 미리 익혀두시길 권장합니다:

• 양자 알고리즘의 기초: Grover 알고리즘
• 양자 정보의 기초

배경

진폭 증폭(Amplitude amplification)은 범용 양자 알고리즘(또는 서브루틴)으로, 여러 고전 알고리즘에 비해 이차적 속도 향상을 얻는 데 활용할 수 있습니다. Grover 알고리즘은 비구조적 탐색 문제에서 이 속도 향상을 처음으로 입증한 알고리즘입니다. Grover 탐색 문제를 공식화하려면 하나 이상의 계산 기저 상태를 찾고자 하는 상태로 표시하는 오라클 함수와, 표시된 상태의 진폭을 높이고 나머지 상태를 억제하는 증폭 Circuit이 필요합니다.

여기서는 Grover 오라클을 구성하는 방법과 Qiskit Circuit 라이브러리의 grover_operator()를 사용하여 Grover 탐색 인스턴스를 손쉽게 설정하는 방법을 소개합니다. 런타임 Sampler 프리미티브를 통해 Grover Circuit을 원활하게 실행할 수 있습니다.

요구 사항

이 튜토리얼을 시작하기 전에 다음이 설치되어 있는지 확인하세요:

• Qiskit SDK v2.0 이상 (시각화 지원 포함)
• 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

소규모 시뮬레이터 예제

이 섹션에서는 실제 양자 하드웨어에서 동일한 문제를 실행하기 전에, 로컬 시뮬레이터를 사용하여 소규모로 Grover 알고리즘의 각 단계를 살펴봅니다.

1단계: 고전적 입력을 양자 문제로 매핑하기

Grover 알고리즘에는 하나 이상의 표시된 계산 기저 상태를 지정하는 오라클이 필요합니다. 여기서 "표시된"이란 위상이 -1인 상태를 의미합니다. controlled-Z Gate 또는 $N$ Qubit에 대한 다중 제어 일반화는 $2^{N}-1$ 상태('1'*$N$ 비트 문자열)를 표시합니다. 이진 표현에 하나 이상의 '0'이 있는 기저 상태를 표시하려면 controlled-Z Gate 전후에 해당 Qubit에 X Gate를 적용해야 합니다. 이는 해당 Qubit에 열린 제어(open-control)를 두는 것과 동일합니다. 다음 코드에서는 비트스트링 표현으로 정의된 하나 이상의 입력 기저 상태를 표시하는 오라클을 정의합니다. 다중 제어 Z Gate를 구현하기 위해 MCMT Gate를 사용합니다.

특정 Grover 인스턴스

오라클 함수가 준비되었으니, 이제 Grover 탐색의 특정 인스턴스를 정의할 수 있습니다. 이 예제에서는 세 qubit 계산 공간의 여덟 가지 가능한 상태 중 두 개의 계산 상태를 표시합니다:

marked_states = ["011", "100"]

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

Grover 연산자

Qiskit의 내장 grover_operator()는 오라클 Circuit을 받아 오라클 Circuit 자체와 오라클이 표시한 상태를 증폭하는 Circuit으로 구성된 Circuit을 반환합니다. 여기서는 decompose() 메서드를 사용하여 연산자 내부의 Gate를 확인합니다:

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

이 grover_op Circuit을 반복 적용하면 표시된 상태가 증폭되어 Circuit 출력 분포에서 가장 높은 확률의 비트 문자열이 됩니다. 최적 반복 횟수는 표시된 상태의 수와 가능한 전체 계산 상태 수의 비율로 결정됩니다:

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

전체 Grover Circuit

완전한 Grover 실험은 각 Qubit에 Hadamard Gate를 적용하여 모든 계산 기저 상태의 균등한 중첩 상태를 만드는 것으로 시작하며, 이후 Grover 연산자(grover_op)를 최적 횟수만큼 반복 적용합니다. 여기서는 QuantumCircuit.power(INT) 메서드를 활용하여 Grover 연산자를 반복 적용합니다.

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단계: 양자 하드웨어 실행을 위한 문제 최적화

소규모 시뮬레이션의 경우, 특정 하드웨어를 대상으로 하지 않고 Circuit을 트랜스파일합니다.

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

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)

하드웨어 예제

1~4단계

Grover 알고리즘은 본질적으로 내결함성 알고리즘입니다 — 오라클과 확산 연산자의 핵심인 다중 제어 Z Gate는 qubit 수가 증가할수록 2-Qubit 게이트 깊이가 매우 빠르게 증가합니다(다음 섹션에서 보여줄 것입니다). 이는 오늘날의 잡음이 있는 하드웨어에서 알고리즘이 잘 확장되지 않음을 의미합니다. 따라서 더 큰 문제 크기를 시도하는 대신, 위의 시뮬레이터 예제와 동일한 소규모에서 하드웨어 실행을 시연합니다.

# -------------------------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)

논의: 2-Qubit 게이트 깊이 확장성

Grover 알고리즘이 내결함성 알고리즘으로 여겨지는 주요 이유 중 하나는 qubit 수가 증가함에 따라 Circuit의 2-Qubit 게이트 깊이가 급격히 증가하기 때문입니다. 오라클과 확산 연산자 모두의 핵심인 다중 제어 Z Gate는 제어 qubit 수에 따라 지수적으로 증가하는 수의 2-Qubit 게이트로 분해됩니다. 최적 Grover 반복 횟수 자체가 $O(\sqrt{2^n})$으로 증가한다는 사실과 결합하면, 전체 2-Qubit 깊이는 잡음이 있는 하드웨어에서 금방 비실용적이 됩니다.

아래에서는 증가하는 qubit 수에 대해 Grover Circuit을 구성하고, 트랜스파일한 후, 이 확장성을 보여주기 위해 결과 2-Qubit 게이트 깊이를 그래프로 표시합니다.

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

그래프에서 보듯이, 2-Qubit 게이트 깊이는 qubit 수가 증가할수록 매우 빠르게 — 대략 지수적으로 — 증가합니다. 이는 현재의 잡음이 있는 양자 하드웨어에서 매우 작은 문제 크기를 넘어서는 Grover 알고리즘을 비실용적으로 만듭니다. 이 알고리즘은 오류 정정을 통해 깊은 Circuit을 신뢰성 있게 실행할 수 있는 미래의 내결함성 양자 컴퓨터의 중요한 목표로 남아 있습니다.

다음 단계

권장 사항

이 내용이 흥미로우셨다면, 다음 자료에도 관심을 가져보실 수 있습니다:

• Qiskit Circuit 라이브러리: grover_operator() API 레퍼런스
• QAOA 튜토리얼과 유틸리티 규모 QAOA 레슨은 양자 컴퓨터를 이용한 최적화의 근거리 예제를 제공합니다
• 근거리 알고리즘에 대한 더 깊은 이해를 위해 실용적 양자 컴퓨팅 강좌를 참고하세요