Shor의 알고리즘은 양자컴퓨터를 이용해 소인수분해를 빠르게 할 수 있는 알고리즘이다.
정수 N을 소인수 분해하는 문제는 $f(x) = a^{x} (modN)$ 의 주기를 찾는 문제와 같다. Shor's algorithm은 다음과 같은 순서로 소인수분해를 진행한다.
1. N보다 작은 정수 중, N과 공약수가 없는 임의의 정수 a를 선택한다.
2. Quantum computer를 사용하여 주기 r을 찾는다.
3.
$$a^r \equiv 1modN \\ a^r - 1 = 0 mod N \\ (a^{\frac{r}{2}}+1)(a^{\frac{r}{2}}-1) = 0 modN \\ \therefore gcd(a^{\frac{r}{2}}+1,N), gcd(a^{\frac{r}{2}}-1,N)$$
이 N의 소인수가 된다.
2번 과정을 더 자세히 설명하자면, 1. 먼저 Quantum computer의 초기상태를 설정해주고, 2. 다음 두번째 register를 측정한 다음, 3. 첫번째 register에 Quantum Fourier Transformation 해주어야 한다. 하나씩 해보자.
1. 먼저
$$ f(x) = a^{x} (modN) $$
에서 주기 $r$은 $a^{r} = 1modN$ 을 만족한다. 따라서 초기상태는
$$\frac{1}{\sqrt{2}}\sum_{x=0}^{2^n-1} |x>|a^x modN>$$
으로 준비한다. 첫번째 레지스터인 $|x>$ 는 n개의 qubit으로 구성되며 $\frac{1}{\sqrt{2^n}} \sum_{x=0}^{2^n-1}|x>$ 의 상태로 준비시킨다.
2. 이 때 두 번째 register를 측정하게 되면 $|a^{x_0} modN>$ 이 되고, 이 때 $x_0$는 $0$ 과 $2^{n-1}$사이의 특정한 정수이다. 한 편 이 측정으로 인해 첫번째 register는
$$\frac{1}{\sqrt{2^n/r}}(|l>+|l+r>+|l+2r>+ ... + |l+(m-1)r>)$$
으로 collapse된다. 여기서$l$은 $a^{x_0}modN$인 가장 작은 $x_0$ 이고, $m=\frac{2^n}{r}$ 이다.
3. 이 첫번째 register에 Quantum Fourier Transformation 해주면,
$$QFT\frac{1}{\sqrt{m}} \sum_{j=0}^{m-1} |l+jr> \rightarrow \frac{1}{\sqrt{m}} \sum_{j=0}^{m-1} \frac{1}{\sqrt{2^n}} \sum_{h=0}^{2^n-1} e^{2 \pi i (l+jr)h / 2^n} |h> \\ = \sum_{h=0}^{2^n-1} \frac{1}{\sqrt{r}} e^{2\pi i lh/2^n} |h>= \frac{1}{\sqrt{r}} \sum_{q=0}^{r-1} e^{2\pi l q /r } |q \frac{2}{r}>$$
이 된다. 즉, 측정하면 $\frac{1}{\sqrt{r}}$ 이 Peak의 개수로 나타나고, 이것이 곧 주기이다.
1. 나는 15를 소인수 분해 하려고 한다. 그래서 N보다 작은 정수 중, N과 공약수가 없는 임의의 정수 a=4 를 선택했다. 따라서
$$f(x) = 4^{x}mod15, \ n=3$$
$$\frac{1}{\sqrt{2^3}} \sum_{x=0}^{2^3-1} |x> |4^x mod 15> = \frac{1}{\sqrt{8}} \sum_{x=0}^{7} |x> |4^x mod 15> = \frac{1}{\sqrt{8}}(|0>|1> + |1>|4>+ |2>|1> + ... + |7>|4>)$$
이 된다.
2-1. 두 번째 register를 측정해서 |4> 가 나왔다고 가정하자. 그렇다면 첫 번째 register는
$$\frac{1}{\sqrt{4}}(|1> + |3> + |5> + |7>) = \frac{1}{4} \sum_{j=0}^{3} |1+2j>$$
로 붕괴된다.
3-1. 첫 번째 register에 Fourier Transformation 해주면,
$$QFT \frac{1}{\sqrt{4}} \sum_{j=0}^3 |1+2j> = \frac{1}{\sqrt{4}} \sum_{j=0}^3 \frac{1}{\sqrt{2^3}} \sum_{h=0}^{7} e^{2 \pi i (1+2j)h/8} |h> = \sum_{h=0}^7 \frac{1}{\sqrt{2}} e^{2\pi i h/8} |h> = \frac{1}{\sqrt{2}} \sum_{q=0}^1 e^{2\pi i q/2} |q 2^2> = \frac{1}{\sqrt{2}} (|0> - |4>)$$
2-2. 이번에는 두 번째 register를 측정해서 |1> 가 나왔다고 가정하자. 그렇다면 첫 번째 register는
$$\frac{1}{\sqrt{4}} (|0> + |2> + |4> + |6>) = \frac{1}{\sqrt{4}} \sum_{j=0}^3 |2j>$$
로 붕괴된다.
3-2 다음, 첫번째 register에 Fourier Transformation 해주면,
$$ QFT \frac{1}{\sqrt{4}} \sum_{j=0}^3 |2j> = \frac{1}{\sqrt{4}} \sum_{j=0}^3 \frac{1}{\sqrt{2^3}} \sum_{h=0}^7 e^{2\pi i jh/8} |h> = \frac{1}{\sqrt{32}}\cdot 4 (|0> + |4>) = \frac{1}{\sqrt{2}}(|0>+|4>)$$
따라서 두 경우 모두 r = 2 이므로,
$$gcd(4^{\frac{2}{2}}+1, 15), gcd(4^{\frac{2}{2}}-1, 15) = gcd(5,15),gcd(3,15) = 3,5 $$
15의 소인수인 3과 5를 구했다.
이어지는 (2)에서는 Shor's algorithm을 IBM-Q를 이용해 실제적인 회로를 구성하고, 실제 측정값을 얻어본다.
>Preview!
