Grover 알고리즘 — √N 검색으로 이루는 이차 속도 향상

개념 소개

N개의 비정렬 데이터베이스에서 특정 항목을 고전적 방법으로 찾으려면 최악의 경우 N번, 평균적으로 N/2번의 조회가 필요하다. 1996년 Lov Grover가 제안한 Grover 알고리즘은 동일한 문제를 약 $\sqrt{N}$번의 양자 연산으로 해결한다.

예를 들어 $N=10^6$개의 항목 중 하나를 찾는 경우, 고전 알고리즘은 평균 500,000번의 조회가 필요하지만 Grover 알고리즘은 약 785번의 반복으로 동일한 결과를 얻는다. 이 이차 속도 향상(quadratic speedup) 은 N이 커질수록 그 효과가 더욱 두드러진다.

---

핵심 원리

Grover 알고리즘은 진폭 증폭(amplitude amplification) 기법을 사용한다. 두 가지 핵심 연산자가 교대로 작용한다.

오라클 연산자

찾고자 하는 정답 $x^{\ast }$에 해당하는 상태의 위상을 반전시킨다.

$$O|x⟩=(-1{)}^{f(x)}|x⟩$$

여기서 $f(x)=1$이면 $x=x^{\ast }$(정답), $f(x)=0$이면 나머지 경우다. 오라클은 정답 상태의 진폭 부호만 바꿀 뿐, 어느 항목이 정답인지를 직접 "알려주지" 않는다.

확산 연산자 (Grover 연산자)

오라클 적용 후 확산 연산자 $D$가 평균에 대한 반전(inversion about the mean) 을 수행한다.

$$D=2|\psi ⟩⟨\psi |-I$$

여기서 $|\psi ⟩=\frac{1}{\sqrt{N}}{\sum }_{x=0}^{N-1}|x⟩$는 균일 중첩 상태다. 이 연산은 각 상태의 진폭을 전체 평균에 대해 대칭 이동시켜, 오라클이 부호를 바꾼 정답 상태의 진폭을 크게 끌어올리고 나머지는 줄인다.

반복 횟수와 기하학적 해석

오라클과 확산 연산자를 한 쌍으로 묶은 것을 Grover 반복이라 하며, 최적 반복 횟수는 다음과 같다.

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

기하학적으로 보면, 초기 상태 $|\psi ⟩$와 정답 상태 $|x^{\ast }⟩$ 사이의 각도를 $\theta$라 할 때 $\sin \theta =1/\sqrt{N}$이 성립한다. 각 Grover 반복은 상태 벡터를 $2\theta$만큼 회전시키므로, $k\approx \pi /(4\theta )$번 반복하면 상태 벡터가 정답 방향과 거의 일치하게 된다. 반복을 과도하게 하면 오히려 진폭이 감소하므로, 적절한 시점에 측정해야 한다.

---

예시·응용

4원소 검색 예시 (N = 4)

$N=4$일 때 $k=\lfloor \pi /4\cdot \sqrt{4}\rfloor =1$번의 반복으로 정답을 확률 1로 찾는다. 큐비트 2개를 사용한 간단한 회로를 Qiskit으로 구성하면 다음과 같다.

from qiskit import QuantumCircuit

# 정답: |11〉 (인덱스 3)
qc = QuantumCircuit(2, 2)

# 1단계: 균일 중첩 생성 (H 게이트)
qc.h([0, 1])

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

# 3단계: 확산 연산자 (H → X → CZ → X → H)
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])

단 1회의 Grover 반복으로 $|11⟩$의 측정 확률이 100%로 상승한다.

주요 응용 분야

분야	내용
데이터베이스 검색	비정렬 데이터 O(N) → O(√N)
조합 최적화	SAT·그래프 문제에서 부분 가속
암호 분석	AES-128의 유효 보안 강도를 64비트로 낮추는 이론적 위협
양자 진폭 추정(QAE)	Grover 반복을 기반으로 한 확장 알고리즘

---

정리

Grover 알고리즘은 오라클과 확산 연산자를 $\lfloor \pi \sqrt{N}/4\rfloor$번 반복하여 비정렬 데이터베이스 검색의 이차 속도 향상을 달성한다. 이는 진폭 증폭 기법의 원형이며, 양자 컴퓨터가 제공하는 가장 기초적이고 실용적인 알고리즘 중 하나다. 단, 지수적이 아닌 이차적 속도 향상임을 명확히 구분해야 하며, 반복 횟수의 최적화가 성공 확률을 결정하는 핵심 설계 요소다.