Grover 알고리즘 — √N 검색과 진폭 증폭

개념 소개

N개의 항목이 담긴 비정렬(unstructured) 데이터베이스에서 특정 조건을 만족하는 항목을 찾는다고 하자. 고전 컴퓨터는 평균 N/2번, 최악의 경우 N번 확인해야 한다. Grover 알고리즘은 양자 중첩과 위상 간섭을 활용해 이 문제를 $O(\sqrt{N})$번의 질의만으로 해결한다.

$N=10^6$이라면 고전 방식은 평균 50만 번, Grover 알고리즘은 약 785번만에 목표를 찾는다. 이 **이차 가속(quadratic speedup)**은 비정렬 탐색에 대해 양자역학적으로 달성 가능한 최적 한계임이 증명되어 있다 — 그 이상의 가속은 원리적으로 불가능하다.

---

핵심 원리

1. 균등 중첩 초기화

n큐비트 레지스터($N=2^n$)에 Hadamard 게이트를 전체 적용한다.

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

목표 상태 $|w⟩$과 그 나머지의 균등 중첩 $|s^{\prime }⟩$로 분리하면

$$|{\psi }_0⟩=\frac{1}{\sqrt{N}}|w⟩+\sqrt{\frac{N-1}{N}}|s^{\prime }⟩$$

2. 오라클 (위상 반전)

오라클 $U_f$는 목표 상태의 위상만 $-1$로 반전한다.

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

오라클은 상태 벡터 공간에서 $|w⟩$에 수직인 초평면에 대한 반사에 해당한다.

3. 확산 연산자 — 평균값 기준 반전

확산 연산자(diffusion operator)는 균등 중첩 상태 $|{\psi }_0⟩$를 기준으로 반사한다.

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

직관적으로는 **평균값에 대한 반전(inversion about the mean)**이다. 오라클이 목표 진폭을 음수로 만들어 평균을 낮추면, 확산 연산자는 각 진폭을 평균 기준으로 대칭 이동시켜 목표 상태의 진폭만 크게 키운다.

4. 기하학적 해석과 최적 반복 횟수

$|w⟩$과 $|s^{\prime }⟩$이 이루는 2차원 평면에서 분석하면, 초기 상태 $|{\psi }_0⟩$와 $|s^{\prime }⟩$ 사이의 각도 $\theta$는

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

한 번의 Grover 반복 $G=D\cdot U_f$는 이 2차원 평면에서 $2\theta$만큼 회전한다. $k$번 반복 후 목표 상태의 진폭은

$$⟨w|{\psi }_k⟩=\sin ((2k+1)\theta )$$

이 값이 1이 되는 최적 반복 횟수는

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

이때 측정 성공 확률 $\approx 1$에 수렴한다.

---

예시·응용

N = 4 (2큐비트) 예시

목표 $|w⟩=|11⟩$, $\sin \theta =1/2$ 이므로 $\theta =\pi /6$, 최적 반복 횟수 $k^{\ast }=1$.

| 단계 | $|00⟩$ | $|01⟩$ | $|10⟩$ | $|11⟩$ | |------|:---:|:---:|:---:|:---:| | 초기화 | 1/2 | 1/2 | 1/2 | 1/2 | | 오라클 후 | 1/2 | 1/2 | 1/2 | −1/2 | | 확산 후 | 0 | 0 | 0 | 1 |

단 1회 반복으로 성공 확률 100%를 달성한다.

Qiskit 간단 구현

from qiskit import QuantumCircuit
import numpy as np

def grover_2qubit(target: str) -> QuantumCircuit:
    """2큐비트 Grover 회로. target: '00','01','10','11'"""
    qc = QuantumCircuit(2, 2)

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

    # 2. 오라클: 목표 상태에 위상 -1 적용
    if target == '11':
        qc.cz(0, 1)
    elif target == '00':
        qc.x([0, 1]); qc.cz(0, 1); qc.x([0, 1])
    elif target == '10':
        qc.x(1); qc.cz(0, 1); qc.x(1)
    elif target == '01':
        qc.x(0); qc.cz(0, 1); qc.x(0)

    # 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])

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

# 예시 실행
qc = grover_2qubit('11')
print(qc.draw())

응용 분야

• 암호 분석: AES 같은 대칭키 암호의 유효 안전 강도를 절반으로 감소 (128비트 → 64비트 수준)
• 최적화 및 SAT: 제약 충족 문제의 해 공간 탐색 가속
• 복수 해 탐색: 해의 개수가 $M$개일 때 최적 반복 횟수는 $\frac{\pi }{4}\sqrt{N/M}$
• 서브루틴 활용: 양자 위상 추정, 양자 워크 등 고급 알고리즘의 내부 구성요소로 사용

---

정리

Grover 알고리즘은 (1) 균등 중첩 초기화 → (2) 오라클 위상 반전 → (3) 확산 연산자에 의한 진폭 증폭을 약 $\frac{\pi }{4}\sqrt{N}$회 반복해 목표 상태를 높은 확률로 찾아낸다. 이차 가속은 비정렬 탐색에 대한 양자 하한임이 증명되어 있어, 이보다 빠른 양자 알고리즘은 존재하지 않는다. 알고리즘 자체의 응용 외에도 복잡한 양자 알고리즘의 서브루틴으로 광범위하게 활용된다.