양자 푸리에 변환
양자 알고리즘
우리가 해를 알고 있는 문제가 있다면, 다른 문제를 해당 문제로 변환하여 해결할 수 있으며 이러한 방식은 양자 알고리즘에도 적용된다. 이번 포스트에서 알아볼 양자 푸리에 변환도 고전 컴퓨팅에서 사용한 이산 푸리에 변환, 고속 푸리에 변환의 변형이다. 후에 알아볼 것이지만 양자 푸리에 변환이 고전 푸리에 변환처럼 파형 분석에 사용할 수 없다. 하지만 다른 양자 알고리즘 (Shor’s Algorithm, Phase Estimation)에서의 기반으로 쓰이므로 알고있어야한다.
추가적으로 필자는 양자 알고리즘에 대해 수식적으로 표현될 때 이러한 수식들로 양자회로를 구성하는데 있어 방식이 궁금하였다. 따라서 해당 글에서 예제를 통해 이를 정리할 것이다.
이산 푸리에 변환
푸리에 변환은 시간 및 공간에 대한 함수를 주파수 성분으로 변환하는 것을 말한다.
\[\boxed { x_k \rightarrow \frac{1}{\sqrt{N}}\sum_{j=0}^{N-1}x_je^{2\pi i j\frac{k}{N}} }\]위의 식은 신호 $x_j$ 에서 주파수 $k$ 성분에 대한 내적으로 볼 수 있으며, 이는 특정 주파수 성분만 뽑아내는 것으로 해석할 수 있다. 힐베르트 공간에서의 이산 내적은 $\langle \mathbf{x}, \mathbf{f}k \rangle = \sum{j=0}^{N-1} x_j \overline{f_k(j)}$ 이며, 푸리에 변환 식에서 $f(j) = x_j$, $g(j) = \dfrac{1}{\sqrt{N}}e^{2\pi i j\frac{k}{N}}$ 임을 알 수 있다. 이는 힐베르트 공간에서의 정규 직교 기저 변환하는 것이다.
양자 푸리에 변환
이제 위의 이산 푸리에 변환을 양자 푸리에 변환으로 변환하면 아래와 같다.
\[\boxed { \text{QFT: } \ket{j} \mapsto \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1} e^{2\pi i j\frac{k}{N}}\ket{k} }\]$\ket{j}$는 시$\cdot$공간에서의 벡터이며, $\ket{k}$는 주파수 영역에서의 정규 직교 기저이다.
어떠한 값 $j$는 이진 표현으로 나타낼 수 있으며 이는 아래와 같다.
\[\begin{align*} j &\mapsto j_1j_2j_3\cdots j_n \\ j &= j_1\cdot2^{n-1}+j_2\cdot2^{n-2}+\cdots+j_n2^{0} \\ 0.j_1j_2j_3\cdots j_n &\mapsto \frac{j_1}{2}+\frac{j_2}{2^2}+\cdots+\frac{j_n}{2^n} \end{align*}\]값 j를 나타내는 $n$개의 큐비트 $\ket{j_0}, \ket{j_1}, \cdots , \ket{j_{n-1}}$이 있다. $n$개의 큐비트로 나타낼 수 있는 값은 총 $2^n$이며 위 푸리에 변환식에서 $N= 2^n$임을 알 수 있다.
$n$개의 큐비트에 대한 $\text{QFT}$를 보기 전 이해를 위해 $2$큐비트의 $\text{QFT}$를 알아보자.
2큐비트 양자 푸리에 변환
2개의 큐비트 $\ket{j_0}, \ket{j_1}$에 대하여 $\ket{j} = \ket{j_1j_0}, j = j_1 \cdot 2^1 + j_0\cdot 2^0$이며, $\ket{k}$또한 $\ket{k}=\ket{k_1k_0}, k = k_1\cdot 2^1 + k_0$로 나타낼 수 있다. (앞에서 얘기했던 이진표현 방식이다.)
위 푸리에 변환식을 행렬표현으로 다음과 같이 나타낼 수 있고, 행렬의 요소는 $\frac{1}{2}e^{2\pi i (j_1 \cdot 2^1 + j_0)(k_1 \cdot 2^1 + k_0)/4}$이다.
\[\frac{1}{2} \begin{pmatrix} e^0 & e^0 & e^0 & e^0 \\ e^0 & e^{\pi i / 2} & e^{\pi i} & e^{3\pi i / 2} \\ e^0 & e^{\pi i} & e^{2\pi i} & e^{3\pi i}\\ e^0 & e^{3\pi i/2} & e^{3\pi i} & e^{9\pi i /2} \\ \end{pmatrix} = \frac{1}{2}\begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i \end{pmatrix}\]위 행렬의 행은 출력 $\ket{k}$의 상태 $\ket{00}, \ket{01}, \ket{10}, \ket{11}$ 순이며, 열은 입력 $\ket{j}$의 상태 $\ket{00},\ket{01},\ket{10},\ket{11}$ 순서대로 나타낸 것이다. 본 포스트 전체에서 이러한 규칙을 따를 것이다.
행렬의 요소를 분석하면 각 큐비트에 어떠한 게이트를 적용해야하는지 알 수 있으며 이는 이후 $n$큐비트 $\text{QFT}$의 양자 회로를 구성하는데 도움이된다.
행렬 요소 $\frac{1}{2}e^{2\pi i (j_1 \cdot 2^1 + j_0)(k_1 \cdot 2^1 + k_0)/4}$에 대하여 지수에서의 합은 곱으로 분해할 수 있다.
\[\begin{align} &\frac{1}{2}e^{2\pi i (j_1 \cdot 2^1 + j_0)(k_1 \cdot 2^1 + k_0)/4} \tag{1} \\ &= e^{2\pi i j_1k_1}\cdot \frac{1}{\sqrt{2}} e^{2\pi i j_1 k_0/2} \cdot \frac{1}{\sqrt{2}} e^{2\pi i j_0k_1/2} \cdot e^{2\pi i j_0k_0/4} \tag{2} \end{align}\]이때 $(2)$에서 $e^{2\pi i j_1 k_1}$은 $j_1, k_1$값이 각각 $0, 1$이므로 항상 $1$이 되어 생략할 수 있다. 즉 $\frac{1}{\sqrt{2}} e^{2\pi i j_1 k_0/2} \cdot \frac{1}{\sqrt{2}} e^{2\pi i j_0k_1/2} \cdot e^{2\pi i j_0k_0/4}$이다.
$\text{(i) } \frac{1}{\sqrt{2}}e^{2\pi i j_1k_0/2}$ 양자회로 구성
$j_1$의 값 ${0, 1}$에 따른 결과 $k_0$의 값 ${0, 1}$을 행렬로 표현하면
\(\frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} \mapsto \text{Hadamard gate}\) 임을 볼 수 있다. 즉 큐비트 $\ket{j_1}$에 하다마드 게이트를 적용하면 $\ket{k_0}$가 나오는 것이다. 그렇다면 회로를 다음과 같이 구성할 수 있다.
$\text{(ii) } \frac{1}{\sqrt{2}}e^{2\pi i j_0k_1/2}$ 양자회로 구성
$j_0$의 값 ${0, 1}$과 $k_1$의 값 ${0, 1}$을 행렬로 표현하면
\(\frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} \mapsto \text{Hadamard gate}\) 이며 바로 앞에서 보였던 양자회로 구성과 같다.
$\text{(iii) } e^{2\pi j_0k_0/4}$ 양자회로 구성
$j_0$의 값 ${0, 1}$과 $k_0$의 값 ${0, 1}$에 대해 살펴보자. 각 값에 대해 $e^{2\pi j_0k_0/4}$의 값은
\[e^{2\pi j_0k_0/4} = \begin{cases} i & (\text{if } j_0 = k_0=1) \\ 1 & \text{(otherwise)} \end{cases}\]이며 $\ket{j_1j_0}, \ket{k_1k_0}$에 대한 행렬로 표현하면 제어형 위상 게이트 $S$와 같다.
\[\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & i \end{pmatrix} \mapsto \text{Controlled-S gate}\]
$\text{(iv) } 2$큐비트 양자 회로 구성
하다마드 게이트와 위상 게이트를 적용했으며 결과로 $(k_0, k_1)$이 나오므로 우리가 원하는 결과 $(k_1, k_0)$가 나오기 위해서 뒤집어줘야한다. 따라서 마지막으로 $\text{SWAP}$게이트를 적용하면 $2$큐비트 QFT가 완성된다.
n 큐비트 양자 푸리에 변환
2큐비트 QFT 에서 확장해서 $n$큐비트의 경우 양자회로를 구성해보자.
$n$큐비트에 대해 $\ket{k} = \ket{k_{n-1}k_{n-2}\cdots k_0}, \ket{j} = \ket{j_{n-1}j_{n-2}\cdots j_0}$로 나타낼 수 있으며 이에 대한 푸리에 변환은 다음과 같다.
\[\begin{align} \ket{j} &\mapsto \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1} e^{2\pi j\frac{k}{N}}\ket{k} \tag{1} \\ &= \frac{1}{2^{n/2}} \sum_{k=0}^{2^n-1}\ket{k}e^{2\pi i j (k_{n-1}\cdot 2^{n-1}+k_{n-2}\cdot 2^{n-2}+\cdots + k_0\cdot 2^0) / 2^n} & (\because N= 2^{n}) \tag{2} \\ &= \frac{1}{2^{n/2}} \sum_{k=0}^{2^n-1}\ket{k}\Pi_{l=0}^{n-1} e^{2\pi i j k_l \cdot 2^{l} / 2^n} = \frac{1}{2^{n/2}} \sum_{k=0}^{2^n-1}\ket{k}\Pi_{l=0}^{n-1} e^{2\pi i j k_l/ 2^{n-l}} \tag{3} \end{align}\]이때 $\sum_{k=0}^{2^n-1}\ket{k}$는 $k$의 이진 표현 $\ket{k_m}_{m=0,1,\cdots,n-1}$의 텐서곱으로 나타낼 수 있다.
\[\begin{align} \ket{j} &\mapsto \frac{1}{2^{n/2}} \sum_{k=0}^{2^n-1}\ket{k}\Pi_{l=0}^{n-1} e^{2\pi i j k_l/ 2^{n-l}} \tag{4} \\ &= \frac{1}{\sqrt{2}}\sum_{k_{n-1} = 0}^{1} e^{2\pi i j k_{n-1}/2}\ket{k_{n-1}}\otimes\cdots\otimes \frac{1}{\sqrt{2}}\sum_{k_0 = 0}^{1} e^{2\pi i j k_0/2^n}\ket{k_0} \tag{5} \\ &= \frac{\ket{0}+e^{2\pi i j/2}\ket{1}}{\sqrt{2}}\otimes \cdots \otimes \frac{\ket{0}+e^{2\pi i j/2^n}\ket{1}}{\sqrt{2}} \tag{6} \end{align}\]$(6)$에서 볼 수 있듯이 $n$개의 큐비트에 대한 QFT연산은 각 연산 결과들의 중첩상태임을 알 수 있다.
어떤 연산이 작용하는지 $\frac{j}{2^n} = 0.j_{n-1}j_{n-2}\dots j_0 = j_{n-1}\frac{1}{2}+j_{n-2}\frac{1}{2^2} \cdots + j_0\frac{1}{2^{n}}$을 통해 위의 식에 약간의 변형을 하면
\[\begin{align} \ket{j} = \ket{j_{n-1}j_{n-2}\cdots j_0} &\mapsto \frac{\ket{0}+e^{2\pi i j/2}\ket{1}}{\sqrt{2}}\otimes \cdots \otimes \frac{\ket{0}+e^{2\pi i j/2^n}\ket{1}}{\sqrt{2}} \tag{7} \\ &= \frac{\ket{0}+e^{2\pi i (0.j_0)}\ket{1}}{\sqrt{2}}\otimes \cdots \otimes \frac{\ket{0}+e^{2\pi i (0.j_{n-1}j_{n-2}\dots j_0)}\ket{1}}{\sqrt{2}} \tag{8} \end{align}\]$\ket{k_0}=\frac{\ket{0}+e^{2\pi i (0.j_{n-1}j_{n-2}\dots j_{0})}\ket{1}}{\sqrt{2}}$에서 $e^{2 \pi i (0.j_{n-1}j_{n-2}\dots j_{0})}$ 는 회전 게이트 $R_k = \begin{pmatrix} 1 & 0 \ 0 & e^{2\pi i / 2^k} \end{pmatrix}$를 $n-1$번 적용한 것임을 알 수 있다.
위 양자 회로에서 $\ket{k_0}$의 경우를 보자. 예시를 위해 $n=3$이고 $\ket{j_2} = \ket{0}$라 했을 때 회전연산자 $R_k$는 $\ket{1}$에만 작용하므로
\[\begin{align*} \ket{0} &\mapsto \frac{\ket{0} + \ket{1}}{\sqrt{2}} \\ &\mapsto \frac{\ket{0} + e^{2\pi i (0.0j_1)} \ket{1}}{\sqrt{2}} \\ &\mapsto \frac{\ket{0} + e^{2\pi i (0.0j_1 j_0)}\ket{1}}{\sqrt{2}} \end{align*}\]위에서 구한 식과 같다는 것을 알 수 있다.
양자 푸리에 변환 시간 복잡도
양자 푸리에 변환에서의 시간 복잡도를 계산해보자. $n$큐비트 $\text{QFT}$에서 $n$개의 하다마드 게이트와 최대 $\frac{n(n-1)}{2}$개의 제어형 회전 연산자, $n/2$개의 스왑연산자가 필요하다. 따라서 시간복잡도 $O(n^2)$로 나타낼 수 있으며 $N = 2^n$이므로 $O((log N)^2)$이다.
이는 고전 컴퓨터에서의 DFT, FFT의 시간복잡도 $O(N^2), O(NlogN)$와 비교하면 속도 측면에서 더 빠름을 알 수 있다.
양자 푸리에 변환 한계
앞 섹션에서 시간복잡도 비교을 통해 양자푸리에 변환이 고전 컴퓨터에 비해 좋다는 것을 알 수 있었다. 하지만 양자 푸리에 변환을 이용하여 푸리에 변환 속도를 높이는 방법은 알려져있지않다. 가장 큰 문제점은 측정을 통해 양자 컴퓨터의 진폭에 접근할 수 없기 때문에 푸리에 변환시킨 진폭을 알아낼 방법이 없다.