반복 횟수 선택

우리는 Grover 알고리즘에서 초기화 단계가 수행되면 레지스터 $\mathsf{Q}$의 상태 벡터가 $\vert A_0\rangle$과 $\vert A_1\rangle$이 생성하는 2차원 부분공간에 머무른다는 것을 확립했습니다.

목표는 원소 $x\in A_1$을 찾는 것이며, 이 목표는 상태 $\vert A_1\rangle$을 얻을 수 있다면 달성됩니다. 이 상태를 측정하면 측정 결과 $x\in A_1$을 얻는 것이 보장되기 때문입니다. 2단계에서 $t$번 반복 후의 $\mathsf{Q}$의 상태가

$$G^t \vert u \rangle = \cos\bigl((2t + 1)\theta\bigr) \vert A_0\rangle + \sin\bigl((2t + 1)\theta\bigr) \vert A_1\rangle,$$

이므로, 측정에서 $x\in A_1$을 얻을 확률을 극대화하기 위해

$$\langle A_1 \vert G^t \vert u \rangle = \sin((2t + 1)\theta)$$

의 절댓값이 가능한 한 $1$에 가깝도록 $t$를 선택해야 합니다. 임의의 각도 $\theta \in (0,2\pi)$에 대해, $t$가 증가함에 따라 값 $\sin((2t + 1)\theta)$는 진동하지만, 반드시 주기적인 것은 아닙니다. 즉, 같은 값을 두 번 얻는다는 보장은 없습니다.

당연히 측정에서 원소 $x\in A_1$을 얻을 확률을 크게 하는 것 외에도, $G$ 연산의 $t$번 적용에는 함수 $f$에 대한 $t$번의 쿼리가 필요하기 때문에 $t$를 가능한 한 작게 선택하고 싶습니다. $\sin( (2t + 1) \theta)$를 절댓값에서 $1$에 가깝게 만드는 것이 목표이므로, 이를 수행하는 자연스러운 방법은

$$(2t + 1) \theta \approx \frac{\pi}{2}.$$

가 되도록 $t$를 선택하는 것입니다.

$t$에 대해 풀면 다음을 얻습니다.

$$t \approx \frac{\pi}{4\theta} - \frac{1}{2}.$$

물론 $t$는 정수여야 하므로, 반드시 이 값에 정확히 도달할 수 있는 것은 아닙니다. 하지만 우리가 할 수 있는 것은 이 값에 가장 가까운 정수를 취하는 것이고, 그것은

$$t = \Bigl\lfloor \frac{\pi}{4\theta} \Bigr\rfloor.$$

입니다.

이것이 Grover 알고리즘에 권장되는 반복 횟수입니다. 분석을 진행하면서, 이 정수가 목표값에 얼마나 가까운지가 자연스럽게 알고리즘의 성능에 영향을 미친다는 것을 보게 될 것입니다.

(참고로, 목표값 $\pi/(4\theta) - 1/2$가 정확히 두 정수 사이의 중간에 있는 경우, 이 $t$의 표현은 반올림하여 얻는 것입니다. 대신 내림할 수도 있는데, 이는 한 번의 쿼리가 적다는 것을 의미하기 때문에 의미가 있습니다. 하지만 이것은 부차적이며 레슨에 있어 중요하지 않습니다.)

각도 $\theta$의 값이 다음 공식에 의해 주어진다는 것을 상기하면,

$$\theta = \sin^{-1}\biggl(\sqrt{\frac{\vert A_1\vert}{N}}\biggr),$$

권장되는 반복 횟수 $t$가 $A_1$의 문자열 수에 의존한다는 것을 알 수 있습니다. 이는 해의 개수를 모르는 경우 어려움을 제시하는데, 이는 나중에 논의하겠습니다.

Unique search

먼저 $f(x)=1$인 문자열 $x$가 단 하나 있는 상황에 집중해 봅시다. 이를 달리 말하면 Unique search 문제의 인스턴스를 고려하고 있다는 것입니다. 이 경우 다음을 얻습니다.

$$\theta = \sin^{-1}\biggl( \sqrt{\frac{1}{N}} \biggr),$$

이는 $N$이 커질 때 편리하게 다음과 같이 근사될 수 있습니다.

$$\theta = \sin^{-1}\biggl( \sqrt{\frac{1}{N}} \biggr) \approx \sqrt{\frac{1}{N}}$$

$\theta = 1/\sqrt{N}$을 식

$$t = \Bigl\lfloor \frac{\pi}{4\theta} \Bigr\rfloor$$

에 대입하면 다음을 얻습니다.

$$t = \Bigl\lfloor \frac{\pi}{4}\sqrt{N} \Bigr\rfloor.$$

$t$가 연산 $G$가 수행되는 횟수일 뿐만 아니라 알고리즘이 필요로 하는 함수 $f$에 대한 쿼리 횟수이기도 함을 상기하면, $O(\sqrt{N})$번의 쿼리를 필요로 하는 알고리즘을 얻는 과정에 있음을 알 수 있습니다.

이제 권장된 $t$의 선택이 얼마나 잘 작동하는지 조사해 봅시다. 최종 측정이 유일한 해를 산출할 확률은 명시적으로 다음과 같이 표현될 수 있습니다.

$$p(N,1) = \sin^2 \bigl( (2t + 1) \theta \bigr).$$

첫 번째 인수 $N$은 탐색하는 항목의 수를 나타내고, 이 경우 $1$인 두 번째 인수는 해의 수를 나타냅니다. 잠시 후 여러 해가 있는 경우에 대해 동일한 표기법을 더 일반적으로 사용할 것입니다.

$N = 2^n$ 값이 증가함에 따른 성공 확률의 표가 다음과 같습니다.

$$\begin{array}{ll} N & p(N,1)\\ \hline 2 & 0.5000000000\\ 4 & 1.0000000000\\ 8 & 0.9453125000\\ 16 & 0.9613189697\\ 32 & 0.9991823155\\ 64 & 0.9965856808\\ 128 & 0.9956198657\\ 256 & 0.9999470421\\ 512 & 0.9994480262\\ 1024 & 0.9994612447\\ 2048 & 0.9999968478\\ 4096 & 0.9999453461\\ 8192 & 0.9999157752\\ 16384 & 0.9999997811\\ 32768 & 0.9999868295\\ 65536 & 0.9999882596 \end{array}$$

이 확률들이 엄격히 증가하지 않는다는 점을 주목하세요. 특히, $N=4$일 때 흥미로운 이상 현상이 있는데, 확실하게 해를 얻습니다. 그러나 일반적으로 다음이 증명될 수 있습니다.

$$p(N,1) \geq 1 - \frac{1}{N}$$

모든 $N$에 대해서 말이며, 따라서 위의 값들이 시사하는 것처럼 $N$이 커짐에 따라 극한에서 성공 확률은 $1$로 수렴합니다. 이는 좋습니다!

그러나 $p(N,1) \geq 1/2$와 같은 약한 경계조차 Grover 알고리즘의 유용성을 입증한다는 점에 주목하세요. 절차를 실행하여 얻은 어떤 측정 결과 $x$에 대해서도, 우리는 항상 $f$에 대한 단일 쿼리를 사용하여 $f(x) = 1$인지 확인할 수 있습니다. 그리고 절차를 한 번 실행하여 $f(x) = 1$인 유일한 문자열 $x$를 얻는 데 실패할 확률이 최대 $1/2$라면, 절차를 독립적으로 $m$번 실행한 후 이 유일한 문자열 $x$를 얻는 데 실패할 확률은 최대 $2^{-m}$가 될 것입니다. 즉, $f$에 대한 $O(m \sqrt{N})$번의 쿼리를 사용하여, 최소 $1 - 2^{-m}$의 확률로 유일한 해 $x$를 얻을 것입니다. 더 나은 경계 $p(N,1) \geq 1 - 1/N$을 사용하면, 이 방법을 통해 $x\in A_1$을 찾을 확률이 실제로 최소 $1 - N^{-m}$이라는 것이 드러납니다.

여러 해가 있는 경우

$A_1$의 원소 수가 달라짐에 따라 각도 $\theta$도 달라지며, 이는 알고리즘의 성공 확률에 상당한 영향을 미칠 수 있습니다. 간결성을 위해 해의 개수를 나타내기 위해 $s = \vert A_1 \vert$이라고 쓰고, 이전과 같이 $s\geq 1$이라고 가정하겠습니다.

동기 부여 예로, 위에서 고려한 단일 해 대신 $s = 4$개의 해가 있다고 상상해 봅시다. 이는 다음을 의미합니다.

$$\theta = \sin^{-1}\biggl( \sqrt{\frac{4}{N}} \biggr),$$

이는 $N$이 클 때 $\vert A_1 \vert = 1$인 경우에 가졌던 각도의 대략 두 배입니다. 더 나은 정보가 없어서 유일한 해 설정에서와 동일한 $t$ 값을 선택했다고 가정합시다.

$$t = \Biggl\lfloor \frac{\pi}{4\sin^{-1}\bigl(1/\sqrt{N}\bigr)}\Biggr\rfloor.$$

다음 확률 표가 보여주듯이 그 영향은 참담할 것입니다.

$$\begin{array}{ll} N & \text{Success probability}\\ \hline 4 & 1.0000000000\\ 8 & 0.5000000000\\ 16 & 0.2500000000\\ 32 & 0.0122070313\\ 64 & 0.0203807689\\ 128 & 0.0144530758\\ 256 & 0.0000705058\\ 512 & 0.0019310741\\ 1024 & 0.0023009083\\ 2048 & 0.0000077506\\ 4096 & 0.0002301502\\ 8192 & 0.0003439882\\ 16384 & 0.0000007053\\ 32768 & 0.0000533810\\ 65536 & 0.0000472907 \end{array}$$

이번에는 $N$이 무한대로 감에 따라 성공 확률이 $0$으로 수렴합니다. 이는 해가 유일했을 때보다 사실상 두 배 빠르게 회전하고 있기 때문에, 목표 $\vert A_1\rangle$을 지나쳐 $-\vert A_0\rangle$ 근처에 도달하게 되는 것입니다.

그러나 대신 권장되는 $t$의 선택

$$t = \Bigl\lfloor \frac{\pi}{4\theta}\Bigr\rfloor$$

를

$$\theta = \sin^{-1}\biggl( \sqrt{\frac{s}{N}} \biggr),$$

에 대해 사용하면 성능이 더 좋아질 것입니다. 더 정확하게 말하자면, 이 $t$의 선택을 사용하면 높은 확률로 성공하게 됩니다.

$$\begin{array}{ll} N & p(N,4)\\ \hline 4 & 1.0000000000\\ 8 & 0.5000000000\\ 16 & 1.0000000000\\ 32 & 0.9453125000\\ 64 & 0.9613189697\\ 128 & 0.9991823155\\ 256 & 0.9965856808\\ 512 & 0.9956198657\\ 1024 & 0.9999470421\\ 2048 & 0.9994480262\\ 4096 & 0.9994612447\\ 8192 & 0.9999968478\\ 16384 & 0.9999453461\\ 32768 & 0.9999157752\\ 65536 & 0.9999997811 \end{array}$$

앞서 주장한 바를 일반화하면, 다음이 증명될 수 있습니다.

$$p(N,s) \geq 1 - \frac{s}{N},$$

여기서 앞서 제시한 표기법을 사용하고 있습니다. $p(N,s)$는 $N$개의 가능성 중 총 $s$개의 해가 있을 때 $t$번 반복 실행된 Grover 알고리즘이 해를 드러낼 확률을 나타냅니다.

성공 확률에 대한 이 하한 $1 - s/N$은 해가 더 많을수록 더 나쁜 하한을 의미한다는 점에서 약간 특이합니다. 하지만 $s$가 $N$보다 상당히 작다는 가정하에, 그럼에도 불구하고 성공 확률이 상당히 높다고 결론 내릴 수 있습니다. 이전과 마찬가지로, $p(N,s)$가 상당히 크다는 사실만으로도 알고리즘의 유용성을 함의합니다.

또한 다음도 성립합니다.

$$p(N,s) \geq \frac{s}{N}.$$

이 하한은 균등하게 무작위로 선택된 문자열 $x\in\Sigma^n$이 해일 확률을 설명합니다. 따라서 Grover 알고리즘은 항상 최소한 무작위 추측만큼은 잘 작동합니다. (사실, $t=0$일 때 Grover 알고리즘은 무작위 추측 그 자체입니다.)

이제 반복 횟수(따라서 쿼리 횟수)

$$t = \Bigl\lfloor \frac{\pi}{4\theta}\Bigr\rfloor,$$

를

$$\theta = \sin^{-1}\biggl(\sqrt{\frac{s}{N}}\biggr).$$

에 대해 살펴봅시다.

모든 $\alpha \in [0,1]$에 대해 $\sin^{-1}(\alpha)\geq \alpha$가 성립하며, 따라서

$$\theta = \sin^{-1}\left(\sqrt{\frac{s}{N}}\right) \geq \sqrt{\frac{s}{N}}.$$

이는 다음을 함의합니다.

$$t \leq \frac{\pi}{4\theta} \leq \frac{\pi}{4}\sqrt{\frac{N}{s}}.$$

이는 $s$가 커짐에 따라 쿼리 수의 절약으로 이어집니다. 특히, 필요한 쿼리 수는

$$O\biggl(\sqrt{\frac{N}{s}}\biggr).$$

입니다.

해의 수가 알려지지 않은 경우

해의 수 $s = \vert A_1 \vert$이 알려지지 않은 경우, 다른 접근이 필요합니다. 이 상황에서는 $t$의 선택에 정보를 제공할 $s$에 대한 지식이 없기 때문입니다. 사실, 여러 접근 방식이 있습니다.

간단한 접근 방식 하나는

$$t \in \Bigl\{ 1,\ldots,\bigl\lfloor\pi\sqrt{N}/4\bigr\rfloor \Bigr\}$$

에서 균등 무작위로 선택하는 것입니다. 이러한 방식으로 $t$를 선택하면 항상 40% 이상의 확률로 (해가 존재한다고 가정할 때) 해를 찾지만, 이는 자명하지 않으며 여기에는 포함되지 않는 분석이 필요합니다. 그러나 특히 기하학적 그림을 생각해 볼 때 의미가 있습니다. 이렇게 $\mathsf{Q}$의 상태를 무작위 횟수만큼 회전시키는 것은 $\vert A_0\rangle$과 $\vert A_1\rangle$이 생성하는 공간에서 무작위 단위 벡터를 선택하는 것과 크게 다르지 않으며, 그 경우 $\vert A_1\rangle$의 계수가 상당히 클 가능성이 있습니다. 이 절차를 반복하고 앞서 설명한 것과 같은 방식으로 결과를 확인함으로써, 해를 찾을 확률을 $1$에 매우 가깝게 만들 수 있습니다.

해의 개수 $s$가 알려지지 않았을 때도 해가 존재하면 $O(\sqrt{N/s})$번의 쿼리로 해를 찾고, $s=0$일 때 해가 없음을 결정하는 데 $O(\sqrt{N})$번의 쿼리가 필요한 개선된 방법이 있습니다.

기본 아이디어는 $T$ 값이 증가함에 따라 반복적으로 집합 $\{1,\ldots,T\}$에서 $t$를 균등 무작위로 선택하는 것입니다. 특히, $T = 1$로 시작하여 지수적으로 증가시킬 수 있으며, 해가 발견되는 즉시 프로세스를 종료하고 해가 없을 때 쿼리를 낭비하지 않도록 $T$의 상한을 두는 것입니다. 이 프로세스는 해가 더 많을 때 쿼리가 더 적게 필요하다는 사실을 활용합니다. 그러나 $T$의 증가율과 각 반복의 성공 확률 사이의 균형을 맞추려면 주의가 필요합니다. (예를 들어, $T \leftarrow \lceil \frac{5}{4}T\rceil$을 취하는 것은 분석에서 드러나듯이 작동합니다. 그러나 $T$를 두 배로 하는 것은 작동하지 않습니다. 이는 너무 빠른 증가인 것으로 드러납니다.)

자명한 경우

방금 진행한 분석 전체에서 해의 개수가 0이 아니라고 가정했습니다. 사실, 벡터

$$\begin{aligned} \vert A_0\rangle &= \frac{1}{\sqrt{\vert A_0\vert}} \sum_{x\in A_0} \vert x\rangle \\ \vert A_1\rangle &= \frac{1}{\sqrt{\vert A_1\vert}} \sum_{x\in A_1} \vert x\rangle \end{aligned}$$

를 언급함으로써 $A_0$와 $A_1$이 모두 비어 있지 않다고 암묵적으로 가정했습니다. 여기서는 이 집합 중 하나가 비어 있을 때 어떤 일이 일어나는지 간단히 고려할 것입니다.

분석을 수고롭게 하기 전에 명백한 것을 관찰합시다. 모든 문자열 $x\in\Sigma^n$이 해라면, 측정할 때 해를 보게 되고, 해가 없을 때는 보지 않을 것입니다. 어떤 의미에서는 이것보다 더 깊이 들어갈 필요가 없습니다.

그러나 이러한 자명한 경우에 대한 수학을 빠르게 확인할 수 있습니다. $A_0$와 $A_1$ 중 하나가 비어 있는 상황은 $f$가 상수일 때 일어납니다. 모든 $x\in\Sigma^n$에 대해 $f(x) = 0$일 때 $A_1$이 비어 있고, 모든 $x\in\Sigma^n$에 대해 $f(x) = 1$일 때 $A_0$가 비어 있습니다. 이는 다음을 의미합니다.

$$Z_f \vert u\rangle = \pm \vert u\rangle,$$

따라서

$$\begin{aligned} G \vert u \rangle & = \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I}\bigr) Z_f\vert u\rangle \\ & = \pm \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I}\bigr) \vert u\rangle \\ & = \pm \vert u\rangle. \end{aligned}$$

따라서 이러한 경우에 수행하는 반복 횟수 $t$에 관계없이, 측정은 항상 균등 무작위 문자열 $x\in\Sigma^n$을 드러낼 것입니다.