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

개념 소개

N개의 원소가 담긴 정렬되지 않은 목록에서 특정 항목을 찾는다고 하자. 고전 컴퓨터는 최악의 경우 N번, 평균 N/2번을 확인해야 한다. 목록이 100만 개라면 평균 50만 번의 조회가 필요하다. Grover 알고리즘은 동일한 문제를 약 $\lfloor \frac{\pi }{4}\sqrt{N}\rfloor$번의 연산으로 해결한다. 같은 예시에서 단 약 785번이면 충분하다.

이 알고리즘의 속도 향상 원리는 고전적 무작위 탐색과 근본적으로 다르다. 양자 중첩으로 모든 후보를 동시에 펼친 뒤, 반복적인 위상 조작을 통해 정답 상태의 확률 진폭만을 선택적으로 키운다.

---

핵심 원리

초기화

n개의 큐비트 각각에 하다마르(Hadamard) 게이트를 적용해 균등 중첩 상태를 구성한다.

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

모든 기저 상태의 진폭은 $1/\sqrt{N}$으로 동일하다.

오라클 (Oracle)

정답 상태 $|w⟩$의 위상을 반전시키는 유니터리 연산자다.

$$O=I-2|w⟩⟨w|$$ $$O|x⟩=\{\begin{array}{ll}-|x⟩& (x=w)\\ |x⟩& (x\ne w)\end{array}$$

오라클은 정답을 판별하는 블랙박스 함수가 주어진다고 가정한다. 이 연산 자체는 정답을 "출력"하지 않고 위상만 바꾸기 때문에, 단독으로는 측정 결과에 영향을 주지 않는다.

확산 연산자 (Diffusion Operator)

"평균에 대한 반전(inversion about the mean)"으로 해석되는 연산자다.

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

오라클 적용 후 음수 진폭을 갖는 정답 상태가 평균 대비 크게 아래에 위치하며, D를 적용하면 평균을 기준으로 뒤집혀 정답 진폭은 크게 증가하고 나머지는 감소한다.

Grover 반복

한 번의 Grover 반복(iteration)은 $G=D\cdot O$로 정의된다. 기하학적으로 $G$는 2차원 평면 위에서 매 반복마다 $2\theta$씩 회전하는 연산이다 ($\sin \theta =1/\sqrt{N}$). 초기 상태 $|s⟩$가 정답 상태 $|w⟩$에 최대한 가까워질 때까지 반복하므로, 최적 횟수는 다음과 같다.

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

이를 초과하여 반복하면 오히려 확률이 감소하므로 적절한 시점에서 멈추는 것이 중요하다.

---

예시·응용

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

N=4일 때 최적 반복 횟수는 $\frac{\pi }{4}\sqrt{4}\approx 1.57$이므로 단 1번으로 정답 확률이 1에 도달한다.

from qiskit import QuantumCircuit
from qiskit_aer import AerSimulator

# 정답: |11⟩ (x = 3)
qc = QuantumCircuit(2, 2)

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

# 2. 오라클: CZ 게이트로 |11⟩ 위상 반전
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])

qc.measure([0, 1], [0, 1])

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

응용 분야

• 암호 분석: AES-128 대칭키의 유효 보안 강도를 이론적으로 절반(64비트)으로 줄일 수 있어, 양자 내성 암호 필요성의 근거가 된다.
• 조합 최적화: 후보 해 공간 탐색을 가속하는 서브루틴으로 활용된다.
• 진폭 증폭의 일반화: Grover 반복은 보다 일반적인 진폭 증폭(amplitude amplification) 기법으로 확장되어 다양한 양자 알고리즘의 핵심 구성 요소로 사용된다.

---

정리

Grover 알고리즘은 비정렬 검색 문제에 대해 고전 알고리즘 대비 이차함수적(quadratic) 속도 향상을 제공한다. 오라클로 정답 상태의 위상을 반전하고, 확산 연산자로 그 진폭을 증폭하는 과정을 $O(\sqrt{N})$번 반복하는 것이 전부다. 단, 이 속도 향상은 지수적이 아닌 이차적 개선임을 명확히 인식해야 하며, Shor 알고리즘의 지수적 속도 향상과는 성격이 다르다.