Grover 알고리즘

직관적 비유

자물쇠 번호 1,000개 중 하나를 맞춰야 한다고 하자. 고전 방식은 평균 500번 시도해야 하지만, Grover 알고리즘은 약 √1000 ≈ 32번 만에 정답을 찾는다. 마치 여러 문을 동시에 두드리되, 정답 문을 점점 밝게 조명해 나가는 과정과 같다.

엄밀한 정의

$N$개의 원소로 이루어진 비정렬 탐색 공간에서 하나의 정답 $\omega$를 찾는 문제를 다룬다. 알고리즘은 다음 두 연산을 $O(\sqrt{N})$회 반복한다.

1. 오라클(Oracle) $U_\omega$: 정답 상태의 위상을 반전 $|\omega\rangle \mapsto -|\omega\rangle$
2. 확산 연산자(Diffusion operator) $U_s = 2|s\rangle\langle s| - I$: 평균에 대한 위상 반전으로 정답 진폭을 증폭

초기 균등 중첩 상태 $|s\rangle = \frac{1}{\sqrt{N}}\sum_{x}|x\rangle$ 에서 출발하여 약 $\frac{\pi}{4}\sqrt{N}$회 반복 후 측정하면 정답을 높은 확률로 얻는다.

중요성 및 응용

• 이차 가속(Quadratic speedup): 고전 $O(N)$ → 양자 $O(\sqrt{N})$으로 증명된 최적 하한
• 범용성: 충족 가능성(SAT), 최적화, 암호 해독(AES 키 길이 사실상 절반) 등 다양한 분야에 서브루틴으로 활용
• NISQ 시대 적합성: 비교적 얕은 회로 깊이로 근미래 양자 하드웨어에서 시연 가능