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

개념 소개

비정렬 데이터베이스에서 특정 항목을 찾는 고전적 방법은 최악의 경우 N번 전체를 확인해야 하므로 O(N) 시간이 소요된다. 1996년 Lov Grover가 제안한 양자 알고리즘은 이를 O(√N)으로 단축한다. 예를 들어 100만 개 항목 중 하나를 찾는다면, 고전 컴퓨터는 평균 50만 번을 조회하지만 Grover 알고리즘은 약 1,000번(≈ √10⁶) 만으로 목표를 식별한다.

핵심 아이디어는 **진폭 증폭(amplitude amplification)**이다. 모든 항목에 균등하게 분포된 확률 진폭을, 목표 상태에만 집중되도록 반복적으로 재형성하는 것이다.

---

핵심 원리

1. 초기 상태 준비

$N=2^n$개 항목을 $n$개 큐비트로 표현한 뒤, Hadamard 변환을 전체 적용해 균등 중첩 상태를 만든다.

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

각 항목의 초기 진폭은 $1/\sqrt{N}$으로 동일하다.

2. 오라클 $U_{\omega }$

목표 상태 $|w⟩$의 위상만 반전시키는 유니터리 연산자다.

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

행렬 표현으로는 $U_{\omega }=I-2|w⟩⟨w|$이다. 오라클은 "이 항목이 정답인가?"를 판별하는 블랙박스로, 단 한 번의 쿼리로 동작한다.

3. 확산 연산자 $D$

오라클이 목표 위상을 뒤집은 후, 확산 연산자가 모든 진폭을 **평균에 대해 반전(inversion about the mean)**시킨다.

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

기하학적으로 해석하면, 오라클은 $|s⟩$와 $|w⟩$가 만드는 2차원 평면에서 $|w{⟩}^{\perp }$에 대한 반사를, 확산 연산자는 $|s⟩$에 대한 반사를 수행한다. 두 반사를 합치면 $|w⟩$ 방향으로의 회전이 된다.

4. 반복 횟수와 복잡도

$|s⟩$와 $|w⟩$ 사이의 각도를 $\theta$라 하면 $\sin \theta \approx 1/\sqrt{N}$이다. Grover 반복 한 번은 이 각도를 $2\theta$만큼 회전시키므로, 목표 상태 확률이 최대가 되려면

$$k\approx \frac{\pi }{4}\sqrt{N}$$

번 반복이 필요하다. 이때 측정하면 $|w⟩$를 높은 확률로 얻는다. 최적 횟수를 초과하면 확률이 다시 감소하므로 반복 횟수 선택이 중요하다.

---

예시·응용

2큐비트 예시 (N = 4, 목표: |11⟩)

최적 반복 횟수는 $\lfloor \pi /4\cdot \sqrt{4}\rfloor =1$회다.

from qiskit import QuantumCircuit

qc = QuantumCircuit(2)

# 균등 중첩
qc.h([0, 1])

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

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

qc.measure_all()
print(qc.draw('text'))

1회 반복 후 $|11⟩$의 측정 확률이 1(100%)에 수렴한다.

실제 활용 분야

분야	내용
조합 최적화	SAT, 그래프 채색 등의 해 탐색
암호해독	대칭키 암호의 유효 보안 강도를 절반으로 단축 (AES-128 → 64비트 수준)
패턴 검색	비정형 데이터 내 특정 패턴 탐색

---

정리

Grover 알고리즘은 오라클과 확산 연산자를 $\approx \sqrt{N}$회 반복하여 목표 상태의 진폭을 집중적으로 증폭한다. Shor 알고리즘처럼 지수 속도 향상은 아니지만, 비정렬 검색 문제에서의 이차 속도 향상은 이론적 최적임이 증명된 근본적 결과다. 이 원리는 진폭 증폭이라는 범용 기법으로 발전해 양자 머신러닝, 양자 최적화 등 다양한 알고리즘의 서브루틴으로 활용된다.