양자 푸리에 변환 (Quantum Fourier Transform)

양자 푸리에 변환(QFT)은 이산 푸리에 변환(DFT)을 양자 컴퓨터를 통해 수행하는 알고리즘이다.

QFT의 시간 복잡도는 O((log N)^2)으로 고전 컴퓨터에서 FFT의 시간 복잡도 O(NlogN)에 비해 지수적으로 빠르게 수행된다. 구현은 Hadamard gate와 Controlled phase gate로 구성된다.

 

Hadamard gate

$ H=\frac{1}{\sqrt{2}}\begin{bmatrix}
1 & 1 \\
1 & -1 \\
\end{bmatrix} $

 

Controlled phase gate

$R_m=\begin{bmatrix}
1 & 0 \\
0 & \frac{2\pi i}{2m} \\
\end{bmatrix}$

 

일반적으로 DFT의 길이가 N(=2^n)인 배열에 대해 정의되는 것에 비해 QFT는 orthonormal basis |0>, |1>, ... |N-1>에 대해 다음과 같이 정의된다.