Quantum Algorithm #2

3. Quantum Phase Estimation

Quantum Phase Estimation$($이하 QPE$)$는 말 그대로 연산자의 phase를 측정하는 방법이다. 일반적으로 양자역학에서 쓰이는 연산자는 유니터리 연산자이기 때문에 연산자의 고유값은 norm이 1이여야한다. 이를 표현하는 가장 좋은 방법은 $U = e^{2 \pi i \theta}$이다. 여기서 우리는 $\theta$를 구하고 싶은 것이다.

전체적인 회로는 다음과 같다. 전체 회로 결과가 어떻게 되는지는 모르더라도, 지금까지 공부한 지식 덕분에 해당 gate들이 어떤 operation을 수행하는지는 파악할 수 있다. 그럼 본격적으로 차근차근 $\theta$를 찾아보자.

 

1. Setup: $\left| \psi \right\rangle$는 qubit registers 중 하나에 저장된 상태이다. 추가로 $n(=t)$개의 qubits이 존재하기 때문에 초기 상태는 다음과 같다.

$$ \left| \psi_{0} \right\rangle = \left| 0 \right\rangle^{\otimes n} \left| \psi \right\rangle $$

2. Superposition: $H^{\otimes n}$을 가하자.

$$ \left| \psi_{1} \right\rangle = {1 \over \sqrt{2^{n}}} \left( \left| 0 \right\rangle  + \left| 1 \right\rangle \right)^{\otimes n} \left| \psi \right\rangle $$

3. Controlled Unitary Operations:

$$ \left| \psi_{2} \right\rangle = {1 \over \sqrt{2^{n}}} \left( \left| 0 \right\rangle + e^{2 \pi i \theta 2^{n-1}}  \left| 1 \right\rangle \right) \otimes \cdots \otimes \left( \left| 0 \right\rangle + e^{2 \pi i \theta 2^{1}}  \left| 1 \right\rangle \right) \otimes \left( \left| 0 \right\rangle + e^{2 \pi i \theta 2^{0}}  \left| 1 \right\rangle \right) \otimes \left| \psi \right\rangle $$

$$ = {1 \over \sqrt{2^{n}} } \overset{2^{n}-1}{\underset{k=0}{\sum}} e^{2 \pi i \theta k} \left| k \right\rangle  \otimes \left| \psi \right\rangle $$

$ \because U^{2^{j}} \left| \psi \right\rangle = (e^{2 \pi i \theta})^{2^{j}} \left| \psi \right\rangle = e^{2 \pi i \theta 2^{j}} \left| \psi \right\rangle$ where $0 \le j \le n-1 $

4. Inverse Fourier Transformation:

Recall QFT

$$ QFT = {1 \over \sqrt{2^{n}}} \underset{k,x}{\sum} e^{{2 \pi i \over 2^{n}} xk} \left| k \right\rangle \left\langle x \right| $$

$$ QFT^{\dagger} = {1 \over \sqrt{2^{n}}} \underset{k,x}{\sum} e^{-{2 \pi i \over 2^{n}} kx} \left| x \right\rangle \left\langle k \right| $$

$$ \left| \psi_{3} \right\rangle = QFT^{\dagger} \left| \psi_{2} \right\rangle = \left( {1 \over \sqrt{2^{n}}} \underset{k',x}{\sum} e^{-{2 \pi i \over 2^{n}} k'x} \left| x \right\rangle \left\langle k' \right| \right) \left( {1 \over \sqrt{2^{n}} } \overset{2^{n}-1}{\underset{k=0}{\sum}} e^{2 \pi i \theta k} \left| k \right\rangle  \otimes \left| \psi \right\rangle \right) $$

$$ = {1 \over 2^{n}} \underset{k, k',x}{\sum} e^{-{2 \pi i \over 2^{n}} k'x} e^{2 \pi i \theta k} \left| x \right\rangle \left\langle k'| k \right\rangle \otimes \left| \psi \right\rangle $$

$$ = {1 \over 2^{n}} \underset{k, k',x}{\sum} e^{-{2 \pi i \over 2^{n}} k'x} e^{2 \pi i \theta k} \left| x \right\rangle \delta_{kk'} \otimes \left| \psi \right\rangle $$

$$ = {1 \over 2^{n}} \underset{k,x}{\sum} e^{-{2 \pi i \over 2^{n}} kx} e^{2 \pi i \theta k} \left| x \right\rangle \otimes \left| \psi \right\rangle $$

$$ = {1 \over 2^{n}} \underset{k,x}{\sum} e^{-{2 \pi i k \over 2^{n}} (x - 2^{n} \theta)} \left| x \right\rangle \otimes \left| \psi \right\rangle $$

5. Measure:

$ \left| \psi_{3} \right\rangle $를 측정하면 가장 높은 확률로 관측되는 상태는 

$$ \left| \psi_{4} \right\rangle = \left| 2^{n} \theta \right\rangle \otimes \left| \psi \right\rangle $$

이다. $2^{n} \theta$가 정수가 아닐 경우는, 올림하거나 내림한 가장 가까운 정수들이 높은 확률을 갖게 된다. 이로써 우리는 QPE를 이해했다. 이는 바로 다음에 이어지는 Shor's Algorithm에 이용된다.

 

4. Shor's Algorithm

쇼어 알고리즘은 인수분해 알고리즘이라고는 하지만 실제로는 주기를 찾는 알고리즘에 가깝다. $mod N$을 연산으로 사용하는 group은 $\mathbb{Z}_{N}$이 있다. 이는 유한체이기 때문에 $\mathbb{Z}_{N}^{*}$는 순환군이다. 순환군의 부분군 역시 순환군이다. 따라서 $\mathbb{Z}_{N}^{*}$의 한 원소$a$를 generator로 하여 발생하는 부분군은 유한 순환군이다. 이를 정리하면 다음과 같다.

$$ ^{\forall} a \in \mathbb{Z}_{N}^{*}, ^{\exists} r \in \mathbb{Z}_{N}^{*}\ s.t. \ a^{r} \equiv 1 (mod N). $$

$ \Rightarrow (a^{r} - 1) \equiv 0 (mod N) $

$ \Rightarrow N \mid (a^{r}-1)$

만약 r이 짝수라면, $ a^{r} - 1 = (a^{r/2} - 1)(a^{r/2}+1). $

$$ \therefore gcd(a^{r/2} \pm 1, N) \mid N.$$

이를 $a=7, N=15$에 적용하면, $gcd(7^{2} \pm 1, 15) \mid 15$임을 알 수 있고, 15의 인수는 3과 5임을 파악할 수 있다. 그럼 본격적으로 Shor's Algorithm을 통해 $r$을 구하는 방법에 대해 알아보자.

 

유니터리 연산자 $U$를 다음과 같이 정의한다.

$$ U \left| y \right\rangle \underset{def}{=} \left| ay\ (mod\ N) \right\rangle. $$

앞선 유한체에서의 논의에 의해 $U$에 의해 생성되는 ket들은 $r$개로 유한하다. 이를 동등한 위상으로 중첩 시킨 ket을 적어보자.

$$ \left| u_{0} \right\rangle = {1 \over \sqrt{r}} \underset{k=0}{\overset{r-1}{\sum}} \left| a^{k}\ (mod\ N) \right\rangle. $$

이제는 동등한 위상이 아닌 각 ket들에 위상의 차이를 주고, 이를 동일한 확률을 갖도록 중첩시켜보자.

$$ \left| u_{s} \right\rangle = {1 \over \sqrt{r}} \underset{k=0}{\overset{r-1}{\sum}} e^{-2 \pi i {s k \over r}}\left| a^{k}\ (mod\ N) \right\rangle. $$

$$ \Rightarrow U \left| u_{s} \right\rangle = e^{2 \pi i {s \over r}}\left| u_{s} \right\rangle. $$

where $0 \le s \le r-1$.

그리고 이 $\left| u_{s} \right\rangle$들을 동일한 위상을 갖도록 중첩하여 initial state $\left| 1 \right\rangle$를 구하자. 

$$ \left| 1 \right\rangle = {1 \over \sqrt{r}} \underset{s=0}{\overset{r-1}{\sum}} \left| u_{s} \right\rangle. $$

이후 $\left| 1 \right\rangle$ 에 QPE를 가하면 우리는 

$$ \phi = {s \over r} $$

를 얻게 된다. 이때 $r$은 주기이고, $s$는 $1$과 $r-1$ 사이의 정수이다. 여러 측정을 통해 $\phi$ 값들을 분수 값으로 얻고, 결과 값을 바탕으로 $r$을 맞출 수 있는 것이다. $r$을 구하고 난 이후에는 도입부에 소개한 방법을 통해서 인수를 구하면 된다.  그리고 만약 $r$이 짝수가 아니라면, 다른 a, N의 조합으로 적절한 인수를 구할 때까지 이 과정을 반복하면 된다.