양자 푸리에 변환

이 Qiskit in Classrooms 모듈을 실습하려면 다음 패키지가 설치된 Python 환경이 필요합니다:

• qiskit v2.1.0 이상
• qiskit-ibm-runtime v0.40.1 이상
• qiskit-aer v0.17.0 이상
• qiskit.visualization
• numpy
• pylatexenc

위 패키지의 설치 및 설정 방법은 Qiskit 설치 가이드를 참고하세요. 실제 양자 컴퓨터에서 작업을 실행하려면 IBM Cloud 계정 설정 가이드의 절차에 따라 IBM Quantum® 계정을 만들어야 합니다.

이 모듈은 테스트 결과 QPU 시간을 13초 사용했습니다. 이는 참고용 추정치이며 실제 사용량은 다를 수 있습니다.

# Added by doQumentation — required packages for this notebook
!pip install -q numpy qiskit qiskit-aer qiskit-ibm-runtime

# Uncomment and modify this line as needed to install dependencies
#!pip install 'qiskit>=2.1.0' 'qiskit-ibm-runtime>=0.40.1' 'qiskit-aer>=0.17.0' 'numpy' 'pylatexenc'

소개

푸리에 변환은 수학, 물리학, 신호 처리, 데이터 압축 등 수많은 분야에서 폭넓게 활용되는 도구입니다. 양자 버전의 푸리에 변환인 양자 푸리에 변환은 가장 중요한 양자 알고리즘의 근간을 이룹니다.

오늘은 고전 푸리에 변환을 간략히 복습한 뒤, 양자 컴퓨터에서 양자 푸리에 변환을 구현하는 방법을 살펴보겠습니다. 그런 다음 양자 푸리에 변환이 위상 추정 알고리즘이라는 알고리즘에 어떻게 응용되는지 알아봅니다. 양자 위상 추정은 양자 컴퓨팅의 "왕관의 보석"으로 불리는 Shor의 유명한 인수분해 알고리즘의 서브루틴입니다. 이 모듈은 Shor의 알고리즘을 다루는 다른 모듈로 이어지지만, 독립적으로도 학습할 수 있도록 구성되어 있습니다. 양자 푸리에 변환 자체가 매우 흥미롭고 유용한 알고리즘이기 때문입니다!

고전 푸리에 변환

양자 푸리에 변환으로 넘어가기 전에, 먼저 고전 버전을 간략히 복습해 보겠습니다. 푸리에 변환은 하나의 이른바 "기저(basis)"에서 다른 기저로 변환하는 방법입니다. 두 기저는 동일한 문제를 서로 다른 관점에서 바라보는 것으로 생각할 수 있습니다. 둘 다 함수를 표현하는 유효한 방법이지만, 다루는 문제에 따라 어느 쪽이 더 유용할 수 있습니다. 푸리에 변환으로 연결되는 기저 쌍의 예로는 위치와 운동량, 시간과 주파수가 있습니다.

푸리에 변환이 음파 파형을 바탕으로 악기가 연주하는 음을 파악하는 데 어떻게 도움이 되는지 예시를 통해 살펴보겠습니다. 일반적으로 파형은 시간 기저로 표현됩니다. 즉, 파동의 진폭이 시간의 함수로 나타납니다.

이 파형에 푸리에 변환을 적용하면 시간 기저에서 주파수 기저로 이동할 수 있습니다:

주파수 기저에서는 약 260 Hz에서 명확한 피크를 쉽게 확인할 수 있습니다. 이는 가운데 C(미들 C)입니다!

푸리에 변환 없이도 가운데 C가 연주되고 있음을 파악할 수 있었겠지만, 여러 음이 동시에 연주된다면 어떨까요? 그러면 시간 기저에서 파형이 더 복잡해집니다:

하지만 주파수 스펙트럼은 세 개의 피크를 명확하게 보여줍니다:

이는 C, E, G 음을 연주하는 다장조(C-major) 화음이었습니다.

이러한 푸리에 분석은 복잡한 신호의 주파수 성분을 추출하는 데 도움이 됩니다.

이산 푸리에 변환

푸리에 변환은 다양한 신호 처리 응용에 유용합니다. 그러나 위의 음악 예시를 포함한 대부분의 실제 응용에서는 연속 함수가 아닌 이산적인 $N$개의 데이터 포인트를 변환해야 합니다. 이 경우 이산 푸리에 변환을 사용합니다. 이산 푸리에 변환(DFT)은 벡터 $(x_0, ..., x_{N-1})$에 작용하여 다음 공식에 따라 벡터 $(y_0, ..., y_{N-1})$로 변환합니다:

$y_k = \frac{1}{\sqrt{N}}\sum_{j=0}^{N-1}x_j\omega_N^{jk}$

여기서 $\omega_N^{jk} = e^{2\pi i \frac{jk}{N}}$으로 정의합니다. (지수에 음수 부호가 붙는 다른 관례도 있으므로, 실제로 DFT를 접할 때 주의하세요.) $e^{2\pi i \frac{jk}{N}}$는 주기 $\frac{N}{k}$를 갖는 주기 함수임을 기억하세요. 따라서 이 함수를 곱하는 푸리에 변환은 본질적으로 (이산) 함수 $\{x_{j}\}$를 각각 주기 $\frac{N}{k}$를 갖는 구성 주기 함수들의 선형 결합으로 분해하는 방법입니다.

양자 푸리에 변환

지금까지 푸리에 변환이 함수를 새로운 "기저 함수" 집합의 선형 결합으로 표현하는 데 사용됨을 살펴봤습니다. 기저 변환은 Qubit 상태에서도 자주 수행됩니다. 예를 들어, 단일 Qubit $|\psi\rangle$의 상태는 계산 기저(computational basis) $|\psi\rangle = c_0 |0\rangle + c_1 |1\rangle$ (기저 상태 $|0\rangle$과 $|1\rangle$ 사용), 또는 $X$ 기저 $|\psi\rangle = c_+ |+\rangle + c_- |-\rangle$ (기저 상태 $|+\rangle = \frac{1}{\sqrt{2}} (|0\rangle + |1\rangle)$과 $|-\rangle = \frac{1}{\sqrt{2}} (|0\rangle - |1\rangle)$ 사용)로 표현할 수 있습니다. 둘 다 유효하지만, 풀려는 문제에 따라 어느 쪽이 더 자연스러울 수 있습니다.

Qubit 상태는 푸리에 기저로도 표현할 수 있습니다. 이 경우 상태가 일반적인 계산 기저 상태 $|x\rangle$ 대신 푸리에 기저 상태 $|\phi_y\rangle$의 선형 결합으로 표현됩니다. 이를 위해 양자 푸리에 변환(QFT)을 적용합니다:

$| \phi_y \rangle = \frac{1}{\sqrt{N}}\sum_{x=0}^{N-1}\omega_N^{y x} \vert x \rangle$

위와 같이 $\omega_N^{yx} = e^{\frac{2\pi i y x}{N}}$이고, $N$은 양자 시스템의 기저 상태 수입니다. Qubit을 다루므로 $m$개의 Qubit은 $2^m$개의 기저 상태를 가져 $N=2^m$임을 유의하세요. 여기서 기저 상태는 $x$가 $0$에서 $N-1$까지 변하는 단일 숫자 $|x\rangle$로 표기되지만, 보통은 $|00...00\rangle$, $|00...01\rangle$, $|00...11\rangle$, ..., $|11...11\rangle$과 같이 각 이진수가 오른쪽에서 왼쪽으로 Qubit 0부터 $m-1$까지의 상태를 나타내는 형태로 표현됩니다. 이 이진 상태를 단일 숫자로 변환하는 방법은 간단합니다: 이진수로 취급하면 됩니다! 따라서 $|00...00\rangle = |0\rangle$, $|00...01\rangle = |1\rangle$, $|00...10\rangle = |2\rangle$, $|00...11\rangle = |3\rangle$, ..., $|11...11\rangle = |2^m -1\rangle = |N-1\rangle$입니다.

푸리에 기저 상태에 대한 직관 쌓기

지금까지 계산 기저 상태가 무엇인지, 그리고 어떻게 순서가 매겨지는지 살펴봤습니다. 계산 기저 상태는 각 Qubit이 $0$ 또는 $1$인 상태들의 집합이며, 모든 Qubit이 $0$인 상태 $|00...00\rangle$부터 모두 $1$인 상태 $|11...11\rangle$까지 순서가 정해집니다.

그렇다면 푸리에 기저 상태는 어떻게 이해할 수 있을까요? 모든 푸리에 기저 상태는 계산 기저 상태들의 동등한 중첩이지만, 각 상태는 성분들의 위상이 주기적으로 변하는 방식에서 서로 다릅니다. 이를 더 구체적으로 이해하기 위해 두 Qubit 시스템의 네 가지 푸리에 기저 상태를 살펴보겠습니다. 가장 낮은 푸리에 상태는 위상이 전혀 변하지 않는 상태입니다:

$|\phi_0\rangle = \frac{1}{2} (|00\rangle + |01\rangle + |10\rangle + |11\rangle)$

각 항의 복소 진폭을 그래프로 시각화해 보겠습니다. 빨간 선은 계산 기저 상태를 따라가면서 이 진폭의 위상이 복소 평면 위에서 어떻게 변하는지 보여줍니다. $|\phi_0\rangle$에서는 위상이 일정하게 유지됩니다:

다음 푸리에 기저 상태는 성분들의 위상이 $0$에서 $2\pi$까지 정확히 한 번 회전하는 상태입니다:

$|\phi_1\rangle = \frac{1}{2} (|00\rangle + e^{i\pi/2}|01\rangle + e^{i\pi}|10\rangle + e^{3i\pi/2}|11\rangle) = \frac{1}{2}(|00\rangle + i|01\rangle - |10\rangle - i|11\rangle)$

계산 기저 상태 대비 복소 진폭 그래프에서 이 위상 회전을 확인할 수 있습니다:

이 예시에서는 기저 상태가 네 개($N=4$)이므로, 각 상태는 표준 순서로 정렬했을 때 이전 상태보다 $2\pi/4$ 라디안만큼 위상이 높습니다. 다음 기저 상태는 $0$에서 $2\pi$까지 두 번 회전합니다:

$|\phi_2\rangle = \frac{1}{2} (|00\rangle + e^{i\pi}|01\rangle + e^{2i\pi}|10\rangle + e^{3i\pi}|11\rangle) = \frac{1}{2} (|00\rangle - |01\rangle + |10\rangle - |11\rangle)$

마지막으로, 가장 높은 푸리에 성분은 위상 변화가 가장 빠른 상태입니다. 두 Qubit 예시에서는 위상이 $0$에서 $2\pi$까지 세 번 회전하는 상태입니다:

$|\phi_3\rangle = \frac{1}{2} (|00\rangle + e^{3i\pi/2}|01\rangle + e^{6i\pi/2}|10\rangle + e^{9i\pi/2}|11\rangle) = \frac{1}{2} (|00\rangle - i|01\rangle - |10\rangle + i|11\rangle)$

일반적으로 $m$-Qubit 상태에는 $2^m$개의 푸리에 기저 상태가 있으며, 위상 변화의 주파수는 $|\phi_0\rangle$의 상수(일정)부터 $|\phi_{2^m-1}\rangle$의 빠른 변화까지 이어지고, 상태들의 중첩에서 $2\pi$ 주위를 $2^m-1$번 감습니다. 따라서 양자 상태에 QFT를 적용하면, 음악 파형에서 수행한 분석과 본질적으로 동일한 작업을 하는 것입니다. 즉, 관심 있는 양자 상태를 구성하는 푸리에 주파수 성분을 파악하는 것입니다.

QFT 예제 실습

이제 양자 푸리에 변환에 대한 직관을 계속 키워 나가기 위해, 계산 기저(computational basis)에서 상태를 만들고 QFT를 적용하면 어떤 결과가 나오는지 살펴보겠습니다. 지금은 QFT를 Qiskit Circuit 라이브러리의 QFTGate를 사용해 적용하는 블랙박스로만 다룰 것입니다. 나중에 내부 구현을 들여다볼 기회도 있습니다.

먼저 필요한 패키지를 불러오고 Circuit을 실행할 디바이스를 선택합니다:

import numpy as np
from qiskit import QuantumCircuit
from qiskit.visualization import plot_histogram
from qiskit.circuit.library import QFTGate

# Load the Qiskit Runtime service
from qiskit_ibm_runtime import QiskitRuntimeService

# Load the Runtime primitive and session
from qiskit_ibm_runtime import SamplerV2 as Sampler

service = QiskitRuntimeService()

# Use the least busy backend
# backend = service.least_busy(operational=True, simulator=False, min_num_qubits = 127)
backend = service.backend("ibm_pinguino2")

print(backend.name)

ibm_pinguino2

계정에 사용 가능한 시간이 없거나 어떤 이유로든 시뮬레이터를 사용하고 싶다면, 아래 셀을 실행해 위에서 선택한 양자 디바이스를 모방하는 시뮬레이터를 설정할 수 있습니다:

# Load the backend sampler
from qiskit.primitives import BackendSamplerV2

# Load the Aer simulator and generate a noise model based on the currently-selected backend.
from qiskit_aer import AerSimulator
from qiskit_aer.noise import NoiseModel

noise_model = NoiseModel.from_backend(backend)

# Define a simulator using Aer, and use it in Sampler.
backend_sim = AerSimulator(noise_model=noise_model)
sampler_sim = BackendSamplerV2(backend=backend_sim)

# Alternatively, load a fake backend with generic properties and define a simulator.
from qiskit.providers.fake_provider import GenericBackendV2

backend_gen = GenericBackendV2(num_qubits=18)
sampler_gen = BackendSamplerV2(backend=backend_gen)

단일 계산 기저 상태

먼저 단일 계산 기저 상태를 변환해 보겠습니다. 임의의 계산 기저 상태를 만들어 시작합니다:

# Step 1: Map

qubits = 4
N = 2**qubits

qc = QuantumCircuit(qubits)

# flip state of random qubits to put in a random single computational basis state
for i in range(1, qubits):
    if np.random.randint(0, 2):
        qc.x(i)

# make a copy of the above circuit. (to be used when we apply the QFT in next part)
qc_qft = qc.copy()

qc.measure_all()
qc.draw("mpl")

# Step 2: Transpile
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)

qc_isa = pm.run(qc)

# Step 3: Run the job on a real quantum computer OR try fake backend

sampler = Sampler(mode=backend)
pubs = [qc_isa]

# Run the job on real quantum device

job = sampler.run(pubs, shots=1000)
res = job.result()
counts = res[0].data.meas.get_counts()

# OR Run the job on the Aer simulator with noise model from real backend

# job = sampler_sim.run([qc_isa])
# res = job.result()
# counts = res[0].data.meas.get_counts()

# Step 4: Post-Process
plot_histogram(counts)

이제 QFTGate로 이 상태에 푸리에 변환을 적용해 봅시다:

# Step 1: Map

qc_qft.compose(QFTGate(qubits), inplace=True)
qc_qft.measure_all()
qc_qft.draw("mpl")

# Step 2: Transpile
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)

qc_isa = pm.run(qc_qft)

# Step 3: Run the job on a real quantum computer - try fake backend

sampler = Sampler(mode=backend)
pubs = [qc_isa]

# Run the job on real quantum device

job = sampler.run(pubs, shots=1000)
res = job.result()
counts = res[0].data.meas.get_counts()

# OR Run the job on the Aer simulator with noise model from real backend

# job = sampler_sim.run([qc_isa])
# res = job.result()
# counts = res[0].data.meas.get_counts()

# Step 4: Post-Process
plot_histogram(counts)

보면 알 수 있듯이, 실험적·통계적 노이즈를 감안하더라도 각 상태의 확률이 거의 균등하게 측정됩니다. 즉, 단일 계산 기저 상태에 QFT를 적용하면 모든 상태의 균등 중첩이 결과로 나옵니다. 푸리에 변환에 익숙하다면 이 결과가 그리 놀랍지 않을 것입니다. 함수와 그 푸리에 변환 사이의 직관을 쌓는 데 도움이 되는 기본 원리 중 하나는, 함수의 폭이 푸리에 변환의 폭에 반비례한다는 것입니다. 예를 들어, 매우 짧은 펄스처럼 시간 영역에서 매우 국소화된 신호는 그 펄스를 구성하기 위해 넓은 주파수 범위를 필요로 합니다. 즉, 해당 신호는 푸리에 공간에서 매우 넓게 퍼지게 됩니다.

이 사실은 사실 양자 불확정성과도 관련이 있습니다! 하이젠베르크의 불확정성 원리는 일반적으로 $\Delta x \Delta p \ge \hbar / 2$로 표현됩니다. 따라서 $x$의 불확정성($\Delta x$)이 작으면 운동량의 불확정성($\Delta p$)이 커야 하고, 그 반대도 마찬가지입니다. 위치 기저 $x$에서 운동량 기저 $p$로의 변환은 바로 푸리에 변환을 통해 이루어집니다.

참고: 우리는 각 기저 상태의 확률(population)을 측정하고 있으므로, 중첩의 여러 성분 사이의 상대적 위상 정보는 잃게 된다는 점을 기억하세요. 따라서 어떤 단일 계산 기저 상태의 QFT도 모든 기저 상태에 걸쳐 동일하게 균등한 확률 분포를 보이지만, 위상은 반드시 같지 않을 수 있습니다.

두 개의 계산 기저 상태

이번에는 계산 기저 상태의 중첩을 준비하면 어떻게 되는지 살펴보겠습니다. 이 경우 푸리에 변환이 어떻게 보일 것 같으신가요?

다음 중첩 상태를 선택해 봅시다:

$|\psi\rangle = \frac{1}{\sqrt{2}} (|0\rangle + |N/2\rangle) = \frac{1}{\sqrt{2}} (|000...0\rangle + |100...0\rangle)$

# Step 1: Map
qubits = 4
N = 2**qubits

qc = QuantumCircuit(qubits)

# To make this state, we just need to apply a Hadamard to the last qubit

qc.h(qubits - 1)

qc_qft = qc.copy()

qc.measure_all()

qc.draw("mpl")

# First, let's go through steps 2-4 for the first circuit, qc

# Step 2: Transpile
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)

qc_isa = pm.run(qc)

# Step 3: Run the job on a real quantum computer - try fake backend

sampler = Sampler(mode=backend)
pubs = [qc_isa]

# Run the job on real quantum device

job = sampler.run(pubs, shots=1000)
res = job.result()
counts = res[0].data.meas.get_counts()

# OR run the job on the Aer simulator with noise model from real backend

# job = sampler_sim.run([qc_isa])
# res = job.result()
# counts = res[0].data.meas.get_counts()

# Step 4: Post-process
plot_histogram(counts)

이제 QFTGate로 이 상태에 푸리에 변환을 적용해 봅시다:

# Step 1: Map

qc_qft.compose(QFTGate(qubits), inplace=True)
qc_qft.measure_all()
qc_qft.draw("mpl")

# Step 2: Transpile
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)

qc_isa = pm.run(qc_qft)

# Step 3: Run the job on a real quantum computer OR try fake backend

sampler = Sampler(mode=backend)
pubs = [qc_isa]

# Run the job on real quantum device

job = sampler.run(pubs, shots=1000)
res = job.result()
counts = res[0].data.meas.get_counts()

# OR run the job on the Aer simulator with noise model from real backend

# job = sampler_sim.run([qc_isa])
# res = job.result()
# counts = res[0].data.meas.get_counts()

# Step 4: Post-process
plot_histogram(counts)

이 결과는 다소 놀라울 수 있습니다. $|\psi\rangle = \frac{1}{\sqrt{2}} (|0\rangle + |N/2\rangle)$ 상태의 QFT가 모든 짝수 기저 상태의 중첩처럼 보입니다. 하지만 각 기저 상태 $|\phi_y\rangle$의 시각화, 즉 각 성분의 위상이 $2\pi$를 $y$번 감아 돌아가는 방식을 떠올리면, 이 결과가 나오는 이유가 명확해질 것입니다.

이해도 확인

아래 질문을 읽고 답을 생각해 본 뒤, 삼각형을 클릭해 해답을 확인하세요.

위의 힌트를 활용하여, $|\psi\rangle = \frac{1}{\sqrt{2}} (|0\rangle + |N/2\rangle)$의 QFT 결과가 왜 예상대로인지 설명하세요.

정답:

원래 상태는 중첩의 두 부분 사이에 상대 위상이 0(또는 $2\pi$의 정수배)입니다. 따라서 이 상태는 그 방식으로 위상이 맞아떨어지는 푸리에 성분을 가지고 있다는 것을 알 수 있습니다: |0000> 항과 |1000> 항 사이에 위상 변화가 0인 것들입니다. 각 푸리에 기저 상태 $|\phi_y\rangle$는 위상이 $2\pi y/N$의 비율로 누적되는 항들로 구성됩니다. 즉, 표준 순서로 정렬했을 때, 중첩의 각 항은 이전 항보다 $2\pi y/N$만큼 위상이 큽니다. 따라서 중간 지점인 $N/2$에서 위상 $2\pi y/N \times N/2$가 $2\pi$의 정수배가 되어야 합니다. 이는 $y$가 짝수일 때 성립합니다.

QFT에서 모든 홀수 이진수에 피크가 나타나는 계산 기저 상태의 중첩은 무엇일까요?

정답:

$\psi = |0\rangle - |N/2\rangle$ 상태의 QFT를 취하면, 모든 홀수 이진수 기저 상태에서 피크를 볼 수 있습니다.

QFT 알고리즘 분석

이제 계산 기저에서의 큐비트 상태와 푸리에 기저 간의 관계에 대한 직관을 더 쌓았으니, QFT 알고리즘 자체를 자세히 살펴보겠습니다. 다시 말해, 이 변환을 실제로 구현하기 위해 양자 컴퓨터에서 어떤 Gate들을 적용하는지 알아보겠습니다.

단일 큐비트처럼 작은 경우부터 시작해 보겠습니다. 즉, 기저 상태가 두 개입니다. QFT$_2$는 계산 기저 상태 $|0\rangle$과 $|1\rangle$을 각각 푸리에 기저 상태 $\phi_0$과 $\phi_1$로 변환합니다:

$|\phi_0\rangle = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$

$|\phi_1\rangle = \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)$

이해도 확인

아래 문제를 읽고 답을 생각해 본 다음, 삼각형을 클릭하여 해답을 확인하세요.

이전 섹션의 QFT 방정식을 사용하여 위의 두 푸리에 기저 상태를 검증해 보세요.

답:

일반적인 QFT 공식은 다음과 같습니다:

$| \phi_y \rangle = \frac{1}{\sqrt{N}}\sum_{x=0}^{N-1}\omega_N^{y x} \vert x \rangle$

단일 큐비트($n=1$)의 경우, $N=2^n=2$이고 $\omega_N^{xy} = e^{2\pi i \frac {y x}{2}}$입니다. 따라서,

$| \phi_0 \rangle = \frac{1}{\sqrt{2}}(e^{2\pi i \frac {0 \times 0}{2}}|0\rangle + e^{2\pi i \frac {0 \times 1}{2}}|1\rangle) = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$

$| \phi_1 \rangle = \frac{1}{\sqrt{2}}(e^{2\pi i \frac {1 \times 0}{2}}|0\rangle + e^{2\pi i \frac {1 \times 1}{2}}|1\rangle) = \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)$

위의 두 방정식을 살펴보면, 이 변환을 구현하는 데 사용할 수 있는 양자 Gate를 이미 알고 있을 수도 있습니다. 즉, 계산 기저 상태 $|0\rangle$과 $|1\rangle$을 각각 푸리에 기저 상태 $|\phi_0\rangle$과 $|\phi_1\rangle$로 변환하는 Gate가 존재합니다. 바로 Hadamard Gate입니다! QFT$_N$ 연산의 행렬 표현을 도입하면 이것이 더욱 명확해집니다:

$\text{QFT}_N = \frac{1}{\sqrt{N}} \sum_{x=0}^{N-1} \sum_{y=0}^{N-1} \omega_N^{xy} \vert x \rangle \langle y \vert$

이 표기법이 익숙하지 않더라도 괜찮습니다! 이것은 $N \times N$ 행렬을 나타내는 방법으로, $x$와 $y$는 $0$부터 $N-1$까지 행렬의 열과 행을 인덱싱하며, $\omega_N^{xy}$는 해당 항목의 값입니다. 예를 들어, 0번째 열과 2번째 행의 항목은 $\omega_N^{0,2} = e^{2 \pi i \frac{0 \times 2}{N}} = 1$이 됩니다.

이 표현에서 각 계산 기저 상태는 기저 벡터 중 하나와 연관됩니다:

$$\begin{pmatrix} 1 \\ 0 \\ \vdots \\ 0 \end{pmatrix}, |1\rangle = \begin{pmatrix} 0 \\ 1 \\ \vdots \\ 0 \end{pmatrix}, |N-1\rangle = \begin{pmatrix} 0 \\ 0 \\ \vdots \\ 1 \end{pmatrix}.$$

이 표현에 대해 더 깊이 알고 싶다면, 양자 정보의 기초 강좌에서 John Watrous의 다중 시스템 강의를 참고하세요.

QFT$_4$의 행렬을 구성해 보겠습니다. 위의 공식을 사용하면 다음을 얻습니다:

$\text{QFT}_4 = \frac{1}{2} \begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i \\ \end{pmatrix}$

이 행렬을 양자 컴퓨터에서 구현하려면, 위 행렬과 일치하는 유니타리 변환을 만들기 위해 어느 큐비트에 어떤 Gate의 조합을 적용할지 파악해야 합니다. 필요한 Gate 중 하나인 Hadamard는 이미 알고 있습니다. 또 필요한 Gate는 제어 위상 Gate인데, 이 Gate는 제어 큐비트가 $|1\rangle$ 상태에 있을 때 대상 큐비트 상태에 상대 위상 $\alpha$를 적용합니다. 행렬 형태로는 다음과 같습니다:

$\text{CP}_\alpha = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & e^{i\alpha} \\ \end{pmatrix}$

$|11\rangle$ 상태만 변경되기 때문에, 실제로 어느 큐비트가 "제어"이고 어느 것이 "대상"인지는 중요하지 않습니다. 어느 쪽이든 결과는 동일합니다.

마지막으로, SWAP Gate도 필요합니다. SWAP Gate는 두 큐비트의 상태를 교환합니다. 행렬 형태는 다음과 같습니다:

$\text{SWAP}_\alpha = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ \end{pmatrix}$

$m$개의 큐비트에 대한 QFT$_{2^m}$ Circuit을 구성하는 절차는 반복적입니다. 먼저 큐비트 $1$부터 $m-1$까지에 QFT$_{2^{m-1}}$을 적용한 다음, 큐비트 $0$과 나머지 $m-1$개의 큐비트 사이에 Gate를 추가합니다. 그런데 QFT$_{2^{m-1}}$을 적용하려면, 먼저 큐비트 2부터 $m-1$까지에 QFT$_{2^{m-2}}$를 적용한 다음, 큐비트 1과 나머지 큐비트 $2$부터 $m-1$ 사이에 Gate를 추가해야 합니다. 이것은 마치 러시아 마트료시카 인형과 같습니다. 각 인형은 QFT Circuit의 차원을 두 배로 늘리고, 가장 작은 인형이 중심에 있는데, 그것이 바로 QFT$_2$, 즉 Hadamard Gate입니다.

한 인형을 다음으로 큰 인형 안에 넣어서 QFT의 차원을 두 배로 늘리려면, 항상 동일한 절차를 따릅니다:

1. 먼저, 가장 아래쪽 $m-1$개의 큐비트에 QFT$_{2^{m-1}}$을 적용합니다. 이것이 곧 다음으로 큰 인형 안에 들어갈 "더 작은 인형"입니다.
2. 그 위의 큐비트를 제어로 사용하고, 아래쪽 $m-1$개의 큐비트 각각에 제어 위상 Gate를 적용합니다. 위상은 나머지 $m-1$개의 큐비트 각각의 표준 기저 상태에 맞게 설정합니다.
3. 위상 Gate에서 제어로 사용된 동일한 최상위 큐비트에 Hadamard를 적용합니다.
4. SWAP Gate를 사용하여 큐비트 순서를 재배열하여, 최하위(최상단) 비트가 최상위(최하단) 비트가 되고 나머지는 한 자리씩 위로 이동하도록 합니다.

우리는 이미 Qiskit Circuit 라이브러리의 QFTGate 함수를 사용하고 있었지만, 이제 위 절차를 확인하기 위해 이러한 QFT Gate 내부를 살펴보겠습니다. decompose()를 사용하면 됩니다.

qc = QuantumCircuit(1)
qc.compose(QFTGate(1), inplace=True)
qc.decompose().draw("mpl")

qc = QuantumCircuit(2)
qc.compose(QFTGate(2), inplace=True)
qc.decompose().draw("mpl")

qc = QuantumCircuit(3)
qc.compose(QFTGate(3), inplace=True)
qc.decompose().draw("mpl")

qc = QuantumCircuit(4)
qc.compose(QFTGate(4), inplace=True)
qc.decompose().draw("mpl")

이렇게 처음 네 가지 QFT를 보면, 각각이 어떻게 다음으로 큰 것 안에 중첩되어 있는지 보이기 시작할 것입니다. 그런데 위상 Gate 중 일부가 앞서 설명한 절차와 정확히 일치하지 않고, SWAP이 각 서브루틴 이후가 아니라 전체 QFT의 맨 끝에만 나타나는 것을 눈치챘을 것입니다. 이는 불필요한 Gate를 줄여 Circuit이 더 오래 걸리고 오류가 더 발생하기 쉬워지는 것을 방지하기 위함입니다. 중첩된 각 인형 이후에 SWAP을 구현하는 대신, Circuit은 각 큐비트 상태가 있어야 할 위치를 추적하고 이에 맞게 위상 Gate를 적용할 큐비트를 조정합니다. 그런 다음 마지막에 SWAP 세트를 적용하여 모든 것을 제자리에 놓습니다.

QFT 적용: 위상 추정

QFT가 양자 컴퓨팅에서 유용한 문제를 해결하는 데 어떻게 활용되는지 살펴보겠습니다. 역 양자 푸리에 변환(inverse QFT)을 계산하는 것은 양자 위상 추정(Quantum Phase Estimation, QPE)이라는 알고리즘에서 필수적인 단계입니다. QPE 자체는 Shor의 인수분해 알고리즘을 비롯한 많은 다른 알고리즘의 서브루틴으로 활용됩니다.

QPE의 목표는 유니타리 연산자의 고유값을 추정하는 것입니다. 유니타리 연산자는 양자 컴퓨팅 전반에 걸쳐 광범위하게 등장하며, 해당 고유벡터에 대한 고유값을 찾는 것이 더 큰 알고리즘의 필수 단계가 되는 경우가 많습니다. 문제에 따라 고유값은 시뮬레이션 유형 문제에서 해밀토니안의 에너지를 나타낼 수도 있고, Shor의 알고리즘에서 수의 소인수를 찾는 데 도움이 될 수도 있으며, 그 밖의 핵심 정보를 담고 있을 수도 있습니다. QPE는 양자 컴퓨팅에서 가장 중요하고 널리 사용되는 서브루틴 중 하나입니다.

그렇다면 이것이 양자 푸리에 변환과 어떤 관련이 있을까요? 앞서 언급했듯이, 유니타리 연산자의 고유값 $\lambda$는 반드시 크기 $|\lambda| = 1$을 가집니다. 따라서 각 고유값을 크기가 1인 복소수로 나타낼 수 있습니다:

$\lambda = e^{2\pi i \theta}$

여기서 $\theta$는 0과 1 사이의 실수입니다. 유니타리 행렬에 대한 더 자세한 내용은 기초 양자 정보 강좌에서 John Watrous의 해당 주제에 관한 강의를 참고하세요.

$\lambda$는 $\theta$에 대해 주기적임을 주목하세요. 이 점은 이미 QFT가 관련될 수 있다는 것을 시사합니다. 앞서 주기 함수 분석에서 QFT가 얼마나 유용한지를 확인했기 때문입니다. 아래에서는 알고리즘을 단계별로 살펴보며 QFT가 정확히 어디에서 역할을 하는지 알아보겠습니다.

QPE의 작동 원리

우선 가장 간단한 QPE 알고리즘부터 시작하겠습니다. 이 알고리즘은 위상을 단 한 개의 이진 자릿수 정밀도로 대략적으로 추정합니다. 다시 말해, 이 알고리즘은 $\theta = 0$과 $\theta = 1/2$를 구별할 수는 있지만 그 이상의 정밀도는 갖지 못합니다. Circuit 도면은 다음과 같습니다:

Qubit들은 상태 $|\pi_0\rangle = |\psi\rangle|0\rangle$으로 준비됩니다. 여기서 Qubit $0$은 $|0\rangle$ 상태이고 나머지 Qubit들은 $U$의 고유상태인 $|\psi\rangle$ 상태입니다. 첫 번째 Hadamard 이후 Qubit 상태는 다음과 같이 됩니다:

$|\pi_1\rangle = \frac{1}{\sqrt{2}}|\psi\rangle (|0\rangle + |1\rangle)$

다음 Gate는 "controlled-$U$" Gate입니다. 이 Gate는 Qubit 0이 $|1\rangle$ 상태일 때 $|\psi\rangle$ 상태에 있는 하위 Qubit들에 유니타리 연산 $U$를 적용하고, Qubit 0이 $|0\rangle$ 상태일 때는 $|\psi\rangle$에 아무것도 하지 않습니다. 이를 통해 Qubit들은 다음 상태로 변환됩니다:

$|\pi_2\rangle = \frac{1}{\sqrt{2}}( |\psi\rangle|0\rangle + e^{2\pi i \theta}|\psi\rangle|1\rangle)$ $= \frac{1}{\sqrt{2}}|\psi\rangle (|0\rangle + e^{2\pi i \theta}|1\rangle)$

여기서 흥미로운 일이 발생합니다. controlled-$U$ Gate는 Qubit $0$을 제어 Qubit으로만 사용하므로, 이 Gate가 Qubit 0의 상태를 전혀 변경하지 않을 것이라고 생각할 수 있습니다. 그런데 실제로는 변경이 일어납니다! 연산이 하위 Qubit에 적용되었음에도 불구하고, Gate의 전체적인 효과는 Qubit $0$의 위상을 변경하는 것입니다. 이를 "위상 킥백(phase kickback) 메커니즘"이라고 하며, Deutsch-Josza 알고리즘과 Grover 알고리즘을 비롯한 많은 양자 알고리즘에서 사용됩니다. 위상 킥백 메커니즘에 대해 더 알고 싶다면 기초 양자 알고리즘 강좌에서 John Watrous의 양자 쿼리 알고리즘 강의를 참고하세요.

위상 킥백 이후, Qubit $0$에 Hadamard를 한 번 더 적용하면 다음 상태가 됩니다:

$|\pi_3\rangle = |\psi\rangle ( \frac{1+e^{2\pi i \theta}}{2} |0\rangle + \frac{1 - e^{2\pi i \theta}}{2}|1\rangle) = |\psi\rangle ( \cos(\pi\theta) |0\rangle - i \sin(\pi\theta)|1\rangle)$

따라서 마지막에 Qubit $0$을 측정하면, $\theta = 0$일 때 $|0\rangle$을 100% 확실하게 측정하고, $\theta = \frac{1}{2}$일 때 $|1\rangle$을 100% 확실하게 측정합니다(양자 컴퓨터가 완벽하여 노이즈가 없는 경우). $\theta$가 이 두 값 이외의 값이면 최종 측정은 확률적이며 그 정보만으로는 한계가 있습니다.

더 높은 정밀도의 QPE: Qubit 추가

이 간단한 개념을 임의의 정밀도를 가진 더 복잡한 알고리즘으로 확장할 수 있습니다. Qubit $0$ 하나만으로 위상을 측정하는 대신, Qubit $0$부터 $m-1$까지 총 $m$개의 Qubit을 사용하면 $m$비트 정밀도로 위상을 추정할 수 있습니다. 어떻게 작동하는지 살펴보겠습니다:

이 더 정밀한 QPE Circuit은 단일 비트 버전과 동일하게 시작합니다. 처음 $m$개의 Qubit에 Hadamard가 적용되고, 나머지 Qubit들은 $|\psi\rangle$ 상태로 준비되어 다음 상태를 만듭니다:

$|\pi_1\rangle = \frac{1}{2^{m/2}}|\psi\rangle(|0\rangle+|1\rangle)(|0\rangle+|1\rangle)...(|0\rangle+|1\rangle)$

이제 controlled-unitary들이 적용됩니다. Qubit $0$은 이전과 동일한 유니타리 $U$의 제어 Qubit입니다. 하지만 이제 Qubit $1$은 $U^2$의 제어 Qubit이 됩니다. $U^2$는 단순히 $U$를 두 번 적용한 것입니다. 따라서 $U^2$의 고유값은 $e^{2*2\pi i \theta}$입니다. 일반적으로 0부터 $m-1$까지의 각 Qubit $k$는 유니타리 $U^{2^k}$의 제어 Qubit이 됩니다. 이는 각 Qubit이 $e^{2^k*2\pi i \theta}$의 위상 킥백을 받는다는 것을 의미합니다. 그 결과 다음 상태가 됩니다:

$|\pi_2\rangle = |\psi\rangle \otimes \frac{1}{2^{m/2}} (|0\rangle+e^{2^{m-1}2\pi i \theta}|1\rangle)(|0\rangle+e^{2^{m-2}2\pi i \theta}|1\rangle)...(|0\rangle+e^{2\pi i \theta}|1\rangle)$

이를 계산 기저 상태들의 합으로 다시 쓸 수 있습니다:

$|\pi_2\rangle = |\psi\rangle \otimes \frac{1}{2^{m/2}} \sum_{k=0}^{2^{m}-1} e^{2\pi i k \theta} |k\rangle$

이 합이 익숙해 보이지 않나요? 바로 QFT입니다! 양자 푸리에 변환의 식을 떠올려 보세요:

$\text{QFT}_{2^m}| y \rangle = \frac{1}{\sqrt{2^m}}\sum_{x=0}^{2^m-1}\omega_{2^m}^{y x} \vert x \rangle$

따라서 위상이 $\theta = y/2^m$ (여기서 $y$는 $0$과 $2^m-1$ 사이의 정수)이면, 이 상태에 역 QFT를 적용한 결과는 다음과 같습니다:

$|\pi_3\rangle = |\psi\rangle \otimes |y\rangle$

그리고 $|y\rangle$로부터 $\theta$를 알아낼 수 있습니다.

만약 $\theta/2^m$이 정수 배수가 아니라면, 역 QFT는 $\theta$를 단지 근사할 뿐입니다. 얼마나 잘 근사하는지는 확률적이어서 항상 최선의 근사값을 얻지는 못하지만 꽤 근접한 결과를 얻을 수 있으며, 사용하는 Qubit 수 $m$이 많을수록 더 나은 근사값을 얻을 수 있습니다. $\theta$의 근사 정도를 정량화하는 방법에 대해서는 기초 양자 알고리즘 강좌에서 John Watrous의 위상 추정과 인수분해 강의를 참고하세요.

결론

이 모듈에서는 QFT가 무엇인지, 양자 컴퓨터에서 어떻게 구현되는지, 그리고 문제 해결에 얼마나 유용한지 전반적으로 살펴보았습니다. QFT가 양자 위상 추정에서 유니타리 행렬의 고유값을 파악하는 데 어떻게 활용될 수 있는지를 통해 그 유용성을 엿볼 수 있었습니다.

핵심 개념

• 양자 푸리에 변환(QFT)은 이산 푸리에 변환(DFT)의 양자 버전입니다.
• QFT는 기저 변환의 예시입니다.
• 양자 위상 추정(QPE) 절차는 controlled-unitary 연산의 위상 킥백 메커니즘과 역 QFT에 의존합니다.
• QFT와 QPE는 모두 수많은 양자 알고리즘에서 광범위하게 사용되는 서브루틴입니다.

문제

참/거짓

1. 참/거짓: 양자 푸리에 변환(QFT)은 고전 이산 푸리에 변환(DFT)의 양자 버전입니다.
2. 참/거짓: QFT는 Hadamard Gate와 CNOT Gate만으로 구현할 수 있습니다.
3. 참/거짓: QFT는 Shor의 알고리즘의 핵심 구성 요소입니다.
4. 참/거짓: 양자 위상 추정의 출력은 연산자의 고유벡터를 나타내는 양자 상태입니다.
5. 참/거짓: QPE는 역 양자 푸리에 변환(QFT$^\dag$)을 사용해야 합니다.
6. 참/거짓: QPE에서 위상 $\phi$가 $n$비트로 정확히 표현 가능한 경우, 알고리즘은 확률 1로 올바른 결과를 제공합니다.

단답형

1. $2^n$개의 데이터 포인트를 가진 시스템에 QFT를 수행하려면 몇 개의 Qubit이 필요합니까?
2. QFT를 계산 기저 상태가 아닌 상태에도 적용할 수 있습니까? 가능하다면 어떤 결과가 나타납니까?
3. QPE에서 사용하는 제어 Qubit의 수는 결과적인 위상 추정의 해상도에 어떤 영향을 미칩니까?

문제 풀이

1. 행렬 곱셈을 이용하여 QFT 알고리즘의 단계들이 실제로 $\text{QFT}_4$ 행렬을 만들어냄을 검증하세요:

$$\text{QFT}_4 = \frac{1}{2} \begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i \\ \end{pmatrix}$$

(손으로 계산하지 않아도 됩니다!)

도전 문제

1. 모든 홀수 계산 기저의 동일한 중첩인 네 Qubit 상태를 만드세요: $|\psi\rangle = |0001\rangle + |0011\rangle + |0101\rangle + |0111\rangle +|1001\rangle +|1011\rangle +|1101\rangle +|1111\rangle$. 그런 다음 해당 상태에 QFT를 수행하세요. 결과 상태는 무엇입니까? 푸리에 변환에 대한 지식을 활용하여 결과가 타당한 이유를 설명하세요.