Grover 알고리즘 — √N 비정형 탐색의 이차 가속

개념 소개

N개의 항목이 무작위로 나열된 데이터베이스에서 특정 조건을 만족하는 항목 하나를 찾는 비정형 탐색(unstructured search) 문제를 생각해보자. 항목에 어떠한 순서나 구조도 없으므로 고전 컴퓨터는 평균 N/2번, 최악의 경우 N번 확인해야 한다. 즉 고전적 쿼리 복잡도는 O(N)이다.

1996년 Lov Grover가 제안한 Grover 알고리즘은 동일한 문제를 단 O(√N)번의 오라클 쿼리로 해결한다. N = 100만이라면 고전 컴퓨터는 평균 50만 번 조회가 필요한 반면, Grover 알고리즘은 약 785번이면 충분하다. 이 **이차 가속(quadratic speedup)**은 지수적 가속인 Shor 알고리즘보다 극적이지는 않으나, 비정형 탐색에 대한 이론적 양자 하한(quantum lower bound)과 정확히 일치하는 최적 알고리즘이다.

---

핵심 원리

1단계 — 균등 중첩 준비

$N=2^n$으로 두고, n개의 큐비트 전부에 하다마드 변환 $H$를 적용한다.

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

모든 상태의 진폭이 동일하게 $1/\sqrt{N}$인 균등 중첩 상태 $|s⟩$이 출발점이다.

2단계 — 오라클 연산자 $U_f$

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

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

행렬 표현으로는 $U_f=I-2|\omega ⟩⟨\omega |$이다. 오라클은 정답을 직접 노출하지 않고 위상 킥백(phase kickback) 방식으로 정보를 인코딩한다.

3단계 — 확산 연산자 $D$ (Grover 확산)

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

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

모든 진폭의 평균 $\bar{a}$를 기준으로 각 진폭 $a_x$를 $2\bar{a}-a_x$로 대체한다. 오라클에 의해 홀로 음수가 된 목표 상태의 진폭은 이 연산을 거치면 크게 양의 방향으로 증폭된다.

Grover 반복과 반복 횟수

한 번의 Grover 반복 $G=D\cdot U_f$는 2차원 평면 $\text{span}\{|\omega ⟩,|{\omega }^{\perp }⟩\}$에서의 회전으로 해석된다. 초기 각도를 $\theta$라 하면 $\sin \theta =1/\sqrt{N}$이고, $k$번 반복 후 목표 상태를 측정할 확률은

$$P_k={\sin }^2((2k+1)\theta )$$

이 최대가 되는 반복 횟수는

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

이것이 O(√N) 복잡도의 정확한 근거다. 반복 횟수가 $k^{\ast }$를 초과하면 오히려 확률이 감소하므로, 적절한 시점에 측정을 멈춰야 한다.

---

예시·응용

2큐비트 예시 (N = 4)

목표 상태가 $|\omega ⟩=|11⟩$인 경우, $\theta =\arcsin (1/2)=\pi /6$이므로 $k^{\ast }=1$이다. 단 1번의 Grover 반복으로 측정 확률이 ${\sin }^2(3\pi /6)=1$에 도달한다. 아래는 Qiskit을 이용한 구현 예시다.

from qiskit import QuantumCircuit
from qiskit_aer import AerSimulator

def grover_2qubit():
    qc = QuantumCircuit(2, 2)

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

    # 2단계: 오라클 — |11> 위상 반전
    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])
    return qc

sim = AerSimulator()
result = sim.run(grover_2qubit(), shots=1024).result()
print(result.get_counts())  # 예상 출력: {'11': ~1024}

주요 응용 분야

• 조합 최적화: SAT 문제나 그래프 색칠 문제 등에서 고전 알고리즘 대비 이차 가속을 제공한다.
• 암호 분석: AES-128에 Grover 알고리즘을 적용하면 유효 키 강도가 64비트로 감소한다. 이것이 양자 내성 암호(post-quantum cryptography)에서 대칭키 길이를 두 배로 권고하는 이유다.
• 진폭 증폭 서브루틴: Grover 반복을 일반화한 진폭 증폭(amplitude amplification) 기법은 다양한 양자 알고리즘의 핵심 부품으로 활용된다.

---

정리

Grover 알고리즘의 핵심 구조는 ① 균등 중첩 초기화 → ② 오라클에 의한 위상 반전 → ③ 확산 연산자에 의한 진폭 증폭의 반복이다. 이 과정을 2차원 평면에서의 회전으로 이해하면 최적 반복 횟수 $k^{\ast }\approx \frac{\pi }{4}\sqrt{N}$이 자연스럽게 도출된다. 이차 가속은 지수적 가속에 비해 작아 보이지만, 비정형 탐색에 대해 이론적으로 달성 가능한 최선임이 증명되어 있으며 실용적으로도 N이 클수록 그 효과가 두드러진다.