양자 Fourier 변환 직관적 이해

양자 Fourier 변환(QFT)은 이산 Fourier 변환의 양자역학적 버전으로, 중첩과 위상 회전을 이용해 $O(\log^2 N)$개의 게이트만으로 변환을 수행한다. 쇼어 알고리즘과 양자 위상 추정의 핵심 서브루틴으로, 고전 FFT 대비 지수적 이점을 제공하는 원리를 회로 수준에서 살펴본다.

개념 소개

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

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

핵심 원리

수학적 정의

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

$QFT ∣ j ⟩ = \frac{1}{N} k = 0 \sum N - 1 e^{2 π ij k / N} ∣ k ⟩$

선형성에 의해 임의의 중첩 상태 $∣ ψ ⟩ = \sum_{j} x_{j} ∣ j ⟩$ 에 적용하면, 진폭 계수 ${x_{j}}$ 의 DFT 결과 ${X_{k}}$ 를 진폭으로 가지는 상태가 출력된다.

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

$n$ 비트 이진 표현 $j = j_{1} 2^{n - 1} + \dots + j_{n}$ 와 이진 소수 표기 $0. j_{l} \dots j_{m} = \sum_{s} j_{l + s - 1} / 2^{s}$ 를 도입하면:

$QFT ∣ j ⟩ = \frac{1}{2 ^{n /2}} l = 1 ⨂ n (∣0 ⟩ + e^{2 π i \cdot 0. j_{n - l + 1} \dots j_{n}} ∣1 ⟩)$

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

회로 구성

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

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

$R_{k} = (10 0 e^{2 π i / 2^{k}})$

3큐비트 QFT 회로 절차

$q_{1}$ 에 H 적용 → 균등 중첩 생성
$q_{2}$ 제어 $R_{2}$ , $q_{3}$ 제어 $R_{3}$ 적용 → $q_{1}$ 위상 미세 조정
$q_{2}$ 에 H 적용, $q_{3}$ 제어 $R_{2}$ 적용
$q_{3}$ 에 H 적용
SWAP으로 비트 역순 정렬

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

예시·응용

1큐비트 QFT = 하다마드

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

$QFT ∣1 ⟩ = \frac{1}{2} (∣0 ⟩ - ∣1 ⟩) = ∣ - ⟩$

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

양자 위상 추정(QPE)

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

쇼어 알고리즘

$N$ 의 소인수 분해에서 $f (x) = a^{x} mod N$ 의 주기를 찾는 단계가 핵심이다. QPE를 통해 이 주기를 $O (lo g^{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 (lo g^{2} N)$ 게이트로 $N$ 차원 Fourier 변환을 수행한다. 곱 형태 분해가 회로 효율성의 수학적 근거이며, 각 큐비트는 독립적인 위상 인코더 역할을 한다. 그러나 측정 시 진폭 정보가 확률로 붕괴되므로, QFT의 출력은 직접 관측하지 않고 QPE·쇼어 알고리즘 등의 서브루틴으로 사용할 때 진가를 발휘한다.

연습문제

Q1.1큐비트 QFT를 $|0\rangle$과 $|1\rangle$에 각각 적용하면 어떤 상태가 되는가? 이 결과가 잘 알려진 어떤 게이트와 동일한지 설명하라.

힌트 보기

$N=2$일 때 정의식 $\frac{1}{\sqrt{2}}\sum_{k=0}^{1} e^{2\pi i jk/2}|k\rangle$을 $j=0$, $j=1$에 대해 각각 전개해 보라.

해설 보기

$\text{QFT}|0\rangle = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle) = |{+}\rangle$, $\text{QFT}|1\rangle = \frac{1}{\sqrt{2}}(|0\rangle + e^{\pi i}|1\rangle) = \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle) = |{-}\rangle$. 두 결과 모두 하다마드 게이트의 출력과 동일하다. 즉, 1큐비트 QFT $\equiv$ H이다.

Q2.$n$큐비트 QFT의 역변환(IQFT)을 회로로 구현하는 방법을 서술하라.

해설 보기

QFT 회로의 모든 게이트를 **역순으로** 배치하고, 각 게이트를 그 역연산으로 교체하면 된다. 구체적으로 SWAP은 그대로(자기 역원), 조건부 위상 $R_k$는 위상 부호를 반전한 $R_k^\dagger$($e^{-2\pi i/2^k}$), H는 그대로(자기 역원)로 바꾼다. Qiskit에서는 `qft_circuit.inverse()`로 간단히 생성할 수 있다.

Q3.QFT가 고전 FFT보다 지수적으로 빠르다고 해서, 임의의 Fourier 변환 문제에 양자 컴퓨터를 쓰면 항상 이점을 얻을 수 있는가? 그렇지 않다면 그 이유를 설명하라.

해설 보기

그렇지 않다. QFT는 양자 상태의 진폭에 인코딩된 $N$개의 복소수를 변환하지만, 고전 데이터 $N$개를 양자 상태로 로딩하는 데 $O(N)$ 이상의 비용이 드는 경우가 많다(QRAM 문제). 또한 변환 결과를 측정으로 읽어내면 $O(\sqrt{N})$ 샘플링 한계에 부딪힌다. 따라서 QFT의 지수 이점은 위상 추정처럼 **위상 정보 자체를 활용**하는 문제에서만 실질적으로 발휘된다.

개념 소개

핵심 원리

수학적 정의

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

회로 구성

예시·응용

1큐비트 QFT = 하다마드

양자 위상 추정(QPE)

쇼어 알고리즘

Qiskit 구현 예시

정리

연습문제

관련 용어