분석

이제 Grover 알고리즘이 어떻게 작동하는지 이해하기 위해 분석해 보겠습니다. 먼저 Grover 연산 $G$가 특정 상태에 어떻게 작용하는지 계산하는 기호적(symbolic) 분석이라고 할 수 있는 것으로 시작한 다음, 이 기호적 분석을 알고리즘이 어떻게 작동하는지 시각화하는 데 유용한 기하학적 그림과 연결하겠습니다.

해와 비해

먼저 두 개의 문자열 집합을 정의하는 것부터 시작하겠습니다.

$$\begin{aligned} A_0 &= \bigl\{ x\in\Sigma^n : f(x) = 0\bigr\} \\ A_1 &= \bigl\{ x\in\Sigma^n : f(x) = 1\bigr\} \end{aligned}$$

집합 $A_1$은 탐색 문제의 모든 해를 포함하고, $A_0$는 해가 아닌 문자열들(편의상 *비해(non-solutions)*이라고 부를 수 있습니다)을 포함합니다. 이 두 집합은 $A_0 \cap A_1 = \varnothing$과 $A_0 \cup A_1 = \Sigma^n$을 만족하며, 이는 $\Sigma^n$의 *이분할(bipartition)*임을 의미합니다.

다음으로, 해와 비해의 집합 위에서 균등 중첩을 나타내는 두 단위 벡터를 정의하겠습니다.

$$\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$ 중 어느 것도 비어 있지 않은 경우에 초점을 맞추겠습니다. $A_0 = \varnothing$과 $A_1 = \varnothing$인 경우는 쉽게 별도로 처리할 수 있으며, 이는 나중에 다루겠습니다.

참고로, 여기서 사용된 표기법은 흔한 것입니다. 유한하고 비어 있지 않은 집합 $S$가 있을 때마다, $S$의 원소들에 대해 균등한 양자 상태 벡터를 나타내기 위해 $\vert S\rangle$이라고 쓸 수 있습니다.

또한 $\vert u \rangle$을 모든 $n$-비트 문자열에 대한 균등(uniform) 양자 상태로 정의하겠습니다.

$$\vert u\rangle = \frac{1}{\sqrt{N}} \sum_{x\in\Sigma^n} \vert x\rangle.$$

다음을 주목하세요.

$$\vert u\rangle = \sqrt{\frac{\vert A_0 \vert}{N}} \vert A_0\rangle + \sqrt{\frac{\vert A_1 \vert}{N}} \vert A_1\rangle.$$

또한 $\vert u\rangle = H^{\otimes n} \vert 0^n \rangle$이므로, $\vert u\rangle$은 Grover 알고리즘의 1단계에서 초기화 후 레지스터 $\mathsf{Q}$의 상태를 나타냅니다.

이는 2단계에서 $G$의 반복이 일어나기 직전에 $\mathsf{Q}$의 상태가 $\vert A_0\rangle$과 $\vert A_1\rangle$이 생성하는 2차원 벡터 공간에 포함되어 있으며, 더욱이 이 벡터들의 계수가 실수임을 의미합니다. 앞으로 보게 되겠지만, 2단계에서 연산 $G$를 몇 번 반복하든 $\mathsf{Q}$의 상태는 항상 이러한 성질을 가질 것입니다. 즉, 상태는 $\vert A_0\rangle$과 $\vert A_1\rangle$의 실수 선형 결합입니다.

Grover 연산에 대한 관찰

이제 Grover 연산

$$G = H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} Z_f,$$

에 주목하며, 이에 대한 흥미로운 관찰로 시작하겠습니다.

잠시 함수 $f$를 $f$와 NOT 함수의 합성, 즉 $f$의 출력 비트를 뒤집어 얻는 함수로 대체한다고 상상해 봅시다. 이 새로운 함수를 $g$라고 부르고, 몇 가지 다른 방식으로 기호를 사용하여 표현할 수 있습니다.

$$g(x) = \neg f(x) = 1 \oplus f(x) = 1 - f(x) = \begin{cases} 1 & f(x) = 0\\[1mm] 0 & f(x) = 1 \end{cases}$$

다음을 주목하세요.

$$(-1)^{g(x)} = (-1)^{1 \oplus f(x)} = - (-1)^{f(x)}$$

모든 문자열 $x\in\Sigma^n$에 대해서 말이며, 따라서

$$Z_g = - Z_f.$$

이것은 함수 $f$를 함수 $g$로 대체하더라도, Grover 알고리즘이 다르게 작동하지 않음을 의미합니다. 두 경우에 알고리즘으로부터 얻는 상태가 전역 위상까지 반드시 동등하기 때문입니다.

이것은 문제가 되지 않습니다! 직관적으로 말해서, 알고리즘은 어떤 문자열이 해이고 어떤 것이 비해인지 신경 쓰지 않습니다. 올바르게 작동하려면 단지 해와 비해를 구별할 수 있기만 하면 됩니다.

Grover 연산의 작용

이제 양자 상태 벡터 $\vert A_0\rangle$과 $\vert A_1\rangle$에 대한 $G$의 작용을 고려해 봅시다.

먼저, 연산 $Z_f$가 $\vert A_0\rangle$과 $\vert A_1\rangle$에 매우 간단한 작용을 한다는 것을 관찰해 봅시다.

$$\begin{aligned} Z_f \vert A_0\rangle & = \vert A_0\rangle \\[1mm] Z_f \vert A_1\rangle & = -\vert A_1\rangle \end{aligned}$$

두 번째로, 연산 $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}$이 있습니다. 연산 $Z_{\mathrm{OR}}$은 다음과 같이 정의됩니다.

$$Z_{\mathrm{OR}} \vert x\rangle = \begin{cases} \vert x\rangle & x = 0^n \\[2mm] -\vert x\rangle & x \neq 0^n, \end{cases}$$

다시 모든 문자열 $x\in\Sigma^n$에 대해서이며, 이 연산을 표현하는 편리한 대안적 방법은 다음과 같습니다.

$$Z_{\mathrm{OR}} = 2 \vert 0^n \rangle \langle 0^n \vert - \mathbb{I}.$$

이 식이 $Z_{\mathrm{OR}}$의 정의와 일치함을 확인하는 간단한 방법은 표준 기저 상태에 대한 그 작용을 평가하는 것입니다.

따라서 연산 $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}$은 다음과 같이 쓸 수 있습니다.

$$H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} = 2 H^{\otimes n} \vert 0^n \rangle \langle 0^n \vert H^{\otimes n} - \mathbb{I} = 2 \vert u \rangle \langle u \vert - \mathbb{I},$$

모든 $n$-비트 문자열에 대한 균등 중첩을 위해 위에서 사용한 것과 동일한 표기법 $\vert u \rangle$을 사용하여 말입니다.

이제 $\vert A_0\rangle$과 $\vert A_1\rangle$에 대한 $G$의 작용을 계산하는 데 필요한 것을 갖추었습니다. 먼저 $\vert A_0\rangle$에 대한 $G$의 작용을 계산해 봅시다.

$$\begin{aligned} G \vert A_0 \rangle & = \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I}\bigr) Z_f \vert A_0\rangle \\ & = \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I}\bigr) \vert A_0\rangle \\ & = 2 \sqrt{\frac{\vert A_0\vert}{N}} \vert u\rangle -\vert A_0 \rangle\\ & = 2 \sqrt{\frac{\vert A_0\vert}{N}} \biggl( \sqrt{\frac{\vert A_0\vert}{N}} \vert A_0\rangle + \sqrt{\frac{\vert A_1\vert}{N}} \vert A_1\rangle\biggr) -\vert A_0 \rangle \\ & = \biggl( \frac{2\vert A_0\vert}{N} - 1\biggr) \vert A_0 \rangle + \frac{2 \sqrt{\vert A_0\vert \cdot \vert A_1\vert}}{N} \vert A_1 \rangle \\ & = \frac{\vert A_0\vert - \vert A_1\vert}{N} \vert A_0 \rangle + \frac{2 \sqrt{\vert A_0\vert \cdot \vert A_1\vert}}{N} \vert A_1 \rangle \end{aligned}$$

두 번째로, $\vert A_1\rangle$에 대한 $G$의 작용을 계산해 봅시다.

$$\begin{aligned} G \vert A_1 \rangle & = \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I} \bigr) Z_f \vert A_1\rangle \\ & = - \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I} \bigr) \vert A_1\rangle \\ & = - 2 \sqrt{\frac{\vert A_1\vert}{N}} \vert u\rangle + \vert A_1 \rangle \\ & = - 2 \sqrt{\frac{\vert A_1\vert}{N}} \biggl(\sqrt{\frac{\vert A_0\vert}{N}} \vert A_0\rangle + \sqrt{\frac{\vert A_1\vert}{N}} \vert A_1\rangle\biggr) + \vert A_1 \rangle \\ & = - \frac{2 \sqrt{\vert A_1\vert \cdot \vert A_0\vert}}{N} \vert A_0 \rangle + \biggl( 1 - \frac{2\vert A_1\vert}{N} \biggr) \vert A_1 \rangle \\ & = - \frac{2 \sqrt{\vert A_1\vert \cdot \vert A_0\vert}}{N} \vert A_0 \rangle + \frac{\vert A_0\vert - \vert A_1\vert}{N} \vert A_1 \rangle \end{aligned}$$

두 경우 모두 다음 방정식을 사용하고 있습니다.

$$\vert u\rangle = \sqrt{\frac{\vert A_0 \vert}{N}} \vert A_0\rangle + \sqrt{\frac{\vert A_1 \vert}{N}} \vert A_1\rangle$$

또한 이로부터 따라 나오는 식

$$\langle u \vert A_0\rangle = \sqrt{\frac{\vert A_0 \vert}{N}} \qquad\text{and}\qquad \langle u \vert A_1\rangle = \sqrt{\frac{\vert A_1 \vert}{N}}$$

도 함께 사용하고 있습니다.

요약하면, 다음을 얻습니다.

$$\begin{aligned} G \vert A_0 \rangle & = \frac{\vert A_0\vert - \vert A_1\vert}{N} \vert A_0 \rangle + \frac{2 \sqrt{\vert A_0\vert \cdot \vert A_1\vert}}{N} \vert A_1 \rangle\\[2mm] G \vert A_1 \rangle & = - \frac{2 \sqrt{\vert A_1\vert \cdot \vert A_0\vert}}{N} \vert A_0 \rangle + \frac{\vert A_0\vert - \vert A_1\vert}{N} \vert A_1 \rangle. \end{aligned}$$

이미 언급했듯이, 2단계 바로 직전의 $\mathsf{Q}$의 상태는 $\vert A_0\rangle$과 $\vert A_1\rangle$이 생성하는 2차원 공간에 포함되어 있고, 방금 $G$가 이 공간의 임의의 벡터를 같은 공간의 다른 벡터로 사상함을 확립했습니다. 이는 분석을 위해 우리가 이 부분공간에만 주의를 집중할 수 있음을 의미합니다.

이 2차원 공간 내에서 일어나는 일을 더 잘 이해하기 위해, 이 공간에서 $G$의 작용을 행렬로 표현해 봅시다.

$$M = \begin{pmatrix} \frac{\vert A_0\vert - \vert A_1\vert}{N} & -\frac{2 \sqrt{\vert A_1\vert \cdot \vert A_0\vert}}{N} \\[2mm] \frac{2 \sqrt{\vert A_0\vert \cdot \vert A_1\vert}}{N} & \frac{\vert A_0\vert - \vert A_1\vert}{N} \end{pmatrix},$$

이 행렬의 첫 번째와 두 번째 행/열은 각각 $\vert A_0\rangle$과 $\vert A_1\rangle$에 해당합니다. 이 시리즈에서 지금까지 우리는 항상 행렬의 행과 열을 시스템의 고전 상태와 연결해 왔지만, 행렬은 여기서처럼 서로 다른 기저에서 선형 사상의 작용을 설명하는 데에도 사용될 수 있습니다.

한눈에는 전혀 명확하지 않지만, 행렬 $M$은 더 단순해 보이는 행렬을 제곱하여 얻어지는 것입니다.

$$\begin{pmatrix} \sqrt{\frac{\vert A_0\vert}{N}} & - \sqrt{\frac{\vert A_1\vert}{N}} \\[2mm] \sqrt{\frac{\vert A_1\vert}{N}} & \sqrt{\frac{\vert A_0\vert}{N}} \end{pmatrix}^2 = \begin{pmatrix} \frac{\vert A_0\vert - \vert A_1\vert}{N} & -\frac{2 \sqrt{\vert A_1\vert \cdot \vert A_0\vert}}{N} \\[2mm] \frac{2 \sqrt{\vert A_0\vert \cdot \vert A_1\vert}}{N} & \frac{\vert A_0\vert - \vert A_1\vert}{N} \end{pmatrix} = M$$

행렬

$$\begin{pmatrix} \sqrt{\frac{\vert A_0\vert}{N}} & - \sqrt{\frac{\vert A_1\vert}{N}} \\[2mm] \sqrt{\frac{\vert A_1\vert}{N}} & \sqrt{\frac{\vert A_0\vert}{N}} \end{pmatrix}$$

은 회전 행렬이며, 다음과 같이 대안적으로 표현할 수 있습니다.

$$\begin{pmatrix} \sqrt{\frac{\vert A_0\vert}{N}} & - \sqrt{\frac{\vert A_1\vert}{N}} \\[2mm] \sqrt{\frac{\vert A_1\vert}{N}} & \sqrt{\frac{\vert A_0\vert}{N}} \end{pmatrix} = \begin{pmatrix} \cos(\theta) & -\sin(\theta) \\[2mm] \sin(\theta) & \cos(\theta) \end{pmatrix}$$

여기서

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

이 각도 $\theta$는 이후의 분석에서 매우 중요한 역할을 할 것이므로, 처음 보는 지금 그 중요성을 강조할 가치가 있습니다.

이 행렬의 이러한 표현에 비추어, 다음을 관찰합니다.

$$M = \begin{pmatrix} \cos(\theta) & -\sin(\theta) \\[2mm] \sin(\theta) & \cos(\theta) \end{pmatrix}^2 = \begin{pmatrix} \cos(2\theta) & -\sin(2\theta) \\[2mm] \sin(2\theta) & \cos(2\theta) \end{pmatrix}.$$

이는 각도 $\theta$로 두 번 회전하는 것이 각도 $2\theta$로 회전하는 것과 동등하기 때문입니다. 이를 확인하는 또 다른 방법은 대안적 표현

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

를 삼각함수의 배각 공식과 함께 사용하는 것입니다.

$$\begin{aligned} \cos(2\theta) & = \cos^2(\theta) - \sin^2(\theta)\\[1mm] \sin(2\theta) & = 2 \sin(\theta)\cos(\theta). \end{aligned}$$

요약하면, 2단계 시작 시점에서 레지스터 $\mathsf{Q}$의 상태는

$$\vert u\rangle = \sqrt{\frac{\vert A_0\vert}{N}} \vert A_0\rangle + \sqrt{\frac{\vert A_1\vert}{N}} \vert A_1\rangle = \cos(\theta) \vert A_0\rangle + \sin(\theta) \vert A_1\rangle,$$

이고, 이 상태에 $G$를 적용하는 효과는 $\vert A_0\rangle$과 $\vert A_1\rangle$이 생성하는 공간 내에서 각도 $2\theta$만큼 회전시키는 것입니다. 예를 들어, 다음과 같습니다.

$$\begin{aligned} G \vert u \rangle &= \cos(3\theta) \vert A_0\rangle + \sin(3\theta) \vert A_1\rangle\\[1mm] G^2 \vert u \rangle &= \cos(5\theta) \vert A_0\rangle + \sin(5\theta) \vert A_1\rangle\\[1mm] G^3 \vert u \rangle &= \cos(7\theta) \vert A_0\rangle + \sin(7\theta) \vert A_1\rangle \end{aligned}$$

일반적으로

$$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.$$

기하학적 그림

이제 방금 수행한 분석을 기하학적 그림과 연결해 봅시다. 아이디어는 연산 $G$가 두 *반사(reflection)*인 $Z_f$와 $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}$의 곱이라는 것입니다. 그리고 두 반사를 수행한 순효과는 회전을 수행하는 것입니다.

$Z_f$부터 시작해 봅시다. 이미 앞서 관찰했듯이, 다음과 같습니다.

$$\begin{aligned} Z_f \vert A_0\rangle & = \vert A_0\rangle \\[1mm] Z_f \vert A_1\rangle & = -\vert A_1\rangle. \end{aligned}$$

$\vert A_0\rangle$과 $\vert A_1\rangle$이 생성하는 2차원 벡터 공간 내에서, 이는 $\vert A_0\rangle$과 평행한 직선(이를 $L_1$이라고 부르겠습니다)에 대한 반사입니다. 다음은 $\vert A_0\rangle$과 $\vert A_1\rangle$의 실수 선형 결합이라고 가정하는 가상의 단위 벡터 $\vert\psi\rangle$에 대한 이 반사의 작용을 보여주는 그림입니다.

두 번째로 연산 $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}$이 있는데, 이미 다음과 같이 쓸 수 있음을 보았습니다.

$$H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} = 2 \vert u \rangle \langle u \vert - \mathbb{I}.$$

이것도 반사이며, 이번에는 벡터 $\vert u\rangle$과 평행한 직선 $L_2$에 대한 반사입니다. 다음은 단위 벡터 $\vert\psi\rangle$에 대한 이 반사의 작용을 보여주는 그림입니다.

이 두 반사를 합성하면, 다음 그림이 보여주듯이 반사의 직선들 사이의 각도의 두 배만큼 회전을 얻습니다.

이것은 기하학적 용어로, Grover 연산의 효과가 $\vert A_0\rangle$과 $\vert A_1\rangle$의 선형 결합을 각도 $2\theta$만큼 회전시키는 이유를 설명합니다.