양자 푸리에 변환

쇼어(Shor) 알고리즘: 정수 인수분해에서 주기 탐색 단계에 직접 사용
양자 위상 추정(QPE): 유니터리 연산자의 고유값(위상)을 정밀 측정
양자 화학·최적화: 해밀토니안 시뮬레이션의 핵심 서브루틴

고전 이산 푸리에 변환을 양자 회로로 구현한 연산으로, 계산 기저 상태의 진폭을 주파수 영역으로 변환한다. 쇼어 알고리즘 등 핵심 양자 알고리즘의 근간을 이룬다.

직관적 비유

음악에서 복잡한 소리를 '도·레·미' 각 음의 세기로 분해하듯, QFT는 양자 상태를 구성하는 **주기적 패턴(주파수 성분)**을 추출한다. 고전 컴퓨터가 악보를 한 음씩 읽는다면, QFT는 중첩을 활용해 모든 음을 동시에 분석하는 셈이다.

$N = 2^n$차원 힐베르트 공간에서 QFT는 계산 기저 상태 $|j\rangle$를 다음과 같이 변환한다.

$$\text{QFT}|j\rangle = \frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} e^{2\pi i jk/N} |k\rangle$$

이는 고전 DFT와 수학적으로 동일하나, $n$개의 큐비트에 작용하는 아다마르 게이트와 제어 위상 회전 게이트의 조합으로 $O(n^2)$ 게이트만으로 구현된다. 고전 FFT의 $O(N \log N)$에 비해 지수적으로 효율적이다.

QFT의 출력은 측정 시 직접 읽을 수 없으며, 반드시 위상 추정 등의 후처리와 결합해야 실질적인 정보를 얻을 수 있다.