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

개념 소개

비정렬 데이터베이스에서 특정 항목을 찾으려면 고전 컴퓨터는 최악의 경우 $N$번, 평균적으로도 $O(N)$번 항목을 확인해야 한다. 1996년 Lov Grover가 제안한 알고리즘은 동일한 문제를 $O(\sqrt{N})$번의 오라클 호출로 해결한다. 이를 2차 가속(quadratic speedup) 이라 부른다.

예를 들어 $N=10^6$인 데이터베이스를 탐색한다면, 고전 방법은 평균 50만 번이 필요하지만 Grover 알고리즘은 약 785번의 연산으로 충분하다. 지수적 가속은 아니지만, 암호 해독·최적화·양자화학 등 다양한 분야에서 실질적 이점을 제공한다.

---

핵심 원리

초기 균등 중첩 상태

$n$큐비트 전체에 아다마르 변환을 적용해 $N=2^n$개의 상태를 균등하게 중첩시킨다.

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

이 시점에서 각 항목이 측정될 확률은 $1/N$으로 동일하다.

위상 오라클 (Phase Oracle)

목표 항목 $|w⟩$만 위상을 $-1$로 뒤집는 연산자 $O$를 정의한다.

$$O|x⟩=(-1{)}^{f(x)}|x⟩,f(x)=\{\begin{array}{ll}1& x=w\\ 0& \text{otherwise}\end{array}$$

진폭의 절댓값은 변하지 않고 부호만 바뀌기 때문에, 이 단계만으로는 측정 결과가 달라지지 않는다.

Grover 확산 연산자 (Diffusion Operator)

오라클 적용 후 평균에 대한 반전(inversion about the mean) 을 수행한다.

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

현재 진폭 평균을 $\mu$라 하면, 각 항목의 진폭 $a_x$는 $2\mu -a_x$로 갱신된다. 목표 항목이 위상 오라클에 의해 음수 진폭을 갖게 되었으므로, 반전 후 해당 항목의 진폭은 두드러지게 증가하고 나머지는 소폭 감소한다.

반복 횟수와 성공 확률

오라클 + 확산 연산자를 한 Grover 반복으로 보면, 최적 반복 횟수는 다음과 같다.

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

이때 목표 상태를 측정할 확률이 $1$에 근접한다. 반복을 과도하게 수행하면 진폭이 다시 감소하는 과회전(over-rotation) 이 발생하므로, 적정 횟수를 정확히 계산해야 한다.

---

예시·응용

2큐비트 예시 (N = 4)

4개의 기저 상태 $\{|00⟩,|01⟩,|10⟩,|11⟩\}$ 중 $|11⟩$을 찾는 경우, 최적 반복 횟수는 $k=1$이다. 아래는 Qiskit을 이용한 구현 예시다.

from qiskit import QuantumCircuit

# 2큐비트 Grover 회로 (목표: |11⟩)
qc = QuantumCircuit(2, 2)

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

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

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

# 4. 측정
qc.measure([0, 1], [0, 1])
print(qc.draw('text'))

이 회로를 시뮬레이션하면 $|11⟩$이 확률 1로 측정된다.

실용적 응용

분야	내용
대칭키 암호	AES-$n$비트 키를 $O(2^{n/2})$ 탐색으로 공격 — 유효 보안 강도가 절반으로 감소
NP 문제 탐색	해 공간을 √N 배 빠르게 브루트포스
양자화학	분자 에너지 최솟값 탐색 보조 루틴

---

정리

Grover 알고리즘은 위상 오라클로 목표 상태를 표시하고, 확산 연산자로 진폭을 증폭시키는 두 단계를 $\lfloor \frac{\pi }{4}\sqrt{N}\rfloor$회 반복해 $O(\sqrt{N})$ 탐색을 달성한다. BBBV 정리에 의해 이 복잡도는 비구조화 탐색의 양자 하한과 일치하므로, 이 유형의 문제에서 점근적으로 최적인 양자 알고리즘이다.