Grover 알고리즘 — √N 비정렬 검색의 양자 가속

개념 소개

전화번호부에서 이름이 아닌 번호로 사람을 역검색하는 상황을 생각해 보자. 정렬 기준이 없으므로 고전적으로는 평균 N/2번, 최악 N번 항목을 확인해야 한다. 이것이 비정렬 검색(unstructured search) 문제다.

Grover 알고리즘(1996)은 이 문제를 $O(\sqrt{N})$ 번의 오라클 조회로 해결한다. N = 1,000,000이면 고전 방법은 평균 500,000번 조회가 필요하지만, Grover 알고리즘은 약 785번이면 충분하다. 이 제곱근 가속은 비정렬 검색에 대한 이론적 하한이기도 하여 더 이상 개선할 수 없음이 증명되어 있다.

---

핵심 원리

1. 균등 중첩 초기화

n큐비트($N=2^n$)를 모두 $|0⟩$으로 시작한 뒤 각 큐비트에 Hadamard 게이트를 적용하면 N개의 계산 기저 상태에 균등한 진폭을 부여한다.

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

목표 항목 $|w⟩$의 초기 진폭은 $1/\sqrt{N}$이고, 측정 확률은 $1/N$으로 매우 작다.

2. 오라클 연산자 $U_f$

오라클은 목표 상태에만 위상 $-1$을 곱하는 단위 연산자다.

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

블랙박스로 구현되며, 내부 탐색 기준을 회로 외부에서 인코딩한다.

3. Grover 확산 연산자 $U_s$

오라클이 위상을 뒤집은 뒤, 확산 연산자는 **현재 진폭 평균에 대한 반사(reflection about mean)**를 수행한다.

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

목표 상태의 진폭은 평균보다 낮으므로 반사 후 평균 위쪽으로 올라간다. 비목표 상태의 진폭은 상대적으로 낮아진다.

4. 반복 횟수

오라클 + 확산 연산자 한 쌍을 **Grover 반복(Grover iteration)**이라 부른다. 반복 횟수가 증가할수록 목표 상태의 확률이 올라가다가 최대점을 지나 다시 내려간다. 최적 반복 횟수는 다음과 같다.

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

이 횟수에서 목표 상태의 측정 확률은 $1-O(1/N)$에 근접한다.

기하학적 해석으로는, 초기 상태 $|s⟩$와 목표 $|w⟩$이 이루는 각도 $\theta$를 정의하면($\sin \theta =1/\sqrt{N}$) 각 반복이 $2\theta$씩 회전시켜 $k$번 후 총 각도가 $\pi /2$에 도달한다.

---

예시·응용

2큐비트 예시: $|11⟩$ 검색

N = 4, 목표 = $|11⟩$, 최적 반복 횟수 = 1회.

from qiskit import QuantumCircuit
from qiskit.primitives import Sampler

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

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

# 2) 오라클: |11>에만 위상 -1 부여 (CZ)
qc.cz(0, 1)

# 3) 확산 연산자: 2|s><s| - I
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])

sampler = Sampler()
result = sampler.run([qc], shots=1024).result()
print(result[0].data.c.get_counts())
# 예상 출력: {'11': ~1024}  (거의 확정적으로 11)

주요 응용 분야

분야	활용 예
암호해독	대칭키 키 공간 탐색 (AES 유효 안전성 절반 감소)
최적화	NP 문제의 지수 탐색 가속
양자 머신러닝	특징 공간 검색
SAT 솔버	변수 할당 탐색

---

정리

Grover 알고리즘은 (1) 균등 중첩 초기화, (2) 오라클로 목표 위상 반전, (3) 확산 연산자로 진폭 재분배를 $\lfloor \frac{\pi }{4}\sqrt{N}\rfloor$회 반복함으로써 비정렬 검색을 $O(\sqrt{N})$에 완료한다. 제곱근 가속은 지수 가속이 아니므로 RSA 암호 등 공개키 체계를 직접 파괴하지는 않으나, 대칭 암호 키 길이를 두 배로 늘려야 하는 실질적 보안 함의를 가진다. 진폭 증폭 기법은 이후 다양한 양자 알고리즘의 서브루틴으로 광범위하게 활용된다.