정의
$$
\mathrm{QFT}_N|x\rangle
=
{1\over\sqrt{N}}\sum_{y=0}^{N-1}e^{2\pi ixy/N}|y\rangle
$$N=2^n이면 n큐비트 회로로 구현합니다.
이진 분해
x=0.x_1x_2\dots x_n 형태의 phase로 분해하면 QFT는 Hadamard와 controlled phase rotation들의 곱으로 구현됩니다.
$$
R_k=
\begin{bmatrix}
1&0\\
0&e^{2\pi i/2^k}
\end{bmatrix}
$$회로 구조
각 큐비트에 H를 걸고, 뒤쪽 큐비트들이 앞쪽 큐비트에 작은 각도의 controlled phase를 겁니다. 마지막에는 비트 순서를 뒤집는 SWAP이 들어갑니다.
작은 각도 회전을 생략하면 approximate QFT가 됩니다. 각도가 매우 작은 controlled phase는 하드웨어에서 비싸고 잡음에 약할 수 있습니다.
Phase estimation
controlled-U^{2^k}를 사용하면 eigenphase가 counting register에 새겨집니다.
$$
U|u\rangle=e^{2\pi i\phi}|u\rangle
$$$$
{1\over\sqrt{2^m}}\sum_{k=0}^{2^m-1}e^{2\pi i k\phi}|k\rangle
\xrightarrow{\mathrm{QFT}^{-1}}
|\tilde{\phi}\rangle
$$예제: 정확히 표현되는 위상
\phi=5/8=0.101_2이고 counting register가 3큐비트면 inverse QFT 후 결과는 |101\rangle가 됩니다.
QFT의 product form
x=x_1x_2\dots x_n을 이진수로 보면 QFT 결과는 각 큐비트의 phase가 누적된 곱 상태로 표현됩니다.
$$
\mathrm{QFT}_{2^n}|x\rangle
=
{1\over 2^{n/2}}
\bigl(|0\rangle+e^{2\pi i\,0.x_n}|1\rangle\bigr)
\bigl(|0\rangle+e^{2\pi i\,0.x_{n-1}x_n}|1\rangle\bigr)
\cdots
\bigl(|0\rangle+e^{2\pi i\,0.x_1x_2\dots x_n}|1\rangle\bigr)
$$출력 큐비트 순서가 뒤집혀 나타나기 때문에 마지막에 SWAP들을 넣거나, 이후 회로가 bit-reversed order를 받아들이게 설계합니다.
3큐비트 QFT 회로 예시
3큐비트 QFT는 큰 틀에서 아래 순서입니다.
- 첫 번째 큐비트에 H
- 두 번째, 세 번째 큐비트에서 첫 번째 큐비트로 controlled phase
- 두 번째 큐비트에 H
- 세 번째 큐비트에서 두 번째 큐비트로 controlled phase
- 세 번째 큐비트에 H
- 출력 순서 보정을 위한 SWAP
controlled phase 각도는 멀리 떨어진 비트일수록 작아집니다.
$$
R_2=\begin{bmatrix}1&0\\0&e^{2\pi i/4}\end{bmatrix},
\qquad
R_3=\begin{bmatrix}1&0\\0&e^{2\pi i/8}\end{bmatrix}
$$이 작은 각도들이 이진 소수점 이하 phase를 조립합니다. 그래서 QFT를 단순히 “Hadamard 여러 개”로 보면 부족하고, controlled phase들이 주기 정보를 세밀하게 새긴다고 봐야 합니다.
inverse QFT의 역할
phase estimation에서는 counting register가 아래 상태가 됩니다.
$$
{1\over\sqrt{2^m}}\sum_{k=0}^{2^m-1}
e^{2\pi i k\phi}|k\rangle
$$이 상태는 계산기저에서 보면 모든 k에 퍼져 있지만, phase가 등차수열처럼 증가합니다. inverse QFT는 이 phase slope를 이진수 \phi로 바꿉니다.
만약 \phi=j/2^m로 정확히 표현되면 inverse QFT 뒤에는 정확히 |j\rangle가 나옵니다. 정확히 표현되지 않으면 2^m\phi에 가까운 정수 주변으로 확률분포가 생깁니다.
approximate QFT
먼 거리 controlled phase는 각도가 매우 작습니다. 예를 들어 R_k의 각도는 2\pi/2^k입니다. k가 크면 이 회전은 하드웨어 오류보다 작거나, 전체 결과에 아주 작은 영향만 줄 수 있습니다.
approximate QFT는 이런 작은 회전을 생략해 depth를 줄입니다. 이론적으로는 오차를 감수하는 대신 회로가 짧아지고, 실제 장비에서는 짧아진 회로가 오히려 더 좋은 결과를 줄 수 있습니다. 이 판단은 목표 precision, 하드웨어 오류율, 뒤에서 쓰는 continued fraction의 허용오차에 따라 달라집니다.