Grover 알고리즘

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

배경

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

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

요구 사항

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

• Qiskit SDK v1.4 이상 (시각화 지원 포함)
• 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단계: 고전적 입력을 양자 문제로 매핑하기

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를 사용합니다.

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

특정 Grover 인스턴스

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

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

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

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)의 이터러블을 받습니다. Sampler의 경우, 각 PUB는 (circuit, parameter_values) 형식의 이터러블입니다. 하지만 최소한 양자 Circuit 목록만 있으면 됩니다.

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

튜토리얼 설문 조사

이 짧은 설문 조사에 참여하여 튜토리얼에 대한 피드백을 제공해 주세요. 여러분의 의견은 콘텐츠와 사용자 경험 개선에 큰 도움이 됩니다.

설문 조사 링크

Note: This survey is provided by IBM Quantum and relates to the original English content. To give feedback on doQumentation's website, translations, or code execution, please open a GitHub issue.