쇼어 알고리즘

이제 정수 인수분해 문제로 관심을 돌려, 위상 추정을 이용해 양자 컴퓨터에서 이 문제를 효율적으로 풀 수 있는 방법을 살펴보겠습니다. 여기서 얻게 될 알고리즘이 바로 정수 인수분해를 위한 쇼어 알고리즘입니다. 쇼어는 자신의 알고리즘을 위상 추정의 관점에서 구체적으로 설명하지는 않았지만, 이 방식이 알고리즘의 동작 원리를 자연스럽고 직관적으로 설명하는 방법입니다.

먼저 *위수 찾기 문제(order-finding problem)*라는 중간 단계 문제를 논의하고, 위상 추정이 이 문제에 대한 해법을 어떻게 제공하는지 살펴보겠습니다. 그런 다음 위수 찾기 문제의 효율적인 해법이 정수 인수분해 문제의 효율적인 해법을 어떻게 제공하는지 알아보겠습니다. (한 문제의 해법이 이런 식으로 다른 문제의 해법을 제공할 때, 두 번째 문제가 첫 번째 문제로 환원된다고 말합니다 — 따라서 이 경우 정수 인수분해를 위수 찾기로 환원하는 것입니다.) 쇼어 알고리즘의 두 번째 부분은 양자 컴퓨팅을 전혀 사용하지 않으며, 완전히 고전적입니다. 양자 컴퓨팅은 위수 찾기를 해결하는 데만 필요합니다.

위수 찾기 문제

기초 정수론

위수 찾기 문제와 위상 추정을 이용해 이를 해결하는 방법을 설명하기 위해, 몇 가지 기초적인 정수론 개념을 먼저 소개하고 유용한 표기법을 함께 알아보겠습니다.

먼저, 양의 정수 $N$이 주어졌을 때 집합 $\mathbb{Z}_N$을 다음과 같이 정의합니다.

$$\mathbb{Z}_N = \{0,1,\ldots,N-1\}$$

예를 들어, $\mathbb{Z}_1 = \{0\},\;$ $\mathbb{Z}_2 = \{0,1\},\;$ $\mathbb{Z}_3 = \{0,1,2\},\;$ 등과 같습니다.

이것들은 수의 집합이지만, 단순한 집합 이상으로 생각할 수 있습니다. 특히, $\mathbb{Z}_N$ 위에서 덧셈과 곱셈 같은 산술 연산을 생각할 수 있습니다 — 항상 $N$으로 나눈 나머지를 결과로 취한다면 (즉, $N$으로 나누어 나머지를 결과로 사용한다면), 이 연산들을 수행해도 항상 이 집합 내에 머물게 됩니다. 덧셈과 곱셈 두 연산을 모두 $N$을 법(modulo)으로 취하면, $\mathbb{Z}_N$은 *환(ring)*이 됩니다. 이는 대수학에서 근본적으로 중요한 구조입니다.

예를 들어, $3$과 $5$는 $\mathbb{Z}_7$의 원소이며, 이 둘을 곱하면 $3\cdot 5 = 15$가 되고, $7$로 나누면 나머지가 $1$입니다. 이를 다음과 같이 표현하기도 합니다.

$$3 \cdot 5 \equiv 1 \; (\textrm{mod } 7)$$

하지만 $\mathbb{Z}_7$ 안에서 작업 중임을 명확히 했다면, 표기를 간단하게 유지하기 위해 단순히 $3 \cdot 5 = 1$이라고 쓸 수도 있습니다.

예시로, $\mathbb{Z}_6$의 덧셈표와 곱셈표를 보겠습니다.

$$\begin{array}{c|cccccc} + & 0 & 1 & 2 & 3 & 4 & 5 \\\hline 0 & 0 & 1 & 2 & 3 & 4 & 5 \\ 1 & 1 & 2 & 3 & 4 & 5 & 0 \\ 2 & 2 & 3 & 4 & 5 & 0 & 1 \\ 3 & 3 & 4 & 5 & 0 & 1 & 2 \\ 4 & 4 & 5 & 0 & 1 & 2 & 3 \\ 5 & 5 & 0 & 1 & 2 & 3 & 4 \\ \end{array} \qquad \begin{array}{c|cccccc} \cdot & 0 & 1 & 2 & 3 & 4 & 5 \\\hline 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 2 & 3 & 4 & 5 \\ 2 & 0 & 2 & 4 & 0 & 2 & 4 \\ 3 & 0 & 3 & 0 & 3 & 0 & 3 \\ 4 & 0 & 4 & 2 & 0 & 4 & 2 \\ 5 & 0 & 5 & 4 & 3 & 2 & 1 \\ \end{array}$$

$\mathbb{Z}_N$의 $N$개 원소 중, $\gcd(a,N) = 1$을 만족하는 원소 $a\in\mathbb{Z}_N$은 특별합니다. 이러한 원소들의 집합은 흔히 별표를 붙여 다음과 같이 표기합니다.

$$\mathbb{Z}_N^{\ast} = \{a\in \mathbb{Z}_N : \gcd(a,N) = 1\}$$

곱셈 연산에만 집중한다면, $\mathbb{Z}_N^{\ast}$는 군(group) — 특히 아벨 군(abelian group) — 을 이룹니다. 이는 대수학에서 또 다른 중요한 구조입니다. 이 집합(그리고 유한 군 일반)에 대한 기본적인 사실로, $a\in\mathbb{Z}_N^{\ast}$인 임의의 원소 $a$를 택해 $a$를 자기 자신에 반복적으로 곱하면, 결국 항상 $1$을 얻게 됩니다.

첫 번째 예시로, $N=6$을 취해보겠습니다. $\gcd(5,6) = 1$이므로 $5\in\mathbb{Z}_6^{\ast}$이고, $5$를 자기 자신에 곱하면 $1$을 얻습니다. 위의 표에서 이를 확인할 수 있습니다.

$$5^2 = 1 \quad \text{(working within $\mathbb{Z}_6$)}$$

두 번째 예시로, $N = 21$을 취해보겠습니다. $0$부터 $20$까지의 수 중 $21$과의 최대공약수가 $1$인 것들은 다음과 같습니다.

$$\mathbb{Z}_{21}^{\ast} = \{1,2,4,5,8,10,11,13,16,17,19,20\}$$

이 원소들 각각에 대해, 그 수를 양의 정수 거듭제곱하여 $1$을 얻는 것이 가능합니다. 그렇게 되는 가장 작은 거듭제곱은 다음과 같습니다.

$$\begin{array}{ccc} 1^{1} = 1 \quad & 8^{2} = 1 \quad & 16^{3} = 1 \\[1mm] 2^{6} = 1 \quad & 10^{6} = 1 \quad & 17^{6} = 1 \\[1mm] 4^{3} = 1 \quad & 11^{6} = 1 \quad & 19^{6} = 1 \\[1mm] 5^{6} = 1 \quad & 13^{2} = 1 \quad & 20^{2} = 1 \end{array}$$

물론 이 등식들은 모두 $\mathbb{Z}_{21}$ 내에서 계산한 것이며, 이를 매번 명시하지 않겠습니다 — 표기가 복잡해지지 않도록 이를 암묵적으로 가정합니다. 이 강좌의 나머지 부분 전체에서 이렇게 하겠습니다.

문제 정의와 위상 추정과의 연결

이제 위수 찾기 문제를 정의할 수 있습니다.

위수 찾기

입력: $\gcd(N,a) = 1$을 만족하는 양의 정수 $N$과 $a$
출력: $a^r \equiv 1$ $(\textrm{mod } N)$을 만족하는 가장 작은 양의 정수 $r$

다른 방식으로 표현하면, 방금 소개한 표기법을 이용해 $a \in \mathbb{Z}_N^{\ast}$가 주어졌을 때, $a^r = 1$을 만족하는 가장 작은 양의 정수 $r$을 찾는 문제입니다. 이 수 $r$을 $N$을 법으로 한 $a$의 *위수(order)*라고 합니다.

위수 찾기 문제를 위상 추정과 연결하기 위해, $\mathbb{Z}_N$에 대응되는 고전 상태를 갖는 시스템 위에서 고정된 원소 $a\in\mathbb{Z}_N^{\ast}$를 곱하는 연산을 생각해 보겠습니다.

$$M_a \vert x\rangle = \vert ax \rangle \qquad \text{(for each $x\in\mathbb{Z}_N$)}$$

명확히 하자면, 곱셈은 $\mathbb{Z}_N$ 안에서 수행하므로, 등식 오른쪽 ket 내부에서 $N$을 법으로 한 나머지를 취한다는 것이 암묵적으로 포함되어 있습니다.

예를 들어, $N = 15$이고 $a=2$이면, $M_2$의 표준 기저 $\{\vert 0\rangle,\ldots,\vert 14\rangle\}$에 대한 작용은 다음과 같습니다.

$$\begin{array}{ccc} M_{2} \vert 0 \rangle = \vert 0\rangle \quad & M_{2} \vert 5 \rangle = \vert 10\rangle \quad & M_{2} \vert 10 \rangle = \vert 5\rangle \\[1mm] M_{2} \vert 1 \rangle = \vert 2\rangle \quad & M_{2} \vert 6 \rangle = \vert 12\rangle \quad & M_{2} \vert 11 \rangle = \vert 7\rangle \\[1mm] M_{2} \vert 2 \rangle = \vert 4\rangle \quad & M_{2} \vert 7 \rangle = \vert 14\rangle \quad & M_{2} \vert 12 \rangle = \vert 9\rangle \\[1mm] M_{2} \vert 3 \rangle = \vert 6\rangle \quad & M_{2} \vert 8 \rangle = \vert 1\rangle \quad & M_{2} \vert 13 \rangle = \vert 11\rangle \\[1mm] M_{2} \vert 4 \rangle = \vert 8\rangle \quad & M_{2} \vert 9 \rangle = \vert 3\rangle \quad & M_{2} \vert 14 \rangle = \vert 13\rangle \end{array}$$

이 연산은 $\gcd(a,N)=1$이면 유니타리 연산입니다. 표준 기저 $\{\vert 0\rangle,\ldots,\vert N-1\rangle\}$의 원소들을 순열하므로, 행렬로 나타내면 순열 행렬이 됩니다. 정의로부터 이 연산이 결정론적임은 분명하며, 가역적임을 확인하는 간단한 방법은 $a$의 $N$을 법으로 한 위수 $r$을 생각하고, $M_a$의 역연산이 $M_a^{r-1}$임을 인식하는 것입니다.

$$M_a^{r-1} M_a = M_a^r = M_{a^r} = M_1 = \mathbb{I}$$

역연산을 생각하는 또 다른 방법이 있는데, 이는 $r$에 대한 지식을 필요로 하지 않습니다 (결국 $r$이 바로 우리가 계산하려는 것이니까요). $a\in\mathbb{Z}_N^{\ast}$인 모든 원소 $a$에 대해, $ab=1$을 만족하는 유일한 원소 $b\in\mathbb{Z}_N^{\ast}$가 항상 존재합니다. 이 원소 $b$를 $a^{-1}$으로 표기하며, 효율적으로 계산할 수 있습니다. 유클리드 GCD 알고리즘의 확장이 $\operatorname{lg}(N)$에 대해 이차 비용으로 이를 수행합니다. 따라서

$$M_{a^{-1}} M_a = M_{a^{-1}a} = M_1 = \mathbb{I}.$$

즉, 연산 $M_a$는 결정론적이면서 가역적입니다. 이는 $M_a$가 순열 행렬로 표현됨을 의미하며, 따라서 유니타리 연산입니다.

이제 $a\in\mathbb{Z}_N^{\ast}$라 가정하고, 연산 $M_a$의 고유벡터와 고유값을 생각해 보겠습니다. 방금 논의한 바와 같이, 이 가정은 $M_a$가 유니타리임을 알려줍니다.

$M_a$의 고유값은 $N$개이며, 같은 고유값이 여러 번 반복될 수도 있고, 대응하는 고유벡터를 선택하는 데 자유도가 있을 수 있습니다 — 하지만 모든 경우를 걱정할 필요는 없습니다. 간단하게 시작하여 $M_a$의 고유벡터 하나만 찾아보겠습니다.

$$\vert \psi_0 \rangle = \frac{\vert 1 \rangle + \vert a \rangle + \cdots + \vert a^{r-1} \rangle}{\sqrt{r}}$$

$r$은 $a$의 $N$을 법으로 한 위수이며, 이후 강좌 내내 이를 사용합니다. 이 고유벡터에 대응하는 고유값은 $1$입니다. $a$를 곱해도 이 벡터가 변하지 않기 때문입니다.

$$M_a \vert \psi_0 \rangle = \frac{\vert a \rangle + \cdots + \vert a^{r-1} \rangle + \vert a^r \rangle}{\sqrt{r}} = \frac{\vert a \rangle + \cdots + \vert a^{r-1} \rangle + \vert 1 \rangle}{\sqrt{r}} = \vert \psi_0 \rangle$$

이는 $a^r = 1$이기 때문에 발생합니다. 각 표준 기저 상태 $\vert a^k \rangle$은 $k\leq r-1$일 때 $\vert a^{k+1} \rangle$로 이동하고, $\vert a^{r-1} \rangle$은 $\vert 1\rangle$로 돌아옵니다. 비유하자면, $\vert \psi_0 \rangle$을 천천히 휘젓는 것과 같지만, 이미 완전히 균일하게 섞여 있어서 아무것도 변하지 않는 것입니다.

다음은 $M_a$의 또 다른 고유벡터 예시입니다. 이것은 위수 찾기와 위상 추정의 맥락에서 더 흥미로운 벡터입니다.

$$\vert \psi_1 \rangle = \frac{\vert 1 \rangle + \omega_r^{-1} \vert a \rangle + \cdots + \omega_r^{-(r-1)}\vert a^{r-1} \rangle}{\sqrt{r}}$$

이 벡터를 합산 표기로 다음과 같이 쓸 수도 있습니다.

$$\vert \psi_1 \rangle = \frac{1}{\sqrt{r}} \sum_{k = 0}^{r-1} \omega_r^{-k} \vert a^k \rangle$$

여기서 복소수 $\omega_r = e^{2\pi i/r}$이 $N$을 법으로 한 $a$의 곱셈 방식 때문에 자연스럽게 나타납니다. 이번에 대응하는 고유값은 $\omega_r$입니다. 이를 확인하기 위해 다음과 같이 계산할 수 있습니다.

$$M_a \vert \psi_1 \rangle = \frac{1}{\sqrt{r}}\sum_{k = 0}^{r-1} \omega_r^{-k} M_a\vert a^k \rangle = \frac{1}{\sqrt{r}}\sum_{k = 0}^{r-1} \omega_r^{-k} \vert a^{k+1} \rangle = \frac{1}{\sqrt{r}}\sum_{k = 1}^{r} \omega_r^{-(k - 1)} \vert a^{k} \rangle = \frac{1}{\sqrt{r}}\omega_r \sum_{k = 1}^{r} \omega_r^{-k} \vert a^{k} \rangle$$

그런 다음, $\omega_r^{-r} = 1 = \omega_r^0$이고 $\vert a^r \rangle = \vert 1\rangle = \vert a^0\rangle$이므로,

$$\frac{1}{\sqrt{r}}\sum_{k = 1}^{r} \omega_r^{-k} \vert a^{k} \rangle = \frac{1}{\sqrt{r}}\sum_{k = 0}^{r-1} \omega_r^{-k} \vert a^k \rangle = \vert\psi_1\rangle,$$

따라서 $M_a \vert\psi_1\rangle = \omega_r \vert\psi_1\rangle$임을 알 수 있습니다.

같은 방법으로 $M_a$의 추가적인 고유벡터/고유값 쌍을 찾을 수 있습니다. $j\in\{0,\ldots,r-1\}$의 임의의 선택에 대해,

$$\vert \psi_j \rangle = \frac{1}{\sqrt{r}} \sum_{k = 0}^{r-1} \omega_r^{-jk} \vert a^k \rangle$$

는 $M_a$의 고유벡터이며, 대응하는 고유값은 $\omega_r^j$입니다.

$$M_a \vert \psi_j \rangle = \omega_r^j \vert \psi_j \rangle$$

$M_a$에는 다른 고유벡터들도 있지만, 그것들을 신경 쓸 필요는 없습니다 — 방금 확인한 고유벡터 $\vert\psi_0\rangle,\ldots,\vert\psi_{r-1}\rangle$에만 집중하겠습니다.

위상 추정을 통한 차수 찾기

주어진 $a\in\mathbb{Z}_N^{\ast}$에 대해 차수 찾기 문제를 풀기 위해, $M_a$ 연산에 위상 추정 절차를 적용할 수 있습니다.

이를 위해서는 $M_a$뿐만 아니라 $M_a^2,$ $M_a^4,$ $M_a^8,$ 등도 양자 Circuit으로 효율적으로 구현해야 합니다. 위상 추정 절차에서 충분히 정밀한 추정값을 얻기 위해 필요한 만큼 거듭제곱을 계속 구해야 합니다. 여기서는 이것이 어떻게 가능한지 설명하고, 정확히 얼마나 많은 정밀도가 필요한지는 나중에 알아보겠습니다.

먼저 $M_a$ 연산 자체부터 시작해 보겠습니다. 양자 Circuit 모델을 사용하므로, 0과 $N-1$ 사이의 숫자를 이진 표기법으로 인코딩합니다. 인코딩해야 하는 가장 큰 수는 $N-1$이므로, 필요한 비트 수는 다음과 같습니다.

$$n = \operatorname{lg}(N-1) = \lfloor \log(N-1) \rfloor + 1.$$

예를 들어, $N = 21$이면 $n = \operatorname{lg}(N-1) = 5$입니다. $\mathbb{Z}_{21}$의 원소들을 길이 $5$의 이진 문자열로 인코딩하는 방식은 다음과 같습니다.

$$\begin{gathered} 0 \mapsto 00000\\[1mm] 1 \mapsto 00001\\[1mm] \vdots\\[1mm] 20 \mapsto 10100 \end{gathered}$$

이제 $M_a$가 $n$-Qubit 연산으로 어떻게 정의되는지 정확히 서술해 보겠습니다.

$$M_a \vert x\rangle = \begin{cases} \vert ax \; (\textrm{mod}\;N)\rangle & 0\leq x < N\\[1mm] \vert x\rangle & N\leq x < 2^n \end{cases}$$

핵심은, $M_a$가 $\vert 0\rangle,\ldots,\vert N-1\rangle$에 대해 어떻게 작동하는지만 관심이 있지만, 나머지 $2^n - N$개의 표준 기저 상태에 대해서도 유니터리 연산이 되도록 정의해야 한다는 점입니다. 나머지 표준 기저 상태에 대해 $M_a$가 아무것도 하지 않도록 정의하면 이 조건이 충족됩니다.

이전 강의에서 논의한 정수 곱셈 및 나눗셈 알고리즘과, 가역적이고 쓰레기 없는 구현 방법론을 활용하면, $a\in\mathbb{Z}_N^{\ast}$의 임의 선택에 대해 $M_a$를 수행하는 양자 Circuit을 $O(n^2)$ 비용으로 구성할 수 있습니다. 한 가지 방법은 다음과 같습니다.

1. 다음 연산을 수행하는 Circuit을 구성합니다.

   $$\vert x \rangle \vert y \rangle \mapsto \vert x \rangle \vert y \oplus f_a(x)\rangle$$

   여기서

   $$f_a(x) = \begin{cases} ax \; (\textrm{mod}\;N) & 0\leq x < N\\[1mm] x & N\leq x < 2^n \end{cases}$$

   이전 강의에서 설명한 방법을 사용합니다. 이로써 크기 $O(n^2)$의 Circuit을 얻습니다.

2. $n$개의 스왑 게이트를 사용하여 Qubit들을 개별적으로 스왑함으로써 두 $n$-Qubit 시스템을 교환합니다.

3. 첫 번째 단계와 유사하게, 다음 연산을 위한 Circuit을 구성합니다.

   $$\vert x \rangle \vert y \rangle \mapsto \vert x \rangle \bigl\vert y \oplus f_{a^{-1}}(x)\bigr\rangle$$

   여기서 $a^{-1}$는 $\mathbb{Z}_N^{\ast}$에서 $a$의 역원입니다.

아래쪽 $n$개의 Qubit를 초기화하고 세 단계를 합성하면 다음 변환을 얻습니다.

$$\vert x \rangle \vert 0^n \rangle \stackrel{\text{step 1}}{\mapsto} \vert x \rangle \vert f_a(x)\rangle \stackrel{\text{step 2}}{\mapsto} \vert f_a(x)\rangle \vert x \rangle \stackrel{\text{step 3}}{\mapsto} \vert f_a(x)\rangle \bigl\vert x \oplus f_{a^{-1}}(f_a(x)) \bigr\rangle = \vert f_a(x)\rangle\vert 0^n \rangle$$

이 방법은 작업공간 Qubit가 필요하지만, 마지막에 초기화된 상태로 반환되므로 위상 추정에 이 Circuit들을 사용할 수 있습니다. 얻어지는 Circuit의 총 비용은 $O(n^2)$입니다.

$M_a^2,$ $M_a^4,$ $M_a^8,$ 등을 수행하려면, 정확히 같은 방법을 사용하되 $a$를 $\mathbb{Z}_N^{\ast}$의 원소로서 $a^2,$ $a^4,$ $a^8,$ 등으로 대체하면 됩니다. 즉, 임의의 거듭제곱 $k$에 대해 $M_a$의 Circuit을 $k$번 반복하는 대신, $b = a^k \in \mathbb{Z}_N^{\ast}$를 계산한 다음 $M_b$에 대한 Circuit을 사용하면 $M_a^k$의 Circuit을 만들 수 있습니다.

$a^k \in \mathbb{Z}_N$의 거듭제곱을 계산하는 것은 이전 강의에서 언급한 모듈러 지수 문제입니다. 이 계산은 이전 강의에서 언급한 모듈러 지수 알고리즘(계산 정수론에서 흔히 거듭제곱 알고리즘이라 불림)을 사용하여 고전적으로 수행할 수 있습니다. 실제로 $a$의 2의 거듭제곱 승, 즉 $a^2, a^4, \ldots a^{2^{m-1}} \in \mathbb{Z}_N^{\ast}$만 필요하며, $m-1$번 반복하여 제곱함으로써 이 거듭제곱들을 얻을 수 있습니다. 각 제곱은 크기 $O(n^2)$의 불리언 Circuit으로 수행할 수 있습니다.

본질적으로, 여기서 우리가 하는 일은 $M_a$를 최대 $2^{m-1}$번 반복하는 문제를 효율적인 고전 계산으로 넘기는 것입니다. 그리고 이것이 가능하다는 것은 정말 다행입니다! 위상 추정 문제에서 임의의 양자 Circuit을 선택하면, 이런 것이 가능하지 않을 가능성이 높습니다. 그런 경우 위상 추정의 비용은 제어 Qubit 수 $m$에 대해 지수적으로 증가합니다.

편리한 고유 벡터가 주어진 경우의 풀이

위상 추정을 사용하여 차수 찾기 문제를 어떻게 풀 수 있는지 이해하기 위해, 먼저 고유 벡터 $\vert\psi_1\rangle$을 사용하여 $M_a$에 위상 추정 절차를 실행한다고 가정해 보겠습니다. 사실 이 고유 벡터를 구하기가 쉽지 않으므로 이것이 전부는 아니지만, 여기서부터 시작하는 것이 도움이 됩니다.

$M_a$의 고유 벡터 $\vert \psi_1\rangle$에 대응하는 고유값은

$$\omega_r = e^{2\pi i \frac{1}{r}}$$

입니다.

즉, $\theta = 1/r$에 대해 $\omega_r = e^{2\pi i \theta}$입니다. 따라서 고유 벡터 $\vert\psi_1\rangle$을 사용하여 $M_a$에 위상 추정 절차를 실행하면, $1/r$의 근사값을 얻습니다. 역수를 계산하면 $r$을 알 수 있습니다 — 근사값이 충분히 정확하다면 말이죠.

더 자세히 설명하면, $m$개의 제어 Qubit를 사용하여 위상 추정 절차를 실행하면 $y\in\{0,\ldots,2^m-1\}$인 수 $y$를 얻습니다. 그런 다음 $y/2^m$을 $\theta$의 추정값으로 삼는데, 지금의 경우 $\theta = 1/r$입니다. 이 근사값에서 $r$이 무엇인지 알아내기 위해 자연스러운 방법은 근사값의 역수를 구하고 가장 가까운 정수로 반올림하는 것입니다.

$$\left\lfloor \frac{2^m}{y} + \frac{1}{2} \right\rfloor$$

예를 들어, $r = 6$이고 고유 벡터 $\vert\psi_1\rangle$을 사용하여 $m = 5$개의 제어 비트로 $M_a$에 위상 추정을 수행한다고 가정해 보겠습니다. $1/r = 1/6$에 대한 최적 $5$비트 근사값은 $5/32$이며, 이 경우 위상 추정에서 결과 $y=5$를 얻을 확률이 꽤 높습니다(약 $68\%$). 다음이 성립합니다.

$$\frac{2^m}{y} = \frac{32}{5} = 6.4,$$

가장 가까운 정수로 반올림하면 $6$이 되어 올바른 답을 얻습니다.

반면에 정밀도가 충분하지 않으면 올바른 답을 얻지 못할 수 있습니다. 예를 들어, 위상 추정에서 $m = 4$개의 제어 Qubit를 사용하면 $1/r = 1/6$에 대한 최적 $4$비트 근사값인 $3/16$을 얻을 수 있습니다. 역수를 취하면

$$\frac{2^m}{y} = \frac{16}{3} = 5.333 \cdots$$

가장 가까운 정수로 반올림하면 잘못된 답인 $5$를 얻습니다.

그렇다면 올바른 답을 얻기 위해 얼마나 많은 정밀도가 필요할까요? 차수 $r$은 정수임을 알고 있으며, 직관적으로 필요한 것은 $1/r$을 인근의 다른 가능성들, 즉 $1/(r+1)$과 $1/(r-1)$로부터 구별하기에 충분한 정밀도입니다. $1/r$에 가장 가까운 수는 $1/(r+1)$이며, 이 두 수 사이의 거리는

$$\frac{1}{r} - \frac{1}{r+1} = \frac{1}{r(r+1)}$$

입니다.

따라서 $1/r$을 $1/(r+1)$로 혼동하지 않으려면, $1/r$에 대한 최적 근사값 $y/2^m$이 $1/(r+1)$보다 $1/r$에 더 가깝도록 보장할 수 있는 충분한 정밀도를 사용하면 됩니다. 다음을 만족하는 정밀도를 사용하면

$$\left\vert \frac{y}{2^m} - \frac{1}{r} \right\vert < \frac{1}{2 r (r+1)},$$

즉 오차가 $1/r$과 $1/(r+1)$ 사이 거리의 절반보다 작으면, $y/2^m$은 $1/(r+1)$이나 $1/(r-1)$을 포함한 다른 어떤 가능성보다 $1/r$에 더 가깝게 됩니다.

이것을 다음과 같이 확인할 수 있습니다.

$$\frac{y}{2^m} = \frac{1}{r} + \varepsilon$$

라고 가정하고, $\varepsilon$이

$$\vert\varepsilon\vert < \frac{1}{2 r (r+1)}$$

을 만족한다고 합시다.

역수를 취하면

$$\frac{2^m}{y} = \frac{1}{\frac{1}{r} + \varepsilon} = \frac{r}{1+\varepsilon r} = r - \frac{\varepsilon r^2}{1+\varepsilon r}$$

을 얻습니다.

분자를 최대화하고 분모를 최소화하면, $r$로부터의 거리를 다음과 같이 한정할 수 있습니다.

$$\left\vert \frac{\varepsilon r^2}{1+\varepsilon r} \right\vert \leq \frac{ \frac{r^2}{2 r(r+1)}}{1 - \frac{r}{2r(r+1)}} = \frac{r}{2 r + 1} < \frac{1}{2}$$

$r$로부터 $1/2$ 미만 떨어져 있으므로, 예상대로 반올림하면 $r$을 얻습니다.

아쉽게도 $r$을 아직 모르기 때문에, 얼마나 많은 정확도가 필요한지 알려주는 데 $r$을 사용할 수 없습니다. 대신 $r$이 $N$보다 작아야 한다는 사실을 이용하여 충분한 정밀도를 사용하도록 할 수 있습니다. 특히, $1/r$에 대한 최적 근사값 $y/2^m$이 다음을 만족하도록 충분한 정확도를 사용하면

$$\left\vert \frac{y}{2^m} - \frac{1}{r} \right\vert \leq \frac{1}{2N^2},$$

역수를 취할 때 $r$을 올바르게 결정하기에 충분한 정밀도를 갖게 됩니다. $m = 2\operatorname{lg}(N)+1$로 설정하면, 앞서 설명한 방법을 사용하여 이 정밀도의 추정을 얻을 높은 확률이 보장됩니다. ($m = 2\operatorname{lg}(N)$으로 설정해도 성공 확률의 하한 40%에 만족한다면 충분합니다.)

일반적인 풀이

방금 살펴본 바와 같이, $M_a$의 고유 벡터 $\vert \psi_1 \rangle$을 갖고 있다면, 충분한 정밀도를 위해 충분한 수의 제어 Qubit를 사용하는 한 위상 추정을 통해 $r$을 알 수 있습니다. 아쉽게도 고유 벡터 $\vert\psi_1\rangle$을 구하기가 쉽지 않으므로 어떻게 진행할지 알아내야 합니다.

잠시 위와 같이 진행하되, 생각해 볼 $k\in\{0,\ldots,r-1\}$의 임의 선택에 대해 $\vert\psi_1\rangle$ 대신 고유 벡터 $\vert\psi_k\rangle$을 사용한다고 가정해 보겠습니다. 위상 추정 절차에서 얻는 결과는 다음의 근사값이 됩니다.

$$\frac{y}{2^m} \approx \frac{k}{r}.$$

$k$와 $r$을 모두 모른다는 가정 하에, 이것이 $r$을 식별하는 데 도움이 될 수도 있고 그렇지 않을 수도 있습니다. 예를 들어, $k = 0$이면 $0$에 대한 근사값 $y/2^m$을 얻는데, 안타깝게도 이것은 아무것도 알려주지 않습니다. 그러나 이것은 특이한 경우이며, 다른 $k$ 값에 대해서는 적어도 $r$에 대해 무언가를 알 수 있습니다.

연분수 알고리즘으로 알려진 알고리즘을 사용하여 근사값 $y/2^m$을 인근 분수들로 변환할 수 있습니다 — 근사값이 충분히 정확하다면 $k/r$을 포함하여 말이죠. 여기서는 연분수 알고리즘을 설명하지 않겠습니다. 대신, 이 알고리즘에 대한 알려진 사실의 진술을 소개합니다.

사실

정수 $N\geq 2$와 실수 $\alpha\in(0,1)$가 주어졌을 때, $v\neq 0$이고 $\gcd(u,v)=1$이며 $\vert \alpha - u/v\vert < \frac{1}{2N^2}$를 만족하는 $u,v\in\{0,\ldots,N-1\}$인 정수 선택은 최대 하나입니다. $\alpha$와 $N$이 주어지면, 연분수 알고리즘은 $u$와 $v$를 찾거나, 존재하지 않으면 그렇다고 알려줍니다. 이 알고리즘은 크기 $O((\operatorname{lg}(N))^3)$의 불리언 Circuit으로 구현할 수 있습니다.

$k/r$에 매우 가까운 근사값 $y/2^m$이 있고, $N$과 $\alpha = y/2^m$에 대해 연분수 알고리즘을 실행하면 사실에서 설명한 $u$와 $v$를 얻습니다. 사실에 대한 분석을 통해 다음을 결론지을 수 있습니다.

$$\frac{u}{v} = \frac{k}{r}.$$

특히 $k$와 $r$을 반드시 알 수 있는 것이 아니라, 기약분수 형태의 $k/r$만 알 수 있음에 주목하세요.

예를 들어, 이미 살펴본 바와 같이 $k=0$에서는 아무것도 알 수 없습니다. 하지만 그것이 그런 경우가 발생하는 유일한 $k$ 값입니다. $k$가 0이 아닌 경우, $r$과 공약수를 가질 수 있지만, 연분수 알고리즘에서 얻는 수 $v$는 적어도 $r$의 약수가 됩니다.

명백하지는 않지만, $k\in\{0,\ldots,r-1\}$이 균등 무작위로 선택될 때 $u/v = k/r$에 대한 $u$와 $v$를 알 수 있는 능력이 있다면, 몇 번의 샘플만으로도 $r$을 높은 확률로 복원할 수 있습니다. 특히, 관찰한 분모 $v$의 모든 값의 최소공배수를 $r$의 추측으로 사용하면 높은 확률로 맞습니다. 직관적으로 말하면, 일부 $k$ 값은 $r$과 공약수를 공유하기 때문에 좋지 않으며, $u$와 $v$를 알게 될 때 그 공약수들이 숨겨집니다. 하지만 무작위 $k$ 선택은 $r$의 인수를 오랫동안 숨기지 않을 가능성이 높으며, 관찰한 분모들의 최소공배수를 취하여 $r$을 올바르게 추측하지 못할 확률은 샘플 수에 대해 지수적으로 감소합니다.

고유 벡터 $\vert\psi_k\rangle$를 어떻게 구해서 위상 추정 절차를 실행하는가의 문제가 남아 있습니다. 알고 보면, 실제로 이 고유 벡터들을 생성할 필요가 없습니다!

대신에 할 일은, 고유 벡터 $\vert\psi\rangle$ 대신 $n$비트 이진 인코딩으로 나타낸 숫자 $1$을 의미하는 상태 $\vert 1\rangle$로 위상 추정 절차를 실행하는 것입니다. 지금까지 특정 고유 벡터에 대해서만 위상 추정 절차를 실행하는 것에 대해 이야기했지만, $M_a$의 고유 벡터가 아닌 입력 상태에도 이 절차를 실행하는 것을 막을 것은 없습니다. 그것이 바로 여기서 상태 $\vert 1\rangle$로 하려는 것입니다. (이것은 $a=1$이 아닌 한 $M_a$의 고유 벡터가 아니며, $a=1$은 우리가 관심 있는 선택이 아닙니다.)

$M_a$의 고유 벡터 대신 상태 $\vert 1\rangle$을 선택하는 근거는 다음 방정식이 성립하기 때문입니다.

$$\vert 1\rangle = \frac{1}{\sqrt{r}} \sum_{k = 0}^{r-1} \vert \psi_k\rangle$$

이 방정식을 확인하는 한 가지 방법은 양쪽을 각 표준 기저 상태와의 내적으로 비교하는 것입니다. 우변의 결과를 평가하기 위해 강의에서 앞서 언급한 공식을 활용합니다. 결과적으로, $k\in\{0,\ldots,r-1\}$을 균등 무작위로 선택하여 $\vert\psi_k\rangle$을 고유 벡터로 사용한 것과 정확히 동일한 측정 결과를 얻게 됩니다.

더 자세히 설명하면, 고유 벡터 $\vert\psi_k\rangle$ 중 하나 대신 상태 $\vert 1\rangle$로 위상 추정 절차를 실행한다고 상상해 보겠습니다. 역 양자 푸리에 변환이 수행된 후, 다음 상태가 남습니다.

$$\frac{1}{\sqrt{r}} \sum_{k = 0}^{r-1} \vert \psi_k\rangle \vert \gamma_k\rangle,$$

여기서

$$\vert\gamma_k\rangle = \frac{1}{2^m} \sum_{y=0}^{2^m - 1} \sum_{x=0}^{2^m-1} e^{2\pi i x (k/r - y/2^m)} \vert y\rangle$$

입니다.

벡터 $\vert\gamma_k\rangle$는 상위 $m$개의 Qubit에 역 양자 푸리에 변환이 수행된 후 해당 Qubit들의 상태를 나타냅니다.

따라서 $\{\vert\psi_0\rangle,\ldots,\vert\psi_{r-1}\rangle\}$이 정규 직교 집합이라는 사실 덕분에, 상위 $m$개의 Qubit를 측정하면 균등 무작위로 선택된 $k\in\{0,\ldots,r-1\}$에 대한 $k/r$ 값의 근사값 $y/2^m$을 얻습니다. 이미 논의한 바와 같이, 이를 통해 여러 번의 독립적인 실행 후 높은 신뢰도로 $r$을 알 수 있으며, 이것이 우리의 목표였습니다.

총 비용

각 제어 유니터리 $M_a^k$를 구현하는 비용은 $O(n^2)$입니다. 제어 유니터리 연산이 $m$개 있고 $m = O(n)$이므로, 제어 유니터리 연산의 총 비용은 $O(n^3)$입니다. 또한 $m$개의 Hadamard Gate가 있으며(비용 $O(n)$에 기여), 역 양자 푸리에 변환은 비용에 $O(n^2)$를 기여합니다. 따라서 제어 유니터리 연산의 비용이 전체 절차의 비용을 지배합니다 — 따라서 총 비용은 $O(n^3)$입니다.

양자 Circuit 자체 외에도, 진행하면서 수행해야 할 고전적 계산이 몇 가지 있습니다. 여기에는 제어 유니터리 게이트를 생성하는 데 필요한 $k = 2, 4, 8, \ldots, 2^{m-1}$에 대한 $\mathbb{Z}_N$에서의 거듭제곱 $a^k$ 계산과, $\theta$의 근사값을 분수로 변환하는 연분수 알고리즘이 포함됩니다. 이 계산들은 총 비용 $O(n^3)$의 불리언 Circuit으로 수행할 수 있습니다.

일반적으로, 이 모든 한계는 점근적으로 빠른 알고리즘을 사용하면 개선할 수 있습니다. 이 한계들은 기본 산술 연산에 표준 알고리즘을 사용한다고 가정합니다.

소인수분해와 위수 구하기

이제 마지막으로 논의해야 할 것은 위수 구하기 문제를 해결하는 것이 소인수분해에 어떻게 도움이 되는지입니다. 이 부분은 완전히 고전적인 방법으로, 양자 컴퓨팅과는 직접적인 관련이 없습니다.

기본 아이디어는 다음과 같습니다. 우리는 수 $N$을 인수분해하고자 하며, 이것을 재귀적으로 수행할 수 있습니다. 구체적으로, $N$을 분리하는 작업에 집중할 수 있습니다. 즉, $N = bc$를 만족하는 두 정수 $b,c\geq 2$를 찾는 것입니다. $N$이 소수라면 이것은 불가능하지만, 먼저 소수 판별 알고리즘을 사용하여 $N$이 소수인지 효율적으로 검사할 수 있으며, $N$이 소수가 아니라면 분리를 시도합니다. $N$을 분리하고 나면, 모든 인수가 소수가 될 때까지 $b$와 $c$에 대해 재귀적으로 진행하여 $N$의 소인수분해를 얻을 수 있습니다.

짝수를 분리하는 것은 쉽습니다: 그냥 $2$와 $N/2$를 출력하면 됩니다.

완전 거듭제곱수, 즉 정수 $s,j\geq 2$에 대해 $N = s^j$ 형태인 수를 분리하는 것도 쉽습니다. $N^{1/2},$ $N^{1/3},$ $N^{1/4}$ 등의 거듭제곱근을 근사하고, 근처의 정수들을 $s$의 후보로 확인하면 됩니다. 이 수열에서 $\log(N)$ 단계 이상으로 나아갈 필요는 없는데, 그 시점에서 거듭제곱근이 $2$ 아래로 내려가 추가적인 후보를 제공하지 않기 때문입니다.

이 두 가지를 처리할 수 있다는 것은 다행입니다. 위수 구하기는 짝수나 $s$가 소수인 소수 거듭제곱수의 인수분해에는 도움이 되지 않기 때문입니다. 그러나 $N$이 홀수이고 소수 거듭제곱수가 아니라면, 위수 구하기를 통해 $N$을 분리할 수 있습니다.

소수 거듭제곱수가 아닌 홀수 합성수 N을 분리하는 확률적 알고리즘

1. $a\in\{2,\ldots,N-1\}$을 무작위로 선택합니다.

2. $d=\gcd(a,N)$을 계산합니다.

3. $d > 1$이면 $b = d$와 $c = N/d$를 출력하고 중단합니다. 그렇지 않으면 $a\in\mathbb{Z}_N^{\ast}$임을 알고 다음 단계로 진행합니다.

4. $r$을 $N$에 대한 $a$의 위수로 설정합니다. (여기서 위수 구하기가 필요합니다.)

5. $r$이 짝수이면:

   5.1 $x = a^{r/2} - 1$을 $N$으로 나눈 나머지로 계산합니다.
   5.2 $d = \gcd(x,N)$을 계산합니다.
   5.3 $d>1$이면 $b=d$와 $c = N/d$를 출력하고 중단합니다.

6. 이 지점에 도달하면, 알고리즘은 $N$의 인수를 찾는 데 실패한 것입니다.

이 알고리즘의 실행은 $N$의 인수를 찾는 데 실패할 수 있습니다. 구체적으로, 이것은 두 가지 상황에서 발생합니다:

• $N$에 대한 $a$의 위수가 홀수인 경우.
• $N$에 대한 $a$의 위수가 짝수이고 $\gcd\bigl(a^{r/2} - 1, N\bigr) = 1$인 경우.

기본적인 정수론을 사용하면, 무작위 선택 $a$에 대해 이 두 사건 중 어느 것도 발생하지 않을 확률이 적어도 $1/2$임을 증명할 수 있습니다. 사실, 두 사건 중 하나가 발생할 확률은 $N$의 서로 다른 소인수의 개수 $m$에 대해 최대 $2^{-(m-1)}$입니다. 이것이 $N$이 소수 거듭제곱수가 아니어야 한다는 가정이 필요한 이유입니다. ($N$이 홀수여야 한다는 가정도 이 사실이 성립하기 위해 필요합니다.)

이는 각 실행마다 $N$을 분리할 확률이 적어도 50%임을 의미합니다. 따라서 알고리즘을 $t$번 실행하면서 매번 $a$를 무작위로 선택하면, 확률 $1 - 2^{-t}$ 이상으로 $N$을 분리하는 데 성공합니다.

알고리즘의 기본 아이디어는 다음과 같습니다. $N$에 대한 $a$의 위수 $r$이 짝수인 $a$의 선택이 있다면, $r/2$는 정수이고 다음 수들을 고려할 수 있습니다.

$$a^{r/2} - 1\; (\textrm{mod}\; N) \quad \text{and} \quad a^{r/2} + 1\; (\textrm{mod}\; N).$$

공식 $Z^2 - 1 = (Z+1)(Z-1)$을 사용하면, 다음을 알 수 있습니다.

$$\bigl(a^{r/2} - 1\bigr) \bigl(a^{r/2} + 1\bigr) = a^r - 1.$$

이제, 위수의 정의에 의해 $a^r \; (\textrm{mod}\; N) = 1$임을 알고 있습니다 — 이것은 $N$이 $a^r - 1$을 나누어 떨어지게 한다는 또 다른 표현입니다. 이는 $N$이 다음 곱을 나누어 떨어지게 함을 의미합니다.

$$\bigl(a^{r/2} - 1\bigr) \bigl(a^{r/2} + 1\bigr).$$

이것이 성립하려면, $N$의 모든 소인수가 $a^{r/2} - 1$ 또는 $a^{r/2} + 1$ (또는 둘 다)의 소인수이기도 해야 합니다 — 그리고 무작위 선택 $a$에 대해서는 $N$의 모든 소인수가 두 항 중 하나를 나누고 다른 항은 나누지 않을 가능성은 낮습니다. 그렇지 않고, $N$의 소인수 중 일부가 첫 번째 항을 나누고 일부가 두 번째 항을 나누는 한, 첫 번째 항과의 GCD를 계산함으로써 $N$의 비자명한 인수를 찾을 수 있습니다.