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

개념 소개

N개의 항목이 임의 순서로 저장된 데이터베이스에서 특정 정답 하나를 찾는다고 하자. 고전 컴퓨터는 하나씩 확인하는 방법 외에 달리 선택지가 없으므로 평균 N/2번, 최악 N번의 조회가 필요하다. 시간 복잡도는 O(N)이다.

1996년 Lov Grover가 제안한 Grover 알고리즘은 동일한 문제를 $O(\sqrt{N})$ 번의 연산으로 해결한다. $N=10^6$이라면 고전 탐색은 약 백만 번이 필요하지만, Grover 알고리즘은 약 1,000번으로 충분하다. 이 **제곱근 속도 향상(quadratic speedup)**은 N이 클수록 효과가 두드러진다.

알고리즘의 핵심 아이디어는 **진폭 증폭(amplitude amplification)**이다. 전체 상태를 균등 중첩으로 초기화한 뒤, 오라클과 확산 연산자를 반복 적용해 정답 상태의 진폭만 선택적으로 키운다.

---

핵심 원리

1단계: 균등 중첩 준비

$n$큐비트($N=2^n$)에 Hadamard 변환을 적용해 모든 기저 상태가 동등한 진폭 $1/\sqrt{N}$을 갖는 상태를 만든다.

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

2단계: 오라클(Oracle)

오라클 $U_f$는 정답 상태 $|\omega ⟩$의 위상만 반전시키고 나머지는 그대로 둔다.

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

행렬 형태로는 $U_f=I-2|\omega ⟩⟨\omega |$이다. 이 단계에서 측정 확률 분포는 아직 바뀌지 않는다.

3단계: 확산 연산자(Diffusion Operator)

확산 연산자 $D$는 **평균에 대한 반전(inversion about the mean)**을 수행한다.

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

진폭의 전체 평균을 $\bar{a}$라 할 때, 각 상태의 진폭 $a_x$는 $2\bar{a}-a_x$로 변환된다. 오라클로 인해 정답 상태의 진폭이 음수가 된 상황에서 이 연산을 적용하면, 정답 상태의 진폭은 크게 증가하고 나머지 상태의 진폭은 소폭 감소한다.

Grover 반복과 최적 횟수

한 번의 **Grover 반복(Grover iteration)**은 다음과 같다.

$$G=D\cdot U_f$$

$k$번 반복 후 정답을 측정할 확률은

$$P(\omega ,k)={\sin }^2\left((2k+1)\theta \right),\theta =\arcsin \left(\frac{1}{\sqrt{N}}\right)$$

$N$이 클 때 $\theta \approx 1/\sqrt{N}$이므로, 성공 확률이 최대가 되는 최적 반복 횟수는

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

이다. 이 횟수를 초과하면 성공 확률이 오히려 감소하므로 반복 횟수 조절이 중요하다.

---

예시·응용

N = 4인 경우 (2큐비트)

정답이 $|\omega ⟩=|11⟩$일 때, $k^{\ast }\approx \frac{\pi }{4}\sqrt{4}\approx 1.57$이므로 단 1번의 Grover 반복만으로 성공 확률이 1에 수렴한다.

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()
counts = sim.run(qc, shots=1024).result().get_counts()
print(counts)  # 기대 출력: {'11': ~1024}

정답이 M개인 경우

정답이 M개 존재하면 최적 반복 횟수는

$$k^{\ast }\approx \frac{\pi }{4}\sqrt{\frac{N}{M}}$$

으로 줄어든다.

주요 응용 분야

분야	내용
암호 해석	AES-128 브루트포스 복잡도를 $2^{128}$에서 $2^{64}$로 감소
조합 최적화	SAT·그래프 색칠 문제의 탐색 가속화
데이터베이스	비구조적 대규모 데이터 질의

---

정리

Grover 알고리즘은 비정렬 데이터베이스 검색의 고전적 O(N)을 양자적 O(√N)으로 개선하는 대표 양자 알고리즘이다. 오라클이 정답 상태의 위상을 반전하고, 확산 연산자가 평균에 대한 반전으로 해당 진폭을 증폭하는 두 단계를 $\approx \pi \sqrt{N}/4$번 반복하는 것이 전체 구조다. 이 제곱근 속도 향상은 양자 하한 이론에 의해 최적임이 증명되어 있어, 어떤 양자 알고리즘도 비정렬 탐색을 이보다 빠르게 수행할 수 없다.