주 콘텐츠로 건너뛰기

양자 알고리즘: Grover 탐색과 응용

참고

Atsushi Matsuo (2024년 5월 10일)

원본 강의의 PDF를 다운로드하세요. 정적 이미지로 제공되므로 일부 코드 스니펫은 더 이상 사용되지 않을 수 있습니다.

이 실험을 실행하는 데 필요한 QPU 시간은 약 2초입니다.

1. Grover 알고리즘 소개​

이 노트북은 양자 컴퓨팅의 유틸리티로 가는 길에 관한 강의 시리즈의 네 번째입니다. 이 노트북에서는 Grover 알고리즘에 대해 학습합니다.

Grover 알고리즘은 고전적인 탐색 방법에 비해 이차적인 속도 향상을 제공하기 때문에 가장 잘 알려진 양자 알고리즘 중 하나입니다. 고전 컴퓨팅에서 NN개의 항목으로 이루어진 정렬되지 않은 데이터베이스를 탐색하려면 O(N)O(N)의 시간 복잡도가 필요합니다. 즉, 최악의 경우 각 항목을 개별적으로 검토해야 할 수도 있습니다. 그러나 Grover 알고리즘을 사용하면 양자역학의 원리를 활용하여 목표 항목을 더 효율적으로 찾아낼 수 있으며, O(N)O(\sqrt{N}) 시간 안에 탐색을 완료할 수 있습니다.

이 알고리즘은 진폭 증폭(amplitude amplification)을 사용합니다. 이는 양자 중첩 상태에서 정답 상태의 확률 진폭을 높여 측정 시 더 높은 확률로 관측될 수 있도록 하는 과정입니다. 이러한 속도 향상 덕분에 Grover 알고리즘은 단순한 데이터베이스 탐색을 넘어, 특히 데이터셋 크기가 클 때 다양한 응용 분야에서 유용하게 활용됩니다. 알고리즘에 대한 자세한 설명은 Grover 알고리즘 노트북에서 확인하세요.

Grover 알고리즘의 기본 구조​

Grover 알고리즘은 네 가지 주요 구성 요소로 이루어져 있습니다:

  1. 초기화(Initialization): 모든 가능한 상태에 대한 중첩을 설정합니다.
  2. Oracle: 목표 상태의 위상을 뒤집어 해당 상태를 표시하는 오라클 함수를 적용합니다.
  3. 확산 연산자(Diffusion Operator): 표시된 상태의 확률을 증폭시키는 일련의 연산을 적용합니다.

이 각 단계는 알고리즘이 효율적으로 동작하는 데 핵심적인 역할을 합니다. 각 단계에 대한 자세한 설명은 이후에 제공됩니다.

2. Grover 알고리즘 구현​

2.1 준비​

양자 Circuit을 실행하기 위한 환경을 설정하고 필요한 라이브러리를 가져옵니다.

# Added by doQumentation — required packages for this notebook
!pip install -q qiskit qiskit-aer qiskit-ibm-runtime
%config InlineBackend.figure_format = 'svg' # Makes the images look nice
# importing Qiskit
from qiskit import QuantumCircuit, ClassicalRegister, QuantumRegister

# import basic plot tools
from qiskit.visualization import plot_histogram

1단계: 문제를 양자 Circuit과 연산자로 매핑​

4개의 원소로 구성된 리스트를 생각해 봅니다. 목표는 특정 조건을 만족하는 원소의 인덱스를 찾는 것입니다. 예를 들어, 값이 2인 원소의 인덱스를 찾고자 합니다. 이 예시에서 양자 상태 ∣01⟩|01\rangle은 해당 조건을 만족하는 원소의 인덱스를 나타내며, 값 2가 위치한 자리를 가리킵니다.

2단계: 목표 하드웨어에 맞게 최적화​

1: 초기화​

초기화 단계에서는 모든 가능한 상태의 중첩을 생성합니다. 이는 n-Qubit 레지스터의 각 Qubit에 Hadamard Gate를 적용함으로써 달성되며, 그 결과 2n2^n개의 상태에 대한 균등한 중첩이 만들어집니다. 수학적으로는 다음과 같이 표현할 수 있습니다:

1N∑x=0N−1∣x⟩\frac{1}{\sqrt{N}} \sum_{x=0}^{N-1} |x\rangle

여기서 N=2nN = 2^n은 가능한 상태의 총 수입니다. 또한 보조 비트의 상태를 ∣−⟩|-\rangle로 변경합니다.

def initialization(circuit):
    # Initialization
    n = circuit.num_qubits
    # For input qubits
    for qubit in range(n - 1):
        circuit.h(qubit)
    # For the ancilla bit
    circuit.x(n - 1)
    circuit.h(n - 1)
    circuit.barrier()
    return circuit
n = 2
qr = QuantumRegister(n, "q")
anc = QuantumRegister(1, "ancillary")
initialization_circuit = QuantumCircuit(qr, anc)

initialization(initialization_circuit)
initialization_circuit.draw(output="mpl", idle_wires=False)

Output of the previous code cell

2: Oracle​

Oracle은 Grover 알고리즘의 핵심 부분입니다. 목표 상태에 위상 이동을 적용하여 해당 상태를 표시하며, 일반적으로 그 상태와 연관된 진폭의 부호를 뒤집습니다. Oracle은 주로 문제에 특화되어 있으며 목표 상태를 식별하는 기준에 따라 구성됩니다. 수학적으로 Oracle은 다음과 같은 변환을 적용합니다:

f(x)={1,if x=xtarget0,otherwisef(x) = \begin{cases} 1, & \text{if } x = x_{\text{target}} \\ 0, & \text{otherwise} \end{cases}

이 위상 뒤집기는 위상 킥백(phase kickback)을 통해 목표 상태의 진폭에 음의 부호를 적용함으로써 이루어집니다.

def oracle(circuit):
    circuit.x(1)
    circuit.ccx(0, 1, 2)
    circuit.x(1)
    circuit.barrier()
n = 2
qr = QuantumRegister(n, "q")
anc = QuantumRegister(1, "ancillary")
oracle_circuit = QuantumCircuit(qr, anc)

oracle(oracle_circuit)
oracle_circuit.draw(output="mpl", idle_wires=False)

Output of the previous code cell

3: 확산 연산자​

진폭 증폭 과정은 Grover 알고리즘을 고전적인 탐색과 구별짓는 핵심 요소입니다. Oracle이 목표 상태를 표시한 후, 이 표시된 상태의 진폭을 높여 측정 시 더 높은 확률로 관측될 수 있도록 하는 일련의 연산을 적용합니다. 이 과정은 **확산 연산자(Diffusion Operator)**를 통해 이루어지며, 이는 평균 진폭에 대한 반전을 효과적으로 수행합니다. 수학적 연산은 다음과 같습니다:

D=2∣ψ⟩⟨ψ∣−ID = 2|\psi\rangle\langle\psi| - I

여기서 DD는 확산 연산자, II는 항등 행렬, ∣ψ⟩|\psi\rangle는 균등 중첩 상태입니다. Oracle과 확산 연산자의 조합은 표시된 상태를 측정할 확률을 최대화하기 위해 약 N\sqrt{N}번 반복 적용됩니다.

def diffusion(circuit):
    input_qubits = circuit.num_qubits - 1
    circuit.h(range(0, input_qubits))
    circuit.x(range(0, input_qubits))
    circuit.h(input_qubits - 1)
    circuit.mcx([i for i in range(0, input_qubits - 1)], input_qubits - 1)
    circuit.h(input_qubits - 1)
    circuit.x(range(0, input_qubits))
    circuit.h(range(0, input_qubits))
    circuit.barrier()
n = 2
qr = QuantumRegister(n, "q")
anc = QuantumRegister(1, "ancillary")
diffusion_circuit = QuantumCircuit(qr, anc)

diffusion(diffusion_circuit)
diffusion_circuit.draw(output="mpl", idle_wires=False)

Output of the previous code cell

2.2 2-Qubit Grover 탐색 예시​

n = 2
qr = QuantumRegister(n, "q")
anc = QuantumRegister(1, "ancillary")
meas = ClassicalRegister(3, "meas")
grover_circuit = QuantumCircuit(qr, anc, meas)
# the number of iterations
num_iterations = 1
# Let's do Grover search
initialization(grover_circuit)

for i in range(0, num_iterations):
    oracle(grover_circuit)
    diffusion(grover_circuit)

# Clear the ancilla bit
grover_circuit.h(n)
grover_circuit.x(n)
grover_circuit.measure_all(add_bits=False)

grover_circuit.draw(output="mpl", idle_wires=False)

Output of the previous code cell

2.3 시뮬레이터로 실험하기​

3단계: Circuit 실행​

from qiskit_aer import AerSimulator
from qiskit_ibm_runtime import Sampler
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

# Define backend
backend = AerSimulator()

# Transpile to backend
pm = generate_preset_pass_manager(backend=backend, optimization_level=1)
isa_qc = pm.run(grover_circuit)

# Run the job
sampler = Sampler(mode=backend)
job = sampler.run([isa_qc])
result = job.result()

4단계: 결과 후처리​

# Print the results
counts = result[0].data.meas.get_counts()
print(counts)

# Plot the counts in a histogram
plot_histogram(counts)
{'001': 1024}

Output of the previous code cell

올바른 답인 ∣01⟩|01\rangle을 얻었습니다. Qubit의 순서에 주의해야 합니다.

3. 실제 디바이스로 실험하기​

단계 2: 대상 하드웨어에 맞게 최적화하기​

from qiskit_ibm_runtime import QiskitRuntimeService

service = QiskitRuntimeService()
real_backend = service.backend("ENTER-QPU-NAME-HERE")
# You can also identify the least busy device

real_backend = service.least_busy(simulator=False, operational=True)
print("The least busy device is ", real_backend)
# Transpile the circuit into basis gates executable on the hardware
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

pm = generate_preset_pass_manager(backend=real_backend, optimization_level=1)
target_circuit = pm.run(grover_circuit)

target_circuit.draw(output="mpl", idle_wires=False)

Output of the previous code cell

Circuit을 트랜스파일하면 해당 디바이스의 네이티브 기저 Gate를 사용하는 Circuit으로 변환됩니다.

단계 3: Circuit 실행하기​

sampler = Sampler(real_backend)
job_real = sampler.run([target_circuit])
job_id = job_real.job_id()
print("job id:", job_id)
job id: cw69csv19rzg0080yfkg
# Check the job status
job_real.status()
'QUEUED'
# If the Notebook session got disconnected you can also check your job status
# by running the following code
job_real = service.job(job_id)  # Input your job-id between the quotations
job_real.status()
'DONE'
# Execute after job has successfully run
result_real = job_real.result()
print(result_real[0].data.meas.get_counts())
{'101': 540, '001': 2253, '011': 476, '000': 251, '110': 105, '100': 100, '010': 168, '111': 203}

단계 4: 결과 후처리하기​

plot_histogram(result_real[0].data.meas.get_counts())

Output of the previous code cell

이번에는 3-Qubit Grover 탐색 예제를 시도해 보겠습니다.

n = 3
qr = QuantumRegister(n, "q")
anc = QuantumRegister(1, "ancilla")
grover_circuit = QuantumCircuit(qr, anc)
# the number of iterations
num_iterations = 2
def oracle(circuit):
    circuit.mcx([0, 1, 2], 3)
    circuit.barrier()

이번에는 ∣111⟩|111\rangle이 "정답" 상태입니다.

# Let's do Grover search
initialization(grover_circuit)

for i in range(0, num_iterations):
    oracle(grover_circuit)
    diffusion(grover_circuit)

# Clear the ancilla bit
grover_circuit.h(n)
grover_circuit.x(n)

grover_circuit.draw(output="mpl", idle_wires=False)

Output of the previous code cell

grover_circuit.measure_all()

# Define backend
backend = AerSimulator()

# Transpile to backend
pm = generate_preset_pass_manager(backend=backend, optimization_level=1)
isa_qc = pm.run(grover_circuit)

# Run the job
sampler = Sampler(backend)
job = sampler.run([isa_qc], shots=1024)
result = job.result()

# Print the results
counts = result[0].data.meas.get_counts()
print(counts)

# Plot the counts in a histogram
plot_histogram(counts)
{'0111': 977, '0100': 11, '0001': 8, '0000': 8, '0011': 5, '0010': 12, '0110': 3}

Output of the previous code cell

예상대로 ∣0111⟩|0111\rangle이 가장 높은 확률로 관측됩니다. 이 경우 반복 횟수 2회가 최적입니다. 다만, 정답을 얻을 확률이 100%가 아닌 것은 Grover 탐색에서 일반적인 현상입니다.

3번 반복하면 어떻게 될까요?​

이번에는 3번 반복해 보겠습니다.

n = 3
qr = QuantumRegister(n, "q")
anc = QuantumRegister(1, "ancillary")
grover_circuit = QuantumCircuit(qr, anc)
# the number of iterations
num_iterations = 3
# Let's do Grover search
initialization(grover_circuit)

for i in range(0, num_iterations):
    oracle(grover_circuit)
    diffusion(grover_circuit)

# Clear the ancilla bit
grover_circuit.h(n)
grover_circuit.x(n)

grover_circuit.draw(output="mpl", idle_wires=False, fold=-1, scale=0.5)

Output of the previous code cell

grover_circuit.measure_all()

# Define backend
backend = AerSimulator()

# Transpile to backend
pm = generate_preset_pass_manager(backend=backend, optimization_level=1)
isa_qc = pm.run(grover_circuit)

# Run the job
sampler = Sampler(backend)
job = sampler.run([isa_qc], shots=1024)
result = job.result()

# Print the results
counts = result[0].data.meas.get_counts()
print(counts)

# Plot the counts in a histogram
plot_histogram(counts)
{'0010': 88, '0001': 103, '0000': 94, '0111': 334, '0100': 112, '0110': 106, '0101': 99, '0011': 88}

Output of the previous code cell

∣0111⟩|0111\rangle은 여전히 가장 높은 확률로 관측되지만, 정답을 얻을 확률이 약간 감소했습니다.

4번이라면 어떨까요?​

이번에는 4번 반복해 보겠습니다.

n = 3
qr = QuantumRegister(n, "q")
anc = QuantumRegister(1, "ancillary")
grover_circuit = QuantumCircuit(qr, anc)
# the number of iterations
num_iterations = 4
# Let's do Grover search
initialization(grover_circuit)

for i in range(0, num_iterations):
    oracle(grover_circuit)
    diffusion(grover_circuit)

# Clear the ancilla bit
grover_circuit.h(n)
grover_circuit.x(n)

grover_circuit.draw(output="mpl", idle_wires=False, fold=-1, scale=0.5)

Output of the previous code cell

grover_circuit.measure_all()

# Define backend
backend = AerSimulator()

# Transpile to backend
pm = generate_preset_pass_manager(backend=backend, optimization_level=1)
isa_qc = pm.run(grover_circuit)

# Run the job
sampler = Sampler(backend)
job = sampler.run([isa_qc])
result = job.result()

# Print the results
counts = result[0].data.meas.get_counts()
print(counts)

# Plot the counts in a histogram
plot_histogram(counts)
{'0110': 127, '0000': 135, '0001': 150, '0101': 164, '0010': 153, '0011': 131, '0100': 150, '0111': 14}

Output of the previous code cell

∣0111⟩|0111\rangle이 가장 낮은 확률로 관측되며, 정답을 얻을 확률이 더욱 감소했습니다. 이를 통해 Grover 알고리즘에서 최적의 결과를 얻기 위해 반복 횟수를 적절히 선택하는 것이 얼마나 중요한지 알 수 있습니다.

# See the version of Qiskit
import qiskit

qiskit.__version__
'2.0.2'
출처: IBM Quantum docs — 2026년 6월 10일 업데이트
doQumentation의 영어 버전 — 2026년 6월 10일 업데이트
사이트 또는 번역 문제?콘텐츠 문제? IBM Quantum docs에서 편집