Grover 알고리즘 — √N 비정형 검색의 원리와 구조

개념 소개

정렬되지 않은 N개 항목의 데이터베이스에서 특정 항목을 찾는 문제를 비정형 검색(unstructured search) 이라 한다. 고전 컴퓨터는 최악의 경우 N번, 평균 N/2번 조회를 거쳐야 하므로 시간 복잡도는 $O(N)$이다.

1996년 Lov Grover가 제안한 알고리즘은 양자 중첩과 진폭 증폭(amplitude amplification) 을 이용해 $O(\sqrt{N})$번의 오라클 호출만으로 동일한 문제를 해결한다. $n$개의 큐비트를 사용하면 $N=2^n$개 항목을 동시에 중첩 상태로 표현할 수 있다는 점이 출발점이 된다.

---

핵심 원리

1. 균일 중첩 초기화

$n$개의 큐비트 모두에 아다마르 게이트를 적용하면 모든 항목의 진폭이 균등한 중첩 상태가 만들어진다.

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

각 항목의 측정 확률은 $1/N$으로 동일하다.

2. 위상 오라클

목표 항목 $|w⟩$에 대해 위상 오라클 $U_f$는 목표의 진폭 부호만 반전시킨다.

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

부호 반전만으로는 측정 확률이 변하지 않는다. 이 정보를 활용하는 것이 다음 단계이다.

3. 확산 연산자 (평균 기준 반전)

Grover 확산 연산자 $D$는 현재 상태를 균일 중첩 $|{\psi }_0⟩$에 대해 반전시킨다.

$$D=2|{\psi }_0⟩⟨{\psi }_0|-I$$

오라클로 낮아진 목표 항목의 진폭이 평균 기준 반전(inversion about the mean) 에 의해 크게 증가하고, 나머지 항목의 진폭은 상대적으로 줄어든다. 이 과정을 반복할수록 목표 항목의 측정 확률이 점점 높아진다.

4. Grover 반복과 최적 횟수

$U_f$와 $D$를 한 쌍으로 묶은 한 사이클을 Grover 반복 $G=D\cdot U_f$라 한다.

기하학적으로 $G$는 2차원 부분 공간 $\{|{\psi }_0⟩,|w⟩\}$ 안에서의 회전이다. 초기 각도를

$$\sin \theta =\frac{1}{\sqrt{N}}$$

로 정의하면, $k$번 반복 후 목표 항목의 측정 확률은 ${\sin }^2((2k+1)\theta )$이다. 확률이 최대가 되는 최적 반복 횟수는 다음과 같다.

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

이보다 많이 반복하면 확률이 오히려 감소하므로 반복 횟수 선택에 주의가 필요하다.

---

예시·응용

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

$n=2$이면 $k^{\ast }\approx \frac{\pi }{4}\sqrt{4}=\frac{\pi }{2}\approx 1$회이다.

from qiskit import QuantumCircuit

qc = QuantumCircuit(2)

# 1단계: 균일 중첩
qc.h([0, 1])

# --- Grover 반복 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()

1회 반복 후 $|11⟩$의 측정 확률은 이론적으로 100%가 된다. 고전 방식이 평균 2.25회 조회를 필요로 하는 문제를 단 1회 오라클 호출로 해결한다.

해가 M개인 일반 경우

목표 항목이 $M$개이면 $\sin \theta =\sqrt{M/N}$으로 일반화되어 최적 횟수가 $k^{\ast }\approx \frac{\pi }{4}\sqrt{N/M}$이 된다. 해의 수가 많을수록 더 적은 반복으로 충분하다.

주요 응용 분야

분야	내용
대칭키 암호	AES 브루트 포스 복잡도 $O(2^n)\to O(2^{n/2})$로 절감
최적화	NP 완전 문제의 해 탐색 가속
양자 카운팅	해의 수 M을 $O(\sqrt{N})$에 추정
진폭 추정	Grover 구조를 일반화해 적분·기댓값 계산에 활용

---

정리

Grover 알고리즘은 위상 오라클로 목표 항목의 진폭 부호를 반전하고, 확산 연산자로 평균 기준 반전을 수행하는 두 연산을 약 $\frac{\pi }{4}\sqrt{N}$회 반복해 목표 항목의 측정 확률을 1에 가깝게 끌어올린다. 고전 알고리즘 대비 이차적 속도 향상이 비정형 검색의 이론적 하한이라는 점에서, 이 알고리즘은 양자 우위(quantum advantage)의 근거를 명확히 보여주는 대표 사례로 자리잡고 있다.