쇼어 알고리즘

What is Shor's algorithm?

다항시간 내에 인수분해를 할 수 있는 알고리즘.

In & Out

input: 양의 정수 N.
output: N=pq 인 인수 p, q

Procedure

1. (고전 컴퓨터로) N과 서로소이며 1<a<N 인 임의의 양의 정수 a 를 고른다.

2. (양자 컴퓨터로) $f(x) = a^{x}$ mod N 이라는 주기함수에 대해, 함수의 주기 r을 구한다.

3. (고전 컴퓨터로) 주기 r이 홀수라면 1번 절차로 돌아간다.
   r이 짝수라면 great common devisor(최대공약수), $gcd(a^{r/2}-1,N)$ 와 $gcd(a^{r/2}+1,N)$ 를 계산한다. 이때 gcd가 1이거나 N이면 1번 절차로 돌아간다.
   아닌 경우, gcd가 N의 인수이다.

1번 절차의 소인수 판별과 3번 절차에서 gcd 를 구하는 계산은 고전 컴퓨터 알고리즘에서도 다항시간내에 계산이 가능하다.
하지만 2번 절차의 경우 $2^{n}$ 형태로 증가하는 숫자에 대해 고전 알고리즘을 사용하면 exponential 한 계산복잡도를 가진다.
양자 컴퓨터의 경우 $2^{n}$이어도 다항시간 복잡도를 가진다.

Mathematical Formulae

Euler $\phi$ function

$\phi(N)$ : N과 서로소(coprime)인 1부터 N 까지의 정수의 갯수.
$\phi(15)$ 에 해당하는 정수는 1, 2, 4, 7, 8, 11, 13, 14 로 $\phi(15)=8$이다.

Operator U

주기함수에 대해, 다음 스텝으로 보내는 오퍼레이터를 U라고 하자.
예를 들어 a=7, N=15 인 경우, $7^{x}$ mod 15 는 1, 7, 4, 13, 1, ... 이런 주기성을 가진다.
이 경우 $U|1\rangle=|7\rangle$, $U^{2}|1\rangle=|4\rangle$... 가 된다.
일반화 해서 표현하면 다음과 같다.

U를 통해 주기성을 가지는 state들을 superposition 하면 eigenvalue 가 1인 U의 eigenstate $|u_{0}\rangle$ 가 된다.

이때 다음과 같이 $u_{s}$를 정의하면, eigenvalue 가 $e^{\frac{(2\pi is)}{r}}$ 가 된다.

$0\leq s \leq r-1$ 이고, 만약 r이 짝수라면, $e^{ix}$의 주기성때문에 $\sum\limits_{s=0}^{r-1} \frac{1}{\sqrt{r}}|u_{s}\rangle=|1\rangle$ 이 된다.

Quantum Circuit

N=15, n=4, a=13 인 경우 소인수 분해를 위한 양자회로는 다음과 같다.

where $f_{a,N} = a^{x}$ (mod N)
second register $|w\rangle$를 target state 라고 하자.

step 0

$|0\rangle |0\rangle$

step 1

$[H^{\otimes n}|0\rangle^{\otimes n} |0\rangle]|0\rangle^{\otimes n}$
=$\frac{1}{4}[|0\rangle + |1\rangle + ... + |15\rangle]|0\rangle$

step 2

since $0\oplus z = z$,
$\frac{1}{4}[|0\rangle |0\oplus 13^{0}(mod15)\rangle + |1\rangle |0\oplus 13^{1}(mod15)\rangle + ... + |15\rangle |0\oplus 13^{15}(mod15)\rangle]$
=$\frac{1}{4}[|0\rangle|1\rangle +|1\rangle|13\rangle +|2\rangle|4\rangle +|3\rangle|7\rangle$
$+|4\rangle|1\rangle +|5\rangle|13\rangle +|6\rangle|4\rangle +|7\rangle|7\rangle$
$+|8\rangle|1\rangle +|9\rangle|13\rangle +|10\rangle|4\rangle +|11\rangle|7\rangle$
$+|12\rangle|1\rangle +|13\rangle|13\rangle +|14\rangle|4\rangle +|15\rangle|7\rangle$

step 3

after measuring w register, if $|7\rangle$ is measured :
$\frac{1}{2}[|3\rangle + |7\rangle + |11\rangle + |15\rangle]|7\rangle$

step 4

apply inverse QFT on the x register
$QFT^{\dagger}|\tilde{x}\rangle = |x\rangle = \frac{1}{\sqrt{N}}\sum\limits_{y=0}^{N-1}e^{-\frac{2\pi i}{N}xy}|y\rangle$
invers QFT on step 3 is
$\frac{1}{8}[4|0\rangle + 4i|4\rangle - 4|8\rangle -4i|12\rangle]$

step 5

measuring the $|x\rangle$ register get $|0\rangle$ or $|4\rangle$ or $|8\rangle$ or $|12\rangle$ with equal probability of $\frac{1}{4}$

measured results peak near $j\frac{N}{r}$ for some integer $j$.

If $|0\rangle$ is measured: $|0\rangle$ is trivial. If we measure $|0\rangle$, restart.

$|4\rangle$: $j\frac{N}{r}=4\rightarrow$ if $j=1$, $r=4$ and $r$ is even.
$a^{r/2}$ (mod N) = $13^{4/2}$ (mod 15) = 4
4+1=5, gcd(5,15) = 5.
4-1=3, gcd(3,15) = 3.

$|8\rangle$: $j\frac{N}{r}=8\rightarrow$ if $j=2$, $r=4$ and $r$ is even. same above. If $j=1$, $r=2$,
$a^{r/2}$ (mod N) = $13^{2/2}$ (mod 15) = 13
13+1=14, gcd(14,15) = 1.
13-1=12, gcd(12,15) = 3. 3 is factor of 15. partial solution. restart or re calculate with 15/3 = 5.

$|12\rangle$: $j\frac{N}{r}=12\rightarrow$ if $j=3$, $r=4$ and $r$ is even. same above.

4개의 결과중 2.5개의 결과가 제대로 작동한다. 일반적으로, 제대로 작동할 확률 최소 1/2 이다.

$N<2^{n}$ 이라면, 2n개의 큐빗을 이용해 소인수 분해가 가능하다

How Implements oracle $U_{f}$? $U_{f}$ is QPE.

reference
쇼어 알고리즘