제5장. 그로버의 검색 알고리즘

4장의 쇼어(Shor) 알고리즘은 ’주기성’이라는 구조화된(structured) 문제에서 지수적 속도 향상을 보여주었습니다. 하지만 만약 문제가 ’주기’와 같은 특별한 구조가 없다면 어떨까요?

전화번호부에서 이름을 찾아 전화번호를 찾는 것은 빠릅니다(구조화된 검색). 하지만 전화번호로 이름을 찾는 것은, 처음부터 끝까지 하나씩 다 확인하는 수밖에 없습니다(비구조화된 검색). 고전적으로 \(N\)개의 항목이 있는 비구조화된 데이터베이스를 검색하려면 평균 \(N/2\)번, 최악의 경우 \(N\)번의 확인이 필요합니다.

1996년 로브 그로버(Lov Grover)는 양자 컴퓨터가 이 비구조화된(unstructured) 검색 문제를 단 \(O(\sqrt{N})\)번의 오라클 호출만으로 풀 수 있음을 보였습니다. 이는 지수적 속도 향상은 아니지만, \(N\)이 매우 클 때(예: \(N=1조\)) \(O(N)\)을 \(O(\sqrt{N})\) (1조 vs 100만)으로 바꾸는 강력한 2차(quadratic) 속도 향상입니다.

이 알고리즘의 핵심 원리는 ‘정답’ 상태의 진폭을 증폭(Amplitude Amplification)시키는 것입니다.

1. 기본 개념 (Fundamental Concepts)

비구조화된 검색 문제: \(N=2^n\)개의 항목이 담긴 블랙박스(오라클)가 있습니다. 이 중 단 하나의 항목(\(w\))이 ‘표시된(marked)’ 항목입니다. 우리는 이 \(w\)를 찾아야 합니다.
- 오라클 함수: \(f(x)\)는 \(x=w\)일 때 \(f(w)=1\)이고, \(x \neq w\)일 때 \(f(x)=0\)입니다.
그로버 오라클 (\(U_w\)): 2장의 도이치 알고리즘처럼, 오라클은 답을 직접 알려주지 않고 ’위상 반동(Phase Kickback)’을 이용해 답을 표시합니다. \[U_w |x\rangle = (-1)^{f(x)} |x\rangle\]
- 작용: 오라클은 ‘표시된’ 항목 \(|w\rangle\)의 위상만 \(-1\)로 뒤집고, 나머지 항목들은 그대로 둡니다.
  - \(|w\rangle \quad \xrightarrow{U_w} \quad -|w\rangle\)
  - \(|x\rangle \quad \xrightarrow{U_w} \quad |x\rangle \quad (\text{if } x \neq w)\)
- 이는 기하학적으로 \(|w\rangle\) 벡터에 수직인 초평면을 기준으로 모든 벡터를 반사(reflection)시키는 연산입니다.
진폭 증폭 (Amplitude Amplification): 그로버 알고리즘의 핵심 전략입니다.
1. 시작: \(H\) 게이트를 이용해 모든 \(N\)개 항목의 진폭이 \(1/\sqrt{N}\)로 동일한 균등 중첩 상태 \(|s\rangle\)에서 시작합니다.
2. 반전: 오라클 \(U_w\)를 적용하여 정답 \(|w\rangle\)의 진폭만 \(-1/\sqrt{N}\)으로 뒤집습니다.
3. 증폭: ’그로버 확산 연산자(\(U_s\))’를 적용하여, 모든 진폭들을 평균값(\(\mu\))을 기준으로 뒤집습니다(Inversion about the mean).
4. 결과: 음수였던 \(|w\rangle\)의 진폭은 평균보다 훨씬 위로 솟아오르고, 양수였던 다른 항목들의 진폭은 조금씩 낮아집니다.
5. 이 과정을 \(O(\sqrt{N})\)번 반복합니다.
그로버 확산 연산자 (\(U_s\)): ’평균에 대한 반전’을 수행하는 연산자입니다. \(U_s = 2|s\rangle\langle s| - \mathbf{1}\)
- \(|s\rangle = H^{\otimes n}|0\rangle^{\otimes n}\) (균등 중첩 상태)
- \(U_s\)는 모든 진폭 \(a_i\)를 \(a_i \to 2\mu - a_i\) (단, \(\mu = \frac{1}{N}\sum_i a_i\))로 변환합니다.

2. 기호 및 핵심 관계식

그로버 반복 (Grover Iterate) \(G\): 알고리즘의 핵심 반복 단계(Iteration)는 오라클과 확산 연산자의 연속 적용입니다. \[G = U_s U_w\]
핵심 상태 정의: 알고리즘의 전 과정은 2차원 평면에서 일어나는 회전으로 완벽하게 기술될 수 있습니다. 이 평면을 구성하는 두 축은 다음과 같습니다.
- ‘정답’ 상태 (marked state): \(|w\rangle\)
- ‘오답’ 상태 (unmarked states): \(|\alpha\rangle = \frac{1}{\sqrt{N-1}}\sum_{x \neq w} |x\rangle\)
- 시작 상태 (uniform state): \(|s\rangle = \frac{1}{\sqrt{N}}\sum_{x} |x\rangle = \sqrt{\frac{N-1}{N}}|\alpha\rangle + \sqrt{\frac{1}{N}}|w\rangle\)
기하학적 해석 (Geometrical Interpretation):
- \(|s\rangle = \cos(\theta)|\alpha\rangle + \sin(\theta)|w\rangle \quad\) (단, \(\sin(\theta) = 1/\sqrt{N}\))
- \(\theta\)는 \(|s\rangle\)와 ‘오답’ 축 \(|\alpha\rangle\) 사이의 초기 각도이며, \(N\)이 크면 매우 작습니다.
- \(U_w\) = \(|\alpha\rangle\) 축에 대한 반사(Reflection)
- \(U_s\) = \(|s\rangle\) 축에 대한 반사(Reflection)
- \(G = U_s U_w\): 두 번의 반사는 회전과 같습니다. \(G\)는 상태 벡터를 \(|w\rangle\) 방향으로 \(2\theta\)만큼 회전시킵니다.
최적 반복 횟수 (\(k\)): 초기 각도 \(\theta\)에서 시작하여 ‘정답’ 축 \(|w\rangle\)(각도 \(90^\circ = \pi/2\))에 가장 가까이 가려면, \(k(2\theta) \approx \pi/2 \implies k \approx \frac{\pi}{4\theta}\) \(N\)이 매우 클 때, \(\sin(\theta) \approx \theta \approx 1/\sqrt{N}\) 이므로, \[k \approx \frac{\pi}{4}\sqrt{N}\]

3. 손쉬운 예제 (Examples with Deeper Insight)

예제 1: N=4 (n=2) - 단 한 번의 반복

문제: \(N=4\) (\(|00\rangle, |01\rangle, |10\rangle, |11\rangle\)) 중, \(|11\rangle\)이 정답(\(w\))입니다.
최적 횟수: \(k \approx \frac{\pi}{4}\sqrt{4} = \pi/2 \approx 1.57\). 따라서 \(k=1\) (단 1회 반복)이 최적입니다.
계산 (단계별):
1. 시작 \(|s\rangle\): (모든 진폭 \(1/2\)) \(|s\rangle = \frac{1}{2}(|00\rangle + |01\rangle + |10\rangle + |11\rangle)\)
2. 오라클 \(U_w\): \(|11\rangle\)의 위상만 뒤집습니다. \(|\psi_1\rangle = \frac{1}{2}(|00\rangle + |01\rangle + |10\rangle - |11\rangle)\)
3. 확산 \(U_s\) (평균 반전):
  - 평균 계산: \(\mu = \frac{1}{4} (1/2 + 1/2 + 1/2 - 1/2) = \frac{1}{4}(1) = 1/4\).
  - 반전 (\(a_i \to 2\mu - a_i\)):
    - \(|00\rangle\): \(2(1/4) - (1/2) = 0\)
    - \(|01\rangle\): \(2(1/4) - (1/2) = 0\)
    - \(|10\rangle\): \(2(1/4) - (1/2) = 0\)
    - \(|11\rangle\): \(2(1/4) - (-1/2) = 1/2 + 1/2 = 1\)
4. 최종 상태 \(|\psi_2\rangle\): \(|\psi_2\rangle = 0|00\rangle + 0|01\rangle + 0|10\rangle + 1|11\rangle = |11\rangle\)
💡 상세 설명 (100% 확률): > 단 1회의 반복(\(G\))으로, 모든 항목에 균등했던 확률(\(P_i=25\%\))이 정답인 \(|11\rangle\)에 100%로 증폭되었습니다. 측정을 하면 항상 \(|11\rangle\)을 얻습니다. \(N=4\)의 경우, 고전적으로 평균 2.25회(\(N/2+...\)) 필요한 검색을 단 1회 만에 완료했습니다.

예제 2: 기하학적 해석 (N=4)

상황: 예제 1을 2차원 회전으로 해석해 봅시다.
축 정의:
- \(|w\rangle = |11\rangle\)
- \(|\alpha\rangle = \frac{1}{\sqrt{3}}(|00\rangle + |01\rangle + |10\rangle)\) (‘오답’ 축)
각도 계산:
- \(|s\rangle = \sqrt{\frac{3}{4}}|\alpha\rangle + \sqrt{\frac{1}{4}}|w\rangle = \cos(\theta)|\alpha\rangle + \sin(\theta)|w\rangle\)
- \(\sin(\theta) = 1/\sqrt{4} = 1/2 \implies \theta = 30^\circ\) (\(\pi/6\)).
회전:
1. 시작: 상태 벡터는 \(|\alpha\rangle\) 축에서 \(\theta=30^\circ\)만큼 떨어진 \(|s\rangle\)에 있습니다.
2. \(U_w\) (오라클): \(|\alpha\rangle\) 축(\(x\)축)에 대해 반사합니다. 각도는 \(-\theta = -30^\circ\)가 됩니다.
3. \(U_s\) (확산): \(|s\rangle\) 축(원래 \(30^\circ\) 축)에 대해 반사합니다.
4. 최종 각도: 새 각도 = (축 각도) + (축 각도 - 현재 각도) \(= 30^\circ + (30^\circ - (-30^\circ)) = 30^\circ + 60^\circ = 90^\circ\).
💡 상세 설명:

최종 각도는 \(90^\circ\)입니다. \(90^\circ\)는 \(|\alpha\rangle\) 축과 수직이며, 이는 곧 \(|w\rangle\) 축과 같습니다. 상태 벡터가 정확히 \(|w\rangle\)로 회전했음을 기하학적으로 완벽하게 확인했습니다. 이 예제는 그로버의 두 연산자 \(U_w\)와 \(U_s\)가, \(|\alpha\rangle\)와 \(|w\rangle\)로 구성된 2D 평면에서 상태 벡터를 \(2\theta\)만큼 회전시키는 회전 연산자 \(G\)로 작동함을 명확히 보여줍니다.

예제 3: 너무 많이 반복하는 경우 (Over-Iteration)

질문: \(k \approx \frac{\pi}{4}\sqrt{N}\)번 반복해야 한다면, \(2k\)번 반복하면 더 좋은 것 아닌가요?
답: 아닙니다. 정답을 ‘지나치게’ 됩니다.
상황: \(N=4\) (예제 1)에서 \(k=1\)이 최적(\(90^\circ\))이었습니다. 만약 \(k=2\)번 반복하면 어떻게 될까요?
1. \(k=1\) 후 상태: \(|11\rangle\) (각도 \(90^\circ\))
2. \(U_w\) 적용: \(U_w|11\rangle = -|11\rangle\) (각도 \(-90^\circ\) 또는 \(270^\circ\))
3. \(U_s\) 적용: \(|11\rangle\)는 \(|\alpha\rangle\)와 \(|s\rangle\)의 선형 결합으로 다시 표현해야 합니다…
기하학적 해석 (더 쉬움): \(k=1\)회 반복 시 \(2\theta = 60^\circ\) 회전하여 \(30^\circ \to 90^\circ\)가 됩니다. \(k=2\)회 반복 시 \(2\theta = 60^\circ\) 더 회전하여 \(90^\circ \to 150^\circ\)가 됩니다. \(k=3\)회 반복 시 \(2\theta = 60^\circ\) 더 회전하여 \(150^\circ \to 210^\circ\) (\(-\theta = -30^\circ\)와 거의 동일)가 됩니다.
💡 상세 설명: > 2회 반복 후(\(150^\circ\)), 상태 벡터는 \(|w\rangle\) 축(\(90^\circ\))에서 \(60^\circ\)나 벗어났습니다. 이때 측정하면 \(|w\rangle\)를 찾을 확률 \(P(w) = \sin^2(150^\circ) = (1/2)^2 = 25\%\)로, 오히려 초기 상태(\(25\%\))와 같아집니다! > 3회 반복하면(\(210^\circ\)), \(P(w) = \sin^2(210^\circ) = (-1/2)^2 = 25\%\)입니다. > 그로버 알고리즘은 ’정답’에 도달했을 때 멈춰야 하는 섬세한 알고리즘입니다. 최적의 반복 횟수를 알아내려면 \(N\)(전체 항목 수)을 미리 알고 있어야 합니다.

4. 연습문제

확산 연산자 구축: \(U_s = 2|s\rangle\langle s| - \mathbf{1}\) 연산자를 \(H, X, Z\) 게이트를 이용해 어떻게 양자 회로로 구현할 수 있을지 \(U_s = H^{\otimes n} (2|0\rangle\langle 0| - \mathbf{1}) H^{\otimes n}\) 항등식을 이용해 설명하십시오.
최적 횟수 계산: \(N=1,000,000\)개의 항목이 있는 데이터베이스에서 정답을 찾으려면 그로버 알고리즘을 약 몇 번 반복해야 합니까? 고전적 방법과 비교하십시오.
다중 해 (Multiple Items): 만약 \(N\)개 중 \(M\)개의 항목이 ‘정답’이라면, 초기 상태 \(|s\rangle\)에서 정답 상태 부분(\(|w\rangle\) 대신 ’정답 부분공간’)이 차지하는 진폭의 제곱(확률)은 얼마입니까?
\(N=2\) 검색: \(N=2\) (\(|0\rangle, |1\rangle\)) 시스템에서 \(|1\rangle\)을 찾는 그로버 알고리즘을 1회 실행하면 어떻게 되는지 계산해보십시오. (힌트: \(\theta\)는?)
쇼어 vs 그로버: 쇼어 알고리즘과 그로버 알고리즘의 속도 향상(지수적 vs 2차)과, 그들이 해결하는 문제의 유형(구조적 vs 비구조적)을 비교 설명하십시오.

5. 해설

\(U_s = H^{\otimes n} (2|0\rangle\langle 0| - \mathbf{1}) H^{\otimes n}\) 입니다.
- \(H^{\otimes n}\) (하다마드)는 \(|s\rangle\)를 \(|0\rangle^{\otimes n}\)으로 변환합니다.
- \((2|0\rangle\langle 0| - \mathbf{1})\) 연산자는 \(|0\rangle\) 상태는 그대로 두고, \(|0\rangle\)과 직교하는 모든 다른 상태(\(|x\rangle \neq |0\rangle\))의 위상을 \(-1\)로 뒤집습니다. (이는 \(Z\) 게이트를 \(n-1\)개의 제어 큐빗으로 제어하는 C…CZ 게이트와 \(X\) 게이트의 조합으로 구현 가능합니다.)
- \(H^{\otimes n}\) (하다마드)를 다시 적용하여 \(|0\rangle^{\otimes n}\)을 \(|s\rangle\)로 되돌립니다.
- 결과적으로 이 전체 연산은 \(|s\rangle\) 상태를 축으로 하는 반사를 수행합니다.
고전적: 평균 \(N/2 = 500,000\)회. 최악 \(N = 1,000,000\)회. 양자: \(k \approx \frac{\pi}{4}\sqrt{N} = \frac{\pi}{4}\sqrt{1,000,000} = \frac{\pi}{4}(1000) \approx 785\)회. 약 785회면 충분하며, 이는 고전적 평균 횟수보다 600배 이상 빠릅니다.
\(|s\rangle = \frac{1}{\sqrt{N}}\sum |x\rangle\). \(M\)개의 정답이 있으므로, \(|s\rangle\)에서 정답 부분공간이 차지하는 총 진폭 제곱(확률)은 \(M \times |1/\sqrt{N}|^2 = M/N\) 입니다. (즉, \(\sin^2(\theta) = M/N\))
\(N=2\). \(\sin(\theta) = 1/\sqrt{2} \implies \theta = 45^\circ\) (\(\pi/4\)). 회전 각도 \(2\theta = 90^\circ\) (\(\pi/2\)). 초기 각도 \(\theta=45^\circ\)에서 \(90^\circ\)를 회전하면 최종 각도는 \(135^\circ\)가 됩니다. \(P(w) = \sin^2(135^\circ) = (1/\sqrt{2})^2 = 1/2\). 초기 확률 \(50\%\)에서 \(50\%\)로 전혀 증폭되지 않습니다. \(N=2\)에서는 그로버 알고리즘이 이득이 없습니다.
쇼어: ‘주기 찾기’라는 구조적 문제를 풉니다. \(O(e^n) \to O(n^3)\)로 지수적 속도 향상을 제공합니다. 그로버: ’비구조적 검색’ 문제를 풉니다. \(O(N) \to O(\sqrt{N})\) (즉, \(O(2^n) \to O(2^{n/2})\))로 2차(quadratic) 속도 향상을 제공합니다.