Yangja Wiki / 알고리즘

Grover

Grover 알고리즘은 비정렬 탐색에서 정답 상태의 진폭을 반복적으로 키웁니다. 핵심은 oracle reflection과 diffusion reflection을 번갈아 적용하는 amplitude amplification입니다.

문제 설정

크기 N=2^n인 탐색공간에서 정답 집합 M을 찾습니다. 오라클은 정답이면 1을 반환합니다.

$$
f(x)=
\begin{cases}
1 & x\in M\\
0 & x\notin M
\end{cases}
$$

Phase oracle

Grover에서는 보통 정답 상태의 부호만 뒤집는 phase oracle을 씁니다.

$$
O_f|x\rangle=(-1)^{f(x)}|x\rangle
$$

정답 진폭은 음수로, 오답 진폭은 그대로 남습니다. 이 자체로 확률은 변하지 않지만 diffusion과 결합하면 정답 진폭이 커집니다.

Diffusion operator

diffusion은 평균에 대한 반사입니다.

$$
D=2|s\rangle\langle s|-I,
\qquad
|s\rangle={1\over\sqrt{N}}\sum_x |x\rangle
$$

진폭 관점에서는 각 진폭 a_x를 평균 \bar a에 대해 반사합니다.

$$
a_x \mapsto 2\bar a-a_x
$$

2차원 기하

정답 상태들의 균등중첩을 |w\rangle, 오답 상태들의 균등중첩을 |r\rangle라 두면 전체 과정은 이 2차원 평면에서의 회전입니다.

$$
|s\rangle
=
\sin\theta |w\rangle+\cos\theta |r\rangle,
\qquad
\sin^2\theta={|M|\over N}
$$

Grover iteration G=DO_f를 한 번 적용할 때마다 각도가 대략 2\theta씩 정답 방향으로 회전합니다.

$$
G^k|s\rangle
=
\sin((2k+1)\theta)|w\rangle
+\cos((2k+1)\theta)|r\rangle
$$

반복 횟수

정답이 하나라면 \sin\theta=1/\sqrt{N}이고 최적 반복 횟수는 대략 아래입니다.

$$
k \approx {\pi\over4}\sqrt{N}-{1\over2}
$$

너무 많이 반복하면 정답 진폭을 지나쳐 다시 작아집니다. Grover는 “많이 돌릴수록 좋다”가 아니라 “적절한 회전 각도에서 멈춰야 한다”는 알고리즘입니다.

작은 예제

2큐비트에서 정답이 |11\rangle 하나라면 초기 진폭은 모두 1/2입니다. oracle 뒤 진폭은 아래처럼 됩니다.

$$
\left({1\over2},{1\over2},{1\over2},{1\over2}\right)
\mapsto
\left({1\over2},{1\over2},{1\over2},-{1\over2}\right)
$$

평균은 1/4이고 diffusion을 적용하면 정답 진폭은 1, 나머지는 0이 됩니다.

오답 진폭은 왜 destructive하게 줄어드는가

Grover의 oracle은 정답 상태의 부호만 뒤집습니다. 이 순간만 보면 확률은 변하지 않습니다. 부호가 바뀌어도 진폭의 절댓값 제곱은 그대로이기 때문입니다. 중요한 변화는 그 다음 diffusion에서 생깁니다.

diffusion은 모든 진폭을 평균 \bar a에 대해 반사합니다.

$$
a_x' = 2\bar a-a_x
$$

oracle 뒤에는 정답 진폭 하나가 음수가 되어 전체 평균을 아래로 끌어내립니다. 그러면 오답 진폭 a_{\mathrm{wrong}}은 평균보다 훨씬 위에 있게 되고, 평균에 대한 반사를 거치며 작아집니다. 반대로 정답 진폭은 음수 쪽에 있으므로 반사 후 크게 양수 쪽으로 이동합니다.

이 과정을 간섭 관점에서 말하면, diffusion 회로의 Hadamard 층은 여러 basis 경로를 다시 섞습니다. 오답 상태로 도달하는 경로들의 phase는 서로 부분적으로 상쇄되어 destructive interference를 만들고, 정답 상태로 도달하는 경로들은 같은 방향으로 더해져 constructive interference를 만듭니다. 그래서 Grover는 정답을 직접 복사해서 키우는 알고리즘이 아니라, 오답으로 가는 진폭을 상쇄시키면서 정답 방향으로 진폭을 재분배하는 알고리즘입니다.

한계

Grover는 quadratic speedup입니다. 지수 속도향상은 아니지만, 비정렬 탐색에서는 일반적인 양자 query lower bound와 맞아 최적입니다. 실제 장비에서는 oracle 구현 비용과 오류 누적이 전체 성능을 좌우합니다.

진폭 표로 보는 한 번의 반복

4개 상태 중 정답이 하나인 경우를 표로 보면 Grover의 동작이 더 분명합니다.

단계오답 진폭정답 진폭설명
초기1/21/2균등중첩
oracle 후1/2-1/2정답만 부호 반전
diffusion 후01평균에 대한 반사

이 작은 경우에는 한 번의 반복으로 정답 확률이 1이 됩니다.

정답이 여러 개인 경우

정답 수가 m개이면 초기 정답 부분공간의 확률은 m/N입니다.

$$
\sin^2\theta={m\over N}
$$

반복 횟수는 대략 아래입니다.

$$
k\approx {\pi\over4}\sqrt{N\over m}-{1\over2}
$$

정답 수가 애매하면 반복 횟수를 바꿔가며 실행하거나 quantum counting으로 m을 추정하는 전략이 필요합니다.

설계 주의점

  • oracle이 비싸면 Grover의 이점이 줄어듭니다.
  • diffusion은 전체 상태에 대한 반사라 n큐비트 제어 연산으로 구현됩니다.
  • NISQ에서는 반복 횟수가 늘수록 오류 누적으로 정답 진폭이 기대만큼 커지지 않을 수 있습니다.

Diffusion을 회로로 구현하기

수식 D=2|s\rangle\langle s|-I는 회로에서는 보통 아래처럼 구현합니다.

$$
D
=
H^{\otimes n}
\left(2|0^n\rangle\langle 0^n|-I\right)
H^{\otimes n}
$$

왜냐하면 H^{\otimes n}|0^n\rangle=|s\rangle이기 때문입니다. 가운데 연산은 |0^n\rangle에 대해서만 부호를 다르게 주는 multi-controlled phase입니다.

$$
2|0^n\rangle\langle 0^n|-I
=
\mathrm{diag}(1,-1,-1,\dots,-1)
$$

실제 회로에서는 전체 global phase가 측정에 영향을 주지 않으므로, |0^n\rangle이 아니라 나머지 또는 |1^n\rangle에 phase를 주는 동치 형태를 쓰기도 합니다. 핵심은 균등중첩 방향에 대한 reflection을 만드는 것입니다.

4큐비트 예제: 정답 하나의 첫 반복

n=4이면 N=16입니다. 정답이 하나라면 초기 모든 진폭은 1/4입니다. oracle 뒤에는 정답 하나만 -1/4가 됩니다.

$$
\bar a
=
{15(1/4)+(-1/4)\over 16}
=
{14\over64}
=
{7\over32}
$$

diffusion은 a_x\mapsto 2\bar a-a_x입니다. 따라서 오답 진폭과 정답 진폭은 아래처럼 바뀝니다.

$$
a_{\mathrm{wrong}}'
=
2\cdot {7\over32}-{1\over4}
=
{3\over16}
$$
$$
a_{\mathrm{right}}'
=
2\cdot {7\over32}-\left(-{1\over4}\right)
=
{11\over16}
$$

정답 확률은 (11/16)^2=121/256\approx0.473입니다. 시작 확률 1/16=0.0625에서 크게 올라갔지만 아직 1은 아닙니다. 그래서 N이 커질수록 여러 번 반복해야 합니다.

overshooting을 수식으로 보기

정답이 하나일 때 \theta\approx1/\sqrt{N}입니다. k번 반복 뒤 정답 확률은 아래입니다.

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

최대점은 (2k+1)\theta\approx\pi/2입니다. 이 지점을 지나치면 \sin^2가 다시 내려갑니다. Grover를 “정답을 계속 키우는 알고리즘”이라고만 기억하면 이 부분을 놓칩니다. 정확히는 2차원 평면에서 상태 벡터를 계속 회전시키는 알고리즘입니다.

오라클 비용이 실제 성능을 결정한다

Grover의 query complexity는 O(\sqrt{N/M})입니다. 하지만 오라클 하나가 매우 비싸면 전체 회로는 여전히 무거울 수 있습니다.

$$
\text{total cost}
\approx
k\cdot(\text{oracle cost}+\text{diffusion cost})
$$

예를 들어 SAT 문제를 Grover로 풀려면 “해인지 검사하는 회로”를 reversible oracle로 만들어야 합니다. 이 과정에서 AND, OR, NOT, comparator, uncompute, ancilla 관리가 들어갑니다. 이 비용을 무시하면 Grover가 모든 탐색 문제를 단순히 빠르게 해결해 주는 것처럼 보이지만, 실제 회로설계에서는 오라클이 본체입니다.

NISQ에서 Grover가 어려운 이유

Grover는 반복 알고리즘입니다. 반복이 많다는 것은 oracle과 diffusion을 계속 쌓는다는 뜻이고, 특히 diffusion의 multi-controlled phase는 2큐비트 게이트로 분해하면 깊이가 빠르게 늘어납니다.

잡음이 있는 장비에서는 이상적인 정답 진폭 증가와 실제 성공확률 증가가 다를 수 있습니다. 어떤 반복 횟수 이후에는 이론상으로는 확률이 더 올라가야 해도, 실제로는 누적 오류 때문에 측정 분포가 흐려질 수 있습니다. 그래서 NISQ 시대에는 “수학적으로 최적인 반복 횟수”와 “하드웨어에서 가장 잘 나오는 반복 횟수”가 다를 수 있습니다.