양자 푸리에 변환

이 교실 내 키스킷 모듈을 사용하려면 학생에게 다음 패키지가 설치된 Python 환경이 있어야 합니다:

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

위의 패키지를 설정하고 설치하려면 키스킷 설치 가이드를 참조하세요. 실제 양자 컴퓨터에서 작업을 실행하려면 학생들은 IBM Cloud 계정 설정 가이드의 단계에 따라 IBM Quantum® 계정을 설정해야 합니다.

이 모듈은 테스트를 거쳐 13초의 QPU 시간을 사용했습니다. 이는 선의의 추정치이며 실제 사용량은 다를 수 있습니다.

# 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의 유명한 인수분해 알고리즘의 하위 루틴으로, 양자 컴퓨팅의 '왕관 보석'이라고도 불립니다. 이 모듈은 쇼의 알고리즘에 관한 다른 모듈을 향해 구축되지만, 독립적으로 사용할 수도 있습니다. 양자 푸리에 변환은 그 자체로 매력적이고 유용한 알고리즘입니다!

고전 푸리에 변환

양자 푸리에 변환에 대해 알아보기 전에 먼저 고전적인 버전을 떠올려 보겠습니다. 푸리에 변환은 소위 '기저'에서 다른 기저로 변환하는 방법입니다. 두 가지 기반은 동일한 문제를 바라보는 서로 다른 관점이라고 생각할 수 있습니다. 둘 다 함수를 표현하는 유효한 방법이지만 당면한 문제에 따라 하나 또는 다른 것이 더 빛을 발할 수 있습니다. 푸리에 변환으로 연결된 염기 쌍의 몇 가지 예로는 위치와 운동량, 시간과 주파수가 있습니다.

푸리에 변환이 오디오 파형을 기반으로 악기가 어떤 음을 연주하고 있는지 파악하는 데 어떻게 도움이 되는지 예를 들어 보겠습니다. 일반적으로 파형은 시간 단위로 표시되며, 즉 파동의 진폭이 시간의 함수로 표현됩니다.

이 파형을 푸리에 변환하여 시간 단위에서 주파수 단위로 변환할 수 있습니다:

주파수 기준으로 보면 약 260Hz에서 뚜렷한 피크를 쉽게 확인할 수 있습니다. 가운데 C입니다!

이제 푸리에 변환을 사용하지 않고도 중간 C가 연주되고 있음을 확인할 수 있었지만 여러 음이 한 번에 연주되는 경우에는 어떻게 해야 할까요? 그러면 파형을 시간 단위로 플롯하면 파형이 더 복잡해집니다:

그러나 주파수 스펙트럼은 세 가지 피크를 명확하게 식별합니다:

이것은 C, E, G 음을 연주하는 C장조 코드입니다.

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

이산 푸리에 변환

푸리에 변환은 다양한 신호 처리 애플리케이션에 유용합니다. 하지만 위에서 사용한 음악 예시를 비롯한 대부분의 실제 애플리케이션에서는 연속 함수가 아닌 $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}$ 를 갖는 구성 주기 함수의 선형 조합으로 분해하는 방법입니다.

양자 푸리에 변환

지금까지 푸리에 변환을 사용하여 함수를 소위 "기저 함수"라는 새로운 집합의 선형 조합으로 표현하는 방법을 살펴봤습니다 기준 변환은 큐비트 상태에서도 정기적으로 수행됩니다. 예를 들어, 단일 큐비트 $|\psi\rangle$ 의 상태는 기저 상태 $|0\rangle$ 및 $|1\rangle$ 와 함께 계산 기저 $|\psi\rangle = c_0 |0\rangle + c_1 |1\rangle$ 로 표현하거나 기저 상태 $|+\rangle = \frac{1}{\sqrt{2}} (|0\rangle + |1\rangle)$ 및 $|-\rangle = \frac{1}{\sqrt{2}} (|0\rangle - |1\rangle)$ 와 함께 $X$ 기저 $|\psi\rangle = c_+ |+\rangle + c_- |-\rangle$ 로 표현할 수 있습니다. 둘 다 똑같이 유효하지만, 해결하려는 문제의 유형에 따라 한 가지가 다른 것보다 더 자연스러울 수 있습니다.

큐비트 상태는 일반적인 계산 기저 상태( $|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$ 는 양자 시스템의 기저 상태 수입니다. 참고로, 현재 큐비트를 다루고 있으므로 $m$ 개의 큐비트는 $2^m$ 개의 기저 상태를 가지며, 따라서 $N=2^m$ 가 됩니다. 여기서 기저 상태는 단일 숫자로 표기됩니다 $|x\rangle$. 여기서 $x$ 는 $0$ 부터 $N-1$ 까지의 값을 가집니다. 그러나 일반적으로 기저 상태는 다음과 같이 표현되는 경우가 더 많습니다 $|00...00\rangle$, $|00...01\rangle$, $|00...11\rangle$,..., $|11...11\rangle$. 여기서 각 이진 자릿수는 오른쪽에서 왼쪽으로 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$ 까지.

푸리에 기저 상태에 대한 직관력 함양

계산 기준 상태가 무엇이며 어떻게 정렬되는지 살펴봤는데, 각 큐비트가 $0$ 또는 $1$ 에 있는 상태의 집합이며, 모든 큐비트가 $0$, $|00...00\rangle$ 에 있는 상태부터 모두 $1$, $|11...11\rangle$ 에 있는 상태까지 순서대로 정렬합니다.

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

$|\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)$

복잡한 진폭 대 계산 기준 상태의 플롯에서 이러한 구불구불함을 확인할 수 있습니다:

따라서 이 예에서는 4개의 기저 상태( $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)$

마지막으로, 가장 높은 푸리에 성분은 위상 변화가 가장 빠른 성분입니다. 큐비트가 두 개인 예제에서는 위상이 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$ -큐비트 상태에 대해, $2^m$ 개의 푸리에 기저 상태가 존재하며, 이들의 위상 변동 주파수는 $|\phi_0\rangle$ 에서 일정하게 유지되는 것부터 $|\phi_{2^m-1}\rangle$ 에서 급격히 변하는 것까지 다양합니다. 이는 상태의 중첩 위에 $2\pi$ 주위를 $2^m-1$ 회 감는 것을 완성합니다. 따라서 양자 상태에 대해 양자장론을 적용할 때, 우리는 본질적으로 서론에서 음악 파형에 대해 수행했던 것과 동일한 기본 분석을 수행하는 것입니다. 우리는 관심 있는 양자 상태를 생성하는 데 기여하는 푸리에 주파수 성분을 결정하고 있습니다.

몇 가지 예시 QFT를 시도해 보세요

계산 기저에서 상태를 정의한 다음, 여기에 양자 푸리에 변환(QFT)을 적용했을 때 어떤 일이 일어나는지 살펴봄으로써, 양자 푸리에 변환에 대한 직관을 계속해서 키워보도록 합시다. 우선은 QFT를 Qiskit 회로 라이브러리의 QFTGate 를 사용하여 적용하는 블랙박스로 간주하겠습니다. 나중에 이 기능의 구현 방식에 대해 자세히 살펴보겠습니다.

필요한 패키지를 로드하고 회로를 실행할 장치를 선택하는 것으로 시작합니다:

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

# Load IBM Quantum Compute 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)

Output:

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")

Output:

# 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)

Output:

이제 이 상태를 QFTGate 으로 푸리에 변환해 보겠습니다:

# Step 1: Map

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

Output:

# 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)

Output:

보시다시피, 각 주의 인구를 어느 정도 동일하게 측정하고, 실험적 및 통계적 노이즈를 감안하여 측정합니다. 따라서 단일 계산 기준 상태의 QFT를 취하면 결과는 모든 상태의 동일한 중첩이 됩니다. 푸리에 변환에 익숙하다면 이 사실이 놀랍지 않을 것입니다. 함수와 푸리에 변환을 직관적으로 연결하는 데 도움이 되는 기본 원리 중 하나는 함수의 폭이 푸리에 변환의 폭에 반비례한다는 것입니다. 따라서 예를 들어 매우 짧은 펄스와 같이 시간적으로 매우 국부적인 것의 경우 해당 펄스를 생성하려면 광범위한 주파수가 필요합니다. 이 신호는 푸리에 공간에서 매우 광범위합니다.

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

참고: 각 기준 상태의 인구를 측정하고 있으므로 중첩의 여러 부분 사이의 상대적 위상에 대한 정보가 손실된다는 점에 유의하세요. 따라서 단일 계산 기저 상태의 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")

Output:

# 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)

Output:

이제 이 상태를 QFTGate 으로 푸리에 변환해 보겠습니다:

# Step 1: Map

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

Output:

# 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)

Output:

이것은 조금 더 놀랍습니다. 상태 $|\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 * N/2$ 단계가 $2\pi$ 의 정수 배수가 되기를 원합니다. 이는 $y$ 가 짝수일 때 발생합니다.

모든 홀수 이진수에 피크가 나타나는 양자장론(QFT)에는 어떤 계산적 상태 중첩이 해당될까요?

• 답변

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

QFT 알고리즘을 분해하다

이제 계산 기저의 큐비트 상태와 푸리에 기저 사이의 관계에 대해 더 직관적으로 이해했으니, QFT 알고리즘 자체에 대해 자세히 알아보겠습니다. 다시 말해, 이러한 변화를 달성하기 위해 양자 컴퓨터에서 실제로 어떤 게이트를 구현해야 할까요?

하나의 큐비트로 작게 시작해 보겠습니다. 즉, 두 가지 기본 상태가 있다는 뜻입니다. 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)$

이 두 가지 방정식을 살펴보세요. 이 변환을 구현하는 데 사용할 수 있는 양자 게이트에 대해 이미 알고 계실 것입니다. 즉, 계산 기저 상태 $|0\rangle$ 와 $|1\rangle$ 를 각각의 푸리에 기저 상태 $|\phi_0\rangle$ 와 $|\phi_1\rangle$ 로 변환하는 게이트가 있는데, 이것이 바로 하다마드 게이트입니다! 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$ 이 됩니다.

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

이 표현에 대해 더 자세히 알아보려면 양자 정보 기초 강좌의 다중 시스템에 대한 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}$

이 행렬을 양자 컴퓨터에서 구현하려면 어떤 큐비트에 어떤 게이트 조합을 적용하면 위의 행렬과 일치하는 단일 변환을 얻을 수 있는지 알아내야 합니다. 우리는 이미 필요한 게이트 중 하나인 하다마드를 알고 있습니다. 필요한 또 다른 게이트는 제어 큐비트가 $|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$ 만 변경되므로 실제로 어떤 큐비트가 "제어"로 간주되고 어떤 큐비트가 "대상"인지는 중요하지 않습니다 어느 쪽이든 결과는 동일합니다.

마지막으로 스왑 게이트도 필요합니다. 스왑 게이트는 두 큐비트의 상태를 교환합니다. 그런 것 같습니다:

$\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}$ 회로를 구성하는 절차는 반복적인데, 먼저 QFT $_{2^{m-1}}$ 를 큐비트 $1$ ~ $m-1$ 에 적용한 다음 큐비트 $0$ 와 다른 $m-1$ 큐비트 사이에 몇 개의 게이트를 추가합니다. 하지만 QFT $_{2^{m-1}}$ 를 적용하려면 먼저 QFT $_{2^{m-2}}$ 를 큐비트 2에서 $m-1$ 까지 적용한 다음, 큐비트 1과 나머지 큐비트 $2$ 에서 $m-1$ 까지 사이에 게이트를 추가해야 합니다. 이는 러시아 중첩 인형과 같습니다. 각 인형은 QFT 회로의 크기에 2의 계수를 더하며, 가장 작은 인형이 가장 중심에 있는 QFT $_2$, 즉 하다마드 게이트가 됩니다.

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

1. 먼저, 가장 아래쪽 $m-1$ 큐비트에 QFT $_{2^{m-1}}$ 를 적용합니다. 이것은 곧 다음으로 큰 인형 안에 넣을 러시아 둥지 인형 세트의 "작은 인형"입니다.
2. 다음 큐비트를 제어로 사용하고, 제어된 위상 게이트를 아래쪽 $m-1$ 큐비트 각각에 적용하여 나머지 $m-1$ 큐비트 각각에 표준 기준 상태의 위상을 적용합니다.
3. 위상 게이트에서 제어로 사용된 것과 동일한 최상위 큐비트에서 하다마드를 수행합니다.
4. SWAP 게이트를 사용하여 큐비트의 순서를 순열하여 가장 중요도가 낮은(위쪽) 비트가 가장 중요한(아래쪽) 비트가 되고 다른 모든 비트가 1씩 위로 이동하도록 합니다.

이미 키스킷 회로 라이브러리의 QFTGate 함수를 사용해 보았지만, 이제 위의 절차를 확인하기 위해 이러한 QFT 게이트의 내부를 살펴보겠습니다. decompose() 으로 이 작업을 수행할 수 있습니다.

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

Output:

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

Output:

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

Output:

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

Output:

따라서 처음 4개의 QFT부터 각 QFT가 다음 큰 QFT 안에 어떻게 중첩되는지 알 수 있기를 바랍니다. 하지만 일부 위상 게이트가 위에서 설명한 절차에 정확히 규정되어 있지 않고, SWAP이 각 하위 루틴 뒤에 나타나지 않고 전체 QFT의 맨 마지막에만 나타나는 것을 눈치챘을 것입니다. 이렇게 하면 회로가 더 오래 걸리고 오류가 발생하기 쉬운 불필요한 게이트를 줄일 수 있습니다. 중첩된 각 인형마다 SWAP을 구현하는 대신 회로는 각 큐비트 상태가 어디에 있어야 하는지 추적하고 그에 따라 위상 게이트를 적용하는 큐비트를 조정합니다. 그런 다음 마지막에 마지막 스왑 세트를 통해 모든 것을 적절한 위치에 배치합니다.

양자장 이론 적용: 위상 추정

양자 컴퓨팅에서 유용한 문제를 해결하기 위해 QFT를 어떻게 사용할 수 있는지 알아봅시다. 역 양자 푸리에 변환을 계산하는 것은 양자 위상 추정(QPE)으로 알려진 알고리즘의 필수 단계로, 양자 알고리즘의 '왕관 보석'인 쇼의 인수분해 알고리즘을 비롯한 다른 많은 알고리즘의 하위 루틴입니다.

QPE의 목표는 단일 연산자의 고유값을 추정하는 것입니다. 단일 연산자는 양자 컴퓨팅에서 어디에나 존재하며, 종종 관련 고유 벡터의 고유값을 찾는 것은 더 큰 알고리즘에서 필수적인 단계입니다. 문제에 따라 고유값은 시뮬레이션 유형 문제에서 해밀턴의 에너지를 나타내거나 쇼의 알고리즘에서 숫자의 소인수를 찾는 데 도움이 될 수 있으며, 다른 필수 정보를 포함할 수도 있습니다. QPE는 양자 컴퓨팅에서 가장 중요하고 널리 사용되는 하위 루틴 중 하나입니다.

그렇다면 이것이 양자 푸리에 변환과 어떤 관련이 있을까요? 기억하시겠지만, 단항 연산자의 모든 고유값 $\lambda$ 은 $|\lambda| = 1$ 의 크기를 갖습니다. 따라서 각 고유값을 진폭 1의 복소수로 쓸 수 있습니다:

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

여기서 $\theta$ 은 0에서 1 사이의 실수입니다. 단위 행렬에 대한 자세한 내용을 알고 싶다면 존 와트러스의 '양자 정보의 기초' 강의를 참조하세요.

$\lambda$ 는 $\theta$ 에서 주기적입니다. 이미 주기 함수를 분석하는 데 QFT가 얼마나 유용한지 보았기 때문에 QFT가 관련될 수 있다는 것을 알 수 있습니다. 아래에서 알고리즘을 살펴보고 QFT가 정확히 어떻게 작동하는지 알아보겠습니다.

QPE의 작동 방식

먼저, 위상을 대략적으로 2진수 한 자리의 정밀도로 추정하는 가장 간단한 QPE 알고리즘부터 시작하겠습니다. 즉, 이 알고리즘은 $\theta = 0$ 과 $\theta = 1/2$ 을 구별할 수는 있지만 그보다 더 잘할 수는 없습니다. 다음은 회로도입니다:

큐비트는 $|\pi_0\rangle = |\psi\rangle|0\rangle$ 상태로 준비되며, 여기서 큐비트 $0$ 는 $|0\rangle$ 상태이고 나머지 큐비트는 $|\psi\rangle$ 상태로, $U$ 의 고유 상태입니다. 첫 번째 하다마드 이후 큐비트 상태는 다음과 같이 됩니다:

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

다음 게이트는 "controlled- $U$ " 게이트입니다. 이는 큐비트 0이 상태 $|1\rangle$ 인 경우 상태 $|\psi\rangle$ 인 하단 큐비트에 단일 연산 $U$ 을 적용하지만, 큐비트 0이 상태 $|0\rangle$ 인 경우 $|\psi\rangle$ 에는 아무 작업도 수행하지 않습니다. 이렇게 하면 큐비트가 해당 상태로 변환됩니다:

$|\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)$

제어- $U$ 게이트는 제어 큐비트 $0$ 만을 큐비트로 사용하므로 이 게이트가 큐비트 0의 상태를 전혀 변경하지 않을 것이라고 생각할 수 있습니다. 하지만 어쩐지 그렇습니다! 이 연산이 하위 큐비트에 적용되었지만 게이트의 전반적인 효과는 큐비트의 위상을 변경하는 것입니다 $0$. 이를 "위상 킥백 메커니즘"이라고 하며, 도이치-요자와 그로버 알고리즘을 비롯한 많은 양자 알고리즘에 사용됩니다. 위상 킥백 메커니즘에 대해 자세히 알아보려면 양자 알고리즘의 기초에서 양자 쿼리 알고리즘에 대한 John Watrous의 강의를 참조하세요.

위상 킥백 후, 해다마드를 하나 더 적용하면 $0$ 상태가 됩니다:

$|\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)$

따라서 마지막에 큐비트 $0$ 를 측정할 때, 만약 $\theta = 0$ 라면 100% 확실하게 $|0\rangle$ 을 측정하고, 만약 $\theta = \frac{1}{2}$ 라면 100% 확실하게 $|1\rangle$ 을 측정합니다(그리고 우리의 양자 컴퓨터가 잡음 없이 완벽하다면). $\theta$ 이 아닌 경우 최종 측정값은 확률적일 뿐이며 많은 것을 알려줄 수 없습니다.

QPE의 정밀도 향상: 더 많은 큐비트

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

이 보다 정밀한 QPE 회로는 단일 비트 버전과 동일하게 시작됩니다: 첫 번째 $m$ 큐비트에 하다마드를 적용하고 나머지 큐비트를 $|\psi\rangle$ 상태로 준비하여 상태를 생성합니다:

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

이제 제어 유니티가 적용됩니다. Qubit $0$ 은 이전과 동일한 단일 $U$ 에 대한 제어입니다. 하지만 이제 쿼비트 $1$ 는 단일 $U^2$ 에 대한 제어이며, $U$ 는 단순히 두 번 적용됩니다. 따라서 $U^2$ 의 고유값은 $e^{2*2\pi i \theta}$ 입니다. 일반적으로 0에서 $m-1$ 까지의 각 큐비트 $k$ 는 단일 큐비트 $U^{2^k}$ 에 대한 제어가 됩니다. 즉, 이러한 각 큐비트는 $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$

따라서 $0$ 와 $2^m-1$ 사이의 어떤 정수에 대한 위상 $\theta = y/2^m$ 이 $y$ 이라면, 이 상태의 역 QFT를 취하면 상태가 됩니다:

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

$|y\rangle$ 에서 $\theta$ 을 추론할 수 있습니다.

그러나 $\theta/2^m$ 이 정수 배수가 아닌 경우, 역 QFT를 사용하면 $\theta$ 에 근사치만 구할 수 있습니다. $\theta$ 에 얼마나 잘 근사하는지는 확률적이기 때문에 항상 최상의 근사치를 얻을 수는 없지만 꽤 근접할 것이며, 더 많은 큐비트 $m$ 를 사용할수록 더 나은 근사치를 얻을 수 있습니다. $\theta$ 의 근사치를 정량화하는 방법에 대해 알아보려면 양자 알고리즘의 기초에 대한 John Watrous의 위상 추정 및 인수분해 강의를 확인하세요.

결론

이 모듈에서는 QFT가 무엇인지, 양자 컴퓨터에서 어떻게 구현되는지, 그리고 문제 해결에 얼마나 유용한지에 대한 개요를 설명했습니다. 양자 위상 추정에서 일차 행렬의 고유값을 알아내는 데 어떻게 사용되는지 살펴봄으로써 그 유용성을 맛보았습니다.

핵심 개념

• 양자 푸리에 변환은 이산 푸리에 변환의 양자 아날로그입니다.
• QFT는 기본 변환의 예입니다.
• 양자 위상 추정 절차는 제어 단일 연산에서 위상 킥백 메커니즘과 역 QFT에 의존합니다.
• QFT와 QPE는 모두 수많은 양자 알고리즘에서 널리 사용되는 하위 루틴입니다.

질문

참/거짓

1. T/F 양자 푸리에 변환은 고전적인 이산 푸리에 변환(DFT)의 양자 아날로그입니다.
2. T/F QFT는 Hadamard 및 CNOT 게이트만 사용하여 구현할 수 있습니다.
3. T/F QFT는 Shor 알고리즘의 핵심 구성 요소입니다.
4. T/F 양자 위상 추정의 출력은 연산자의 고유 벡터를 나타내는 양자 상태입니다.
5. T/F QPE는 역 양자 푸리에 변환(QFT $^\dag$ )을 사용해야 합니다.
6. T/F QPE에서 $\phi$ 단계가 $n$ 비트로 정확히 표현 가능하다면 알고리즘은 확률 1로 올바른 결과를 제공합니다.

짧은 답변

1. $2^n$ 데이터 포인트가 있는 시스템에서 QFT를 수행하려면 몇 개의 큐비트가 필요합니까?
2. 계산 기준 상태가 아닌 상태에서도 QFT를 사용할 수 있나요? 그렇다면 어떻게 되나요?
3. QPE에 사용되는 제어 큐비트 수는 결과 위상 추정치의 해상도에 어떤 영향을 미칩니까?

문제점

1. 행렬 곱셈을 사용하여 QFT 알고리즘의 단계가 실제로 $\text{QFT}_4$ 행렬을 생성하는지 확인합니다:

(이 작업을 손으로 할 필요는 없습니다!)

도전 문제

1. 모든 홀수 계산 기저를 동일하게 중첩한 4쿼비트 상태를 만듭니다: $|\psi\rangle = |0001\rangle + |0011\rangle + |0101\rangle + |0111\rangle +|1001\rangle +|1011\rangle +|1101\rangle +|1111\rangle$. 그런 다음 상태에 대해 QFT를 수행합니다. 결과 상태는 어떻게 되나요? 푸리에 변환에 대한 지식을 활용하여 결과가 왜 타당한지 설명하세요.