양자 Fourier 변환 직관적 이해

개념 소개

고전 이산 Fourier 변환(DFT)은 $N$개의 복소수 입력을 주파수 성분으로 분해한다. FFT(고속 Fourier 변환)조차 $O(N\log N)$의 연산이 필요하다. 양자 Fourier 변환(QFT)은 $n$개의 큐비트($N=2^n$)에 대해 단 $O(n^2)$개의 게이트로 동일한 변환을 구현한다.

핵심 직관: QFT는 계산 기저의 각 상태를 특정 주파수로 "진동하는" 위상 패턴으로 매핑한다. 음악으로 비유하면, 악보(시간 영역)를 화음 스펙트럼(주파수 영역)으로 전환하는 작업이다. 다만 양자 측정의 특성상 변환 결과를 직접 읽어낼 수 없고, 위상 정보를 활용하는 알고리즘의 내부 단계로 사용된다.

---

핵심 원리

수학적 정의

계산 기저 상태 $|j⟩$ ($j=0,1,\dots ,N-1$)에 대해 QFT는 다음과 같이 정의된다.

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

선형성에 의해 임의의 중첩 상태 $|\psi ⟩={\sum }_j{x}_j|j⟩$에 적용하면, 진폭 계수 $\{x_j\}$의 DFT 결과 $\{X_k\}$를 진폭으로 가지는 상태가 출력된다.

곱 형태 표현 — 회로 설계의 열쇠

$n$비트 이진 표현 $j=j_1{2}^{n-1}+\cdots +j_n$와 이진 소수 표기 $0.j_l\cdots j_m={\sum }_s{j}_{l+s-1}/2^s$를 도입하면:

$$\text{QFT}|j⟩=\frac{1}{2^{n/2}}\underset{l=1}{\overset{n}{⨂}}\left(|0⟩+e^{2\pi i\cdot 0.j_{n-l+1}\cdots j_n}|1⟩\right)$$

각 큐비트가 $|0⟩+e^{i\varphi }|1⟩$ 형태로 독립적으로 분리된다. 이 구조가 QFT를 효율적인 회로로 구현할 수 있는 근거다.

회로 구성

회로를 구성하는 두 게이트:

• 하다마드(H) 게이트: $|0⟩\mapsto \frac{|0⟩+|1⟩}{\sqrt{2}},|1⟩\mapsto \frac{|0⟩-|1⟩}{\sqrt{2}}$
• 조건부 위상 회전 $R_k$:

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

3큐비트 QFT 회로 절차

1. $q_1$에 H 적용 → 균등 중첩 생성
2. $q_2$ 제어 $R_2$, $q_3$ 제어 $R_3$ 적용 → $q_1$ 위상 미세 조정
3. $q_2$에 H 적용, $q_3$ 제어 $R_2$ 적용
4. $q_3$에 H 적용
5. SWAP으로 비트 역순 정렬

전체 게이트 수: H $n$개, 위상 게이트 $\frac{n(n-1)}{2}$개, SWAP $\lfloor n/2\rfloor$개 → 합계 $O(n^2)$.

---

예시·응용

1큐비트 QFT = 하다마드

$n=1$이면 QFT는 하다마드 게이트 그 자체다.

$$\text{QFT}|1⟩=\frac{1}{\sqrt{2}}(|0⟩-|1⟩)=|-⟩$$

단일 큐비트에서 QFT는 주파수 "고음"을 $|-⟩$ 상태로 인코딩한다.

양자 위상 추정(QPE)

유니터리 $U$의 고유벡터 $|\psi ⟩$에 대해 $U|\psi ⟩=e^{2\pi i\phi }|\psi ⟩$일 때, QPE 알고리즘은 IQFT(QFT의 역변환)를 이용해 $\phi$를 $n$비트 정밀도로 추출한다.

쇼어 알고리즘

$N$의 소인수 분해에서 $f(x)=a^x\mathrm{mod}N$의 주기를 찾는 단계가 핵심이다. QPE를 통해 이 주기를 $O({\log }^{3}N)$ 게이트로 찾아내며, QFT가 그 중심에 있다.

Qiskit 구현 예시

from qiskit import QuantumCircuit
import numpy as np

def qft(n: int) -> QuantumCircuit:
    """n큐비트 QFT 회로 생성"""
    qc = QuantumCircuit(n)
    for j in range(n):
        qc.h(j)
        for k in range(j + 1, n):
            angle = 2 * np.pi / (2 ** (k - j + 1))
            qc.cp(angle, k, j)  # 조건부 위상 게이트
    # 비트 역순 정렬
    for i in range(n // 2):
        qc.swap(i, n - i - 1)
    return qc

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

---

정리

QFT는 중첩·위상 간섭을 활용해 $O({\log }^{2}N)$ 게이트로 $N$차원 Fourier 변환을 수행한다. 곱 형태 분해가 회로 효율성의 수학적 근거이며, 각 큐비트는 독립적인 위상 인코더 역할을 한다. 그러나 측정 시 진폭 정보가 확률로 붕괴되므로, QFT의 출력은 직접 관측하지 않고 QPE·쇼어 알고리즘 등의 서브루틴으로 사용할 때 진가를 발휘한다.