양자 푸리에 변환 직관적 이해

개념 소개

고전 신호 처리에서 이산 푸리에 변환(DFT)은 시간 영역의 신호를 주파수 성분으로 분해한다. 음악 파일의 스펙트럼을 분석하거나, 이미지에서 반복 패턴을 추출하는 것이 대표적 예다.

양자 푸리에 변환(QFT, Quantum Fourier Transform)은 동일한 수학적 연산을 큐비트 상태에 적용한다. 핵심 차이는 **위상(phase)**의 역할이다. 고전 DFT가 숫자 배열을 변환한다면, QFT는 큐비트의 진폭에 인코딩된 정보를 주파수 공간으로 보내되, 변환 결과를 각 큐비트의 상대 위상 안에 저장한다.

복잡도 측면에서 QFT의 위력이 드러난다. 고전 고속 푸리에 변환(FFT)이 $N$개의 원소를 처리하는 데 $O(N\log N)$ 연산이 필요한 반면, QFT는 $n$개의 큐비트($N=2^n$)에 대해 $O(n^2)$개의 양자 게이트만으로 동일한 변환을 수행한다. 이는 입력 크기에 대해 지수적 속도 향상이다.

---

핵심 원리

수학적 정의

$n$개의 큐비트가 이루는 계산 기저 상태 $|j⟩$ ($j=0,1,\dots ,N-1$, $N=2^n$)에 대한 QFT는 다음과 같이 정의된다.

$$\text{QFT}|j⟩=\frac{1}{\sqrt{N}}\sum _{k=0}^{N-1}{e}^{2\pi ijk/N}|k⟩$$

고전 DFT와 구조가 같다. 차이는 입력·출력 모두 양자 상태라는 점이다.

텐서 곱 분해: 회로의 핵심

QFT 회로 구현을 가능하게 하는 핵심은 다음 곱 형태 분해다.

$$\text{QFT}|j⟩=\frac{1}{2^{n/2}}\underset{l=1}{\overset{n}{⨂}}\left(|0⟩+e^{2\pi ij/2^l}|1⟩\right)$$

이 식은 결과 상태가 각 큐비트가 서로 다른 위상을 가진 중첩 상태들의 텐서 곱임을 보여준다. $l$번째 큐비트는 $e^{2\pi ij/2^l}$라는 위상을 담으며, 이는 해당 주파수 성분에 대응한다. 얽힘 없이 각 큐비트를 독립적으로 처리할 수 있다는 점이 지수적 효율의 근원이다.

회로 구성: H 게이트와 제어 위상 회전

QFT 회로는 두 종류의 게이트로 구성된다.

아다마르 게이트 $H$: 큐비트를 균등 중첩으로 만든다.

$$H=\frac{1}{\sqrt{2}}\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right)$$

제어 위상 회전 게이트 $R_k$: $k$가 클수록 더 미세한 위상을 더한다.

$$R_k=\left(\begin{array}{cc}1& 0\\ 0& e^{2\pi i/2^k}\end{array}\right)$$

3-큐비트 QFT 회로의 진행 순서는 다음과 같다.

1. 큐비트 0에 $H$ 적용
2. 큐비트 1이 제어, 큐비트 0이 타깃인 $R_2$ 적용
3. 큐비트 2가 제어, 큐비트 0이 타깃인 $R_3$ 적용
4. 큐비트 1에 $H$ 적용 후, 큐비트 2가 제어하는 $R_2$ 적용
5. 큐비트 2에 $H$ 적용
6. SWAP 게이트로 큐비트 순서 역전 (비트 반전 정렬)

전체 게이트 수는 $H$가 $n$개, 제어 위상 게이트가 $\frac{n(n-1)}{2}$개로, 합산 시 $O(n^2)$이 된다.

Qiskit을 이용한 구현 예시는 다음과 같다.

from qiskit import QuantumCircuit
import numpy as np

def qft_circuit(n):
    qc = QuantumCircuit(n)
    for qubit in range(n):
        qc.h(qubit)
        for k in range(qubit + 1, n):
            angle = 2 * np.pi / (2 ** (k - qubit + 1))
            qc.cp(angle, k, qubit)  # controlled phase rotation
    # SWAP으로 큐비트 순서 역전
    for i in range(n // 2):
        qc.swap(i, n - i - 1)
    return qc

qc = qft_circuit(3)
print(qc.draw('text'))

---

예시·응용

상태 $|5⟩$에 3-큐비트 QFT 적용

$n=3$, $j=5$ ($5=101_2$)일 때 텐서 곱 분해를 적용하면:

$$\text{QFT}|5⟩=\frac{1}{2\sqrt{2}}\left(|0⟩+e^{i\cdot 5\pi /4}|1⟩\right)\otimes \left(|0⟩+e^{i\cdot 5\pi /2}|1⟩\right)\otimes \left(|0⟩+e^{i\cdot 5\pi }|1⟩\right)$$

각 큐비트는 서로 다른 위상을 가지며, 이 위상들 안에 입력값 $5$에 관한 주파수 정보가 인코딩되어 있다.

양자 위상 추정 (QPE)

QFT의 가장 중요한 응용은 **양자 위상 추정(Quantum Phase Estimation)**이다. 유니터리 연산자 $U$의 고유벡터 $|\psi ⟩$에 대해 $U|\psi ⟩=e^{2\pi i\theta }|\psi ⟩$를 만족하는 미지의 위상 $\theta$를 추정하는 문제에서, QFT의 역변환(IQFT)이 핵심 역할을 한다. QPE는 양자 화학 시뮬레이션에서 분자의 에너지 준위를 계산할 때도 필수적으로 사용된다.

Shor 알고리즘과의 연결

Shor의 인수분해 알고리즘에서 QFT는 주기 찾기(period finding) 단계에 사용된다. 함수 $f(x)=a^x\mathrm{mod}N$의 주기를 찾는 것이 핵심인데, 이 주기성은 QFT를 거치면 주파수 공간에서 날카로운 피크로 나타난다. 고전 컴퓨터에서 지수 시간이 걸리는 인수분해를 다항 시간으로 줄이는 것이 바로 QFT 덕분이다.

---

정리

양자 푸리에 변환은 고전 DFT의 양자 버전으로, 중첩과 위상을 이용해 $O(n^2)$개의 게이트만으로 $2^n$ 크기의 변환을 수행한다. 텐서 곱 분해를 통해 각 큐비트를 독립적으로 처리할 수 있다는 점이 효율성의 근원이며, 아다마르 게이트와 제어 위상 회전 게이트의 단순한 조합이 전체 회로를 구성한다. QFT는 그 자체로 출력을 직접 읽어내기 어렵지만, 위상 추정과 Shor 알고리즘의 서브루틴으로서 양자 컴퓨팅의 지수적 속도 향상을 실현하는 핵심 도구이다.