Grover 알고리즘: 비정렬 데이터베이스의 √N 양자 검색

개념 소개

N개 항목이 무작위로 나열된 목록에서 특정 항목 하나를 찾는다고 하자. 색인이 없으므로 고전적으로는 최악의 경우 N번, 평균적으로 N/2번 항목을 하나씩 확인해야 한다. Grover 알고리즘은 이 문제를 약 $\frac{\pi }{4}\sqrt{N}$번의 양자 연산으로 해결한다.

비유하자면, 고전 탐색은 열쇠 꾸러미에서 맞는 열쇠를 순서대로 꽂아보는 방식이다. Grover 알고리즘은 모든 열쇠를 동시에 시험하되, 맞는 열쇠만 점점 "밝게 빛나도록" 반복적으로 조명을 강화하는 방식에 가깝다.

핵심 원리

1. 초기화

$n={\log }_{2}N$개의 큐비트에 Hadamard 변환을 적용해 균일 중첩 상태를 만든다.

$$|s⟩=H^{\otimes n}|0{⟩}^{\otimes n}=\frac{1}{\sqrt{N}}\sum _{x=0}^{N-1}|x⟩$$

이 상태에서 목표 상태 $|\omega ⟩$의 초기 측정 확률은 $\frac{1}{N}$에 불과하다.

2. 오라클

오라클 $U_{\omega }$는 목표 상태의 위상만 반전시키는 단일 연산자다.

$$U_{\omega }=I-2|\omega ⟩⟨\omega |$$

$$U_{\omega }|x⟩=\{\begin{array}{ll}-|x⟩& x=\omega \\ |x⟩& x\ne \omega \end{array}$$

위상 반전만으로는 측정 확률이 바뀌지 않는다. 확산 연산자와의 결합이 핵심이다.

3. 확산 연산자

확산 연산자 $U_s$는 균일 중첩 상태 $|s⟩$에 대한 반사(inversion about the mean)를 수행한다.

$$U_s=2|s⟩⟨s|-I$$

이 연산은 각 상태의 진폭을 전체 평균을 기준으로 뒤집는다. 오라클이 목표 상태의 진폭을 평균 아래로 끌어내리면, 확산 연산자는 그것을 평균 위로 크게 끌어올린다.

4. 진폭 증폭과 반복 횟수

한 번의 Grover 반복은 $G=U_s\cdot U_{\omega }$로 정의된다. 기하학적으로 $G$는 $|s⟩$와 $|\omega ⟩$로 이루어진 2차원 평면에서의 회전이다. 초기 각도를 $\theta$로 정의하면 $\sin \theta =\frac{1}{\sqrt{N}}$이고, $k$번 반복 후 목표 상태가 측정될 확률은

$$P(\omega ,k)={\sin }^2((2k+1)\theta )$$

이다. 확률이 최대(≈ 1)가 되는 최적 반복 횟수는 $k^{\ast }\approx \frac{\pi }{4\theta }\approx \frac{\pi }{4}\sqrt{N}$이다.

예시·응용

N = 4 사례 (2큐비트)

$N=4$이면 $\theta =30°$이므로 단 1번의 Grover 반복으로 목표 상태를 확률 1에 근접해 찾을 수 있다.

아래는 Qiskit으로 $|\omega ⟩=|11⟩$을 목표로 하는 2큐비트 Grover 회로 예시다.

from qiskit import QuantumCircuit
from qiskit_aer import AerSimulator

qc = QuantumCircuit(2, 2)

# 1. 균일 중첩 초기화
qc.h([0, 1])

# 2. 오라클: |11>의 위상 반전 (CZ 게이트)
qc.cz(0, 1)

# 3. 확산 연산자
qc.h([0, 1])
qc.x([0, 1])
qc.cz(0, 1)
qc.x([0, 1])
qc.h([0, 1])

qc.measure([0, 1], [0, 1])

sim = AerSimulator()
result = sim.run(qc, shots=1024).result()
print(result.get_counts())
# 기대 출력: {'11': 1024} (또는 근접한 값)

응용 분야

분야	내용
암호 분석	대칭키 전수 조사 시 유효 키 길이 절반으로 감소 (이론적)
조합 최적화	SAT, 그래프 색칠 문제의 해 탐색 가속
양자 머신러닝	데이터 검색 서브루틴으로 활용

정리

Grover 알고리즘의 본질은 오라클(위상 반전)과 확산 연산자(평균에 대한 반사)를 $O(\sqrt{N})$회 반복해 목표 상태의 진폭을 선택적으로 증폭하는 것이다. 비정렬 탐색 문제에서 고전 O(N)에 대한 이차 가속은 양자역학이 허용하는 이론적 최대치임이 증명되어 있다. 지수 가속을 제공하는 Shor 알고리즘과 달리 이차 가속임을 유의해야 하며, 실용적 활용을 위해서는 오라클을 실제 문제에 맞게 효율적으로 구현하는 것이 관건이다.