양자 알고리즘: 위상 추정

참고

Kento Ueda (15 May 2024)

이 노트북은 양자 푸리에 변환(QFT)과 양자 위상 추정(QPE)의 기본 개념과 구현 방법을 설명합니다.

원본 강의의 PDF를 다운로드하세요. 일부 코드 스니펫은 정적 이미지이므로 더 이상 사용되지 않을 수 있습니다.

이 실험을 실행하는 데 필요한 QPU 시간은 약 7초입니다.

1. 소개

양자 푸리에 변환 (QFT)

양자 푸리에 변환은 고전적인 이산 푸리에 변환의 양자 버전입니다. 이는 양자 상태에 적용되는 선형 변환으로, 계산 기저를 푸리에 기저 표현으로 매핑합니다. QFT는 양자 상태에서 주기 정보를 효율적으로 추출하는 방법을 제공하며, 많은 양자 알고리즘에서 핵심적인 역할을 합니다. QFT는 $N$개의 Qubit에 대해 Hadamard Gate 및 제어 위상 Gate와 같은 양자 Gate를 사용하여 $O(N^2)$ 연산으로 구현할 수 있으며, 이를 통해 고전적인 푸리에 변환 대비 지수적 가속을 실현합니다.

• 응용: 큰 정수의 인수 분해 및 이산 로그를 위한 Shor 알고리즘과 같은 양자 알고리즘의 기초적인 구성 요소입니다.

양자 위상 추정 (QPE)

양자 위상 추정은 유니터리 연산자의 고유 벡터와 연관된 위상을 추정하는 양자 알고리즘입니다. 이 알고리즘은 양자 상태의 추상적인 수학적 특성과 그 계산적 응용 사이의 다리 역할을 합니다.

• 응용: 유니터리 행렬의 고유값 찾기 및 양자 시스템 시뮬레이션과 같은 문제를 해결할 수 있습니다.

QFT와 QPE는 함께 고전 컴퓨터로는 불가능한 문제를 해결하는 많은 양자 알고리즘의 핵심 기반을 형성합니다. 이 노트북을 마치면 이러한 기법들이 어떻게 구현되는지 이해하게 될 것입니다.

2. 양자 푸리에 변환 (QFT) 기초

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

from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister
from qiskit_aer import AerSimulator
from qiskit.visualization import plot_histogram, plot_bloch_multivector
from qiskit.quantum_info import Statevector
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager
from qiskit_ibm_runtime import Sampler

from numpy import pi

이산 푸리에 변환과의 유추로, QFT는 $N$개의 Qubit에 대해 양자 상태 $\vert X\rangle = \sum_{j=0}^{N-1} x_j \vert j \rangle$에 작용하여 이를 양자 상태 $\vert Y\rangle = \sum_{k=0}^{N-1} y_k \vert k \rangle$로 매핑합니다.

$$QFT_{N}: \vert j \rangle \mapsto \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}\omega_N^{jk} \vert k \rangle$$

여기서 $\omega_N^{jk} = e^{2\pi i \frac{jk}{N}}$입니다.

또는 유니터리 행렬 표현으로:

$$U_{QFT} = \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} \sum_{k=0}^{N-1} \omega_N^{jk} \vert k \rangle \langle j \vert$$

2.1. 직관적 이해

양자 푸리에 변환(QFT)은 두 기저, 즉 계산 기저(Z 기저)와 푸리에 기저 사이를 변환합니다. 그렇다면 이 맥락에서 푸리에 기저란 무엇을 의미할까요? 함수 $f(x)$의 푸리에 변환 $F(\omega)$는 $f(x)$를 주파수 $\omega$의 사인 함수와의 합성곱으로 나타낸다는 것을 기억할 것입니다. 쉽게 말해, 푸리에 변환은 $f(x)$를 사인 함수(또는 코사인 함수)로 구성하는 데 각 주파수 $\omega$가 얼마나 필요한지를 나타내는 함수입니다. QFT가 이 맥락에서 무엇을 의미하는지 더 잘 이해하기 위해, 4개의 Qubit을 사용해 이진수로 숫자를 인코딩하는 아래의 단계별 이미지를 살펴보세요.

계산 기저에서는 $|0\rangle$ 및 $|1\rangle$ 상태를 사용해 이진수로 숫자를 저장합니다.

서로 다른 Qubit이 변화하는 빈도에 주목하세요. 가장 왼쪽 Qubit은 숫자가 1씩 증가할 때마다 뒤집히고, 그 다음은 2씩 증가할 때마다, 세 번째는 4씩 증가할 때마다 뒤집힙니다.

이 상태들에 양자 푸리에 변환을 적용하면 다음과 같이 매핑됩니다.

$$|\text{계산 기저의 상태}\rangle \quad \xrightarrow[]{\text{QFT}} \quad |\text{푸리에 기저의 상태}\rangle$$ $$\text{QFT}|x\rangle = |\widetilde{x}\rangle$$

(푸리에 기저의 상태는 흔히 틸드(~)로 표기합니다.)

푸리에 기저에서는 Z축을 기준으로 서로 다른 회전을 사용해 숫자를 저장합니다.

IFRAME

저장하려는 숫자가 각 Qubit의 Z축 회전 각도를 결정합니다. $|\widetilde{0}\rangle$ 상태에서는 모든 Qubit이 $|{+}\rangle$ 상태에 있습니다. 위의 예시에서 보듯, 4개의 Qubit에서 $|\widetilde{5}\rangle$ 상태를 인코딩하려면 가장 왼쪽 Qubit을 $\tfrac{5}{2^n} = \tfrac{5}{16}$ 바퀴 ($\tfrac{5}{16}\times 2\pi$ 라디안)만큼 회전시킵니다. 그 다음 Qubit은 이것의 두 배($\tfrac{10}{16}\times 2\pi$ 라디안, 즉 $10/16$ 바퀴)이며, 그 다음 Qubit에서는 이 각도가 다시 두 배가 됩니다.

다시 한번, 각 Qubit이 변화하는 빈도에 주목하세요. 이 경우 가장 왼쪽의 Qubit(qubit 0)이 가장 낮은 주파수를 가지며, 가장 오른쪽이 가장 높은 주파수를 갖습니다.

2.2 예제: 1-Qubit QFT

$N = 2^1 = 2$인 경우를 살펴보겠습니다.

유니터리 행렬은 다음과 같이 쓸 수 있습니다.

$$\begin{aligned} U_{QFT} & = \frac{1}{\sqrt{2}} \sum_{j=0}^{1} \sum_{k=0}^{1} \omega_2^{jk} \vert k \rangle \langle j \vert \\ & = \frac{1}{\sqrt{2}} (\omega_2^{0} \vert 0 \rangle \langle 0 \vert + \omega_2^{0} \vert 0 \rangle \langle 1 \vert + \omega_2^{0} \vert 1 \rangle \langle 0 \vert + \omega_2^{1} \vert 1 \rangle \langle 1 \vert) \\ & = \frac{1}{\sqrt{2}} (\vert 0 \rangle \langle 0 \vert + \vert 0 \rangle \langle 1 \vert + \vert 1 \rangle \langle 0 \vert - \vert 1 \rangle \langle 1 \vert) \\ & = H \end{aligned}$$

이 연산은 Hadamard Gate ($H$)를 적용한 결과입니다.

2.3 QFT의 곱 표현

$N = 2^n$에 대한 변환을 일반화하여, $\vert x \rangle = \vert x_1\ldots x_n \rangle$ 상태에 작용하는 $QFT_{N}$을 살펴보겠습니다.

$$\begin{aligned} QFT_N\vert x \rangle & = \frac{1}{\sqrt{N}} \sum_{y=0}^{N-1}\omega_N^{xy} \vert y \rangle \\ & = \frac{1}{\sqrt{N}} \sum_{y=0}^{N-1} e^{2 \pi i xy / 2^n} \vert y \rangle ~\text{since}\: \omega_N^{xy} = e^{2\pi i \frac{xy}{N}} \:\text{and}\: N = 2^n \\ & = \frac{1}{\sqrt{N}} \sum_{y=0}^{N-1} e^{2 \pi i \left(\sum_{k=1}^n y_k/2^k\right) x} \vert y_1 \ldots y_n \rangle \:\text{rewriting in fractional binary notation}\: y = y_1\ldots y_n, y/2^n = \sum_{k=1}^n y_k/2^k \\ & = \frac{1}{\sqrt{N}} \sum_{y=0}^{N-1} \prod_{k=1}^n e^{2 \pi i x y_k/2^k } \vert y_1 \ldots y_n \rangle \:\text{after expanding the exponential of a sum to a product of exponentials,} \\ & = \frac{1}{\sqrt{N}} \bigotimes_{k=1}^n \left(\vert0\rangle + e^{2 \pi i x /2^k } \vert1\rangle \right) \:\text{after rearranging the sum and products, and expanding} \sum_{y=0}^{N-1} = \sum_{y_1=0}^{1}\sum_{y_2=0}^{1}\ldots\sum_{y_n=0}^{1} \\ & = \frac{1}{\sqrt{N}} \left(\vert0\rangle + e^{\frac{2\pi i}{2}x} \vert1\rangle\right) \otimes \left(\vert0\rangle + e^{\frac{2\pi i}{2^2}x} \vert1\rangle\right) \otimes \ldots \otimes \left(\vert0\rangle + e^{\frac{2\pi i}{2^{n-1}}x} \vert1\rangle\right) \otimes \left(\vert0\rangle + e^{\frac{2\pi i}{2^n}x} \vert1\rangle\right) \end{aligned}$$

2.4 예제: 3-Qubit QFT Circuit 구성

위의 설명만으로는 QFT Circuit을 어떻게 구성해야 하는지 명확하지 않을 수 있습니다. 우선, 세 개의 Qubit이 서로 다른 "속도"로 위상이 변화할 것이라는 점만 주목하세요. 이것이 Circuit으로 어떻게 변환되는지 정확히 이해하는 것은 독자의 연습 문제로 남겨둡니다. 강의 PDF에는 여러 다이어그램과 예제가 있습니다. 추가 자료로는 양자 알고리즘 기초 과정의 이 강의를 참고하세요.

여기서는 시뮬레이터만을 사용하여 QFT를 시연하며, 양자 위상 추정으로 넘어갈 때까지 Qiskit 패턴 프레임워크는 사용하지 않습니다.

# Prepare for 3 qubits circuit
qr = QuantumRegister(3)
cr = ClassicalRegister(3)
qc = QuantumCircuit(qr, cr)

qc.h(2)
qc.cp(pi / 2, 1, 2)  # Controlled-phase gate from qubit 1 to qubit 2
qc.cp(pi / 4, 0, 2)  # Controlled-phase gate from qubit 0 to qubit 2
qc.draw(output="mpl")

qc.h(1)
qc.cp(pi / 2, 0, 1)  # Controlled-phase gate from qubit 0 to qubit 1

qc.draw(output="mpl")

qc.h(0)

qc.draw(output="mpl")

qc.swap(0, 2)

qc.draw(output="mpl")

$|5\rangle$에 QFT를 적용하는 예제를 살펴보겠습니다.

먼저, 정수 5의 이진 표기를 확인하고 상태 5를 인코딩하는 Circuit을 만듭니다.

bin(5)

'0b101'

qc = QuantumCircuit(3)

qc.x(0)
qc.x(2)
qc.draw(output="mpl")

Aer 시뮬레이터를 사용하여 양자 상태를 확인합니다.

statevector = Statevector(qc)
plot_bloch_multivector(statevector)

마지막으로, QFT를 추가하고 Qubit의 최종 상태를 확인합니다.

qc.h(2)
qc.cp(pi / 2, 1, 2)
qc.cp(pi / 4, 0, 2)

qc.h(1)
qc.cp(pi / 2, 0, 1)

qc.h(0)

qc.swap(0, 2)

qc.draw(output="mpl")

statevector = Statevector(qc)
plot_bloch_multivector(statevector)

QFT 함수가 올바르게 작동했음을 확인할 수 있습니다. Qubit 0은 $\tfrac{5}{8}$ 바퀴만큼 회전했고, Qubit 1은 $\tfrac{10}{8}$ 바퀴($\tfrac{1}{4}$ 바퀴에 해당), Qubit 2는 $\tfrac{20}{8}$ 바퀴($\tfrac{1}{2}$ 바퀴에 해당)만큼 회전했습니다.

2.5 연습문제: QFT

(1) 4 Qubit QFT를 구현하세요.

##your code goes here##

(2) $|14\rangle$에 QFT를 적용하고, 시뮬레이션한 뒤 블로흐 구(Bloch sphere)를 사용하여 상태벡터를 시각화하세요.

##your code goes here##

연습문제 풀이: QFT

(1)

qr = QuantumRegister(4)
cr = ClassicalRegister(4)
qc = QuantumCircuit(qr, cr)

qc.h(3)
qc.cp(pi / 2, 2, 3)
qc.cp(pi / 4, 1, 3)
qc.cp(pi / 8, 0, 3)

qc.h(2)
qc.cp(pi / 2, 1, 2)
qc.cp(pi / 4, 0, 2)

qc.h(1)
qc.cp(pi / 2, 0, 1)

qc.h(0)

qc.swap(0, 3)
qc.swap(1, 2)

qc.draw(output="mpl")

(2)

bin(14)

'0b1110'

qc = QuantumCircuit(4)

qc.x(1)
qc.x(2)
qc.x(3)
qc.draw("mpl")

qc.h(3)
qc.cp(pi / 2, 2, 3)
qc.cp(pi / 4, 1, 3)
qc.cp(pi / 8, 0, 3)

qc.h(2)
qc.cp(pi / 2, 1, 2)
qc.cp(pi / 4, 0, 2)

qc.h(1)
qc.cp(pi / 2, 0, 1)
qc.h(0)

qc.swap(0, 3)
qc.swap(1, 2)

qc.draw(output="mpl")

statevector = Statevector(qc)
plot_bloch_multivector(statevector)

3. 양자 위상 추정(QPE)의 기초

유니터리 연산 $U$가 주어지면, QPE는 $U\vert\psi \rangle =e^{\boldsymbol{2\pi i} \theta }|\psi \rangle$에서 $\theta$를 추정합니다. $U$는 유니터리이므로 모든 고유값의 노름은 1입니다.

3.1 절차

1. 초기 설정

$\vert\psi\rangle$은 한 세트의 Qubit 레지스터에 있습니다. 추가로 $n$개의 Qubit으로 구성된 계수 레지스터에 $2^n\theta$ 값을 저장합니다:

$$|\psi_0\rangle = \lvert 0 \rangle^{\otimes n} \lvert \psi \rangle$$

2. 중첩

계수 레지스터에 $n$비트 Hadamard Gate 연산 $H^{\otimes n}$을 적용합니다:

$$|\psi_1\rangle = {\frac {1}{2^{\frac {n}{2}}}}\left(|0\rangle +|1\rangle \right)^{\otimes n} \lvert \psi \rangle$$

3. 제어 유니터리 연산

제어 Qubit이 $|1\rangle$인 경우에만 목표 레지스터에 유니터리 연산자 $U$를 적용하는 제어 유니터리 $CU$가 필요합니다. $U$는 $U|\psi \rangle =e^{\boldsymbol{2\pi i} \theta }|\psi \rangle$를 만족하는 고유벡터 $|\psi\rangle$을 가진 유니터리 연산자이므로, 다음이 성립합니다:

$$U^{2^{j}}|\psi \rangle =U^{2^{j}-1}U|\psi \rangle =U^{2^{j}-1}e^{2\pi i\theta }|\psi \rangle =\cdots =e^{2\pi i2^{j}\theta }|\psi \rangle$$

3.2 예제: T-Gate QPE

QPE의 예제로 $T$ Gate를 사용하여 위상 $\theta$를 추정해 보겠습니다.

$$T|1\rangle = \begin{pmatrix} 1 & 0\\ 0 & e^\frac{i\pi}{4}\\ \end{pmatrix} \begin{pmatrix} 0\\ 1\\ \end{pmatrix} = e^\frac{i\pi}{4}|1\rangle$$

기대 결과:

$$\theta = \frac{1}{8}$$

여기서

$$T|1\rangle = e^{2i\pi\theta}|1\rangle$$

$X$ Gate를 적용하여 $T$ Gate의 고유벡터인 $\vert\psi\rangle = \vert1\rangle$로 초기화합니다:

qpe = QuantumCircuit(4, 3)
qpe.x(3)
qpe.draw(output="mpl")

다음으로, 계수 Qubit에 Hadamard Gate를 적용합니다:

for qubit in range(3):
    qpe.h(qubit)
qpe.draw(output="mpl")

제어 유니터리 연산을 수행합니다:

repetitions = 1
for counting_qubit in range(3):
    for i in range(repetitions):
        qpe.cp(pi / 4, counting_qubit, 3)  # This is C-U
    repetitions *= 2
qpe.draw(output="mpl")

계수 레지스터의 상태를 변환하기 위해 역 양자 푸리에 변환을 적용한 후, 계수 레지스터를 측정합니다:

from qiskit.circuit.library import QFT

# Apply inverse QFT
qpe.append(QFT(3, inverse=True), [0, 1, 2])
qpe.draw(output="mpl")

for n in range(3):
    qpe.measure(n, n)
qpe.draw(output="mpl")

Aer 시뮬레이터를 사용하여 시뮬레이션할 수 있습니다:

aer_sim = AerSimulator()
shots = 2048

pm = generate_preset_pass_manager(backend=aer_sim, optimization_level=1)
t_qpe = pm.run(qpe)

sampler = Sampler(mode=aer_sim)
job = sampler.run([t_qpe], shots=shots)
result = job.result()
answer = result[0].data.c.get_counts()

plot_histogram(answer)

결과(001)가 확실하게 하나만 나오는 것을 확인할 수 있으며, 이는 십진수로 1에 해당합니다. 이제 결과(1)를 $2^n$으로 나누어 $\theta$를 구합니다:

$$\theta = \frac{1}{2^3} = \frac{1}{8}$$

Shor 알고리즘을 사용하면 $\theta$가 미지수인 Circuit을 구성하고 $\theta$를 구함으로써 숫자를 인수분해할 수 있습니다.

3.3 연습 문제

계수를 위한 3개의 Qubit과 고유벡터용 1개의 Qubit을 사용하여 $\theta = 1/3$을 추정하세요.

$P|1\rangle = e^{i\lambda}|1\rangle$. $U|1\rangle = e^{2\pi i \tfrac{1}{3}}|1\rangle$을 구현하려면 $\lambda = \tfrac{2 \pi}{3}$으로 설정해야 합니다.

##your code goes here##

연습 문제 풀이: $\theta = 1/3$

# Create and set up circuit
qpe = QuantumCircuit(4, 3)

# Apply H-Gates to counting qubits:
for qubit in range(3):
    qpe.h(qubit)

# Prepare our eigenstate |psi>:
qpe.x(3)

# Do the controlled-U operations:
angle = 2 * pi / 3
repetitions = 1
for counting_qubit in range(3):
    for i in range(repetitions):
        qpe.cp(angle, counting_qubit, 3)
    repetitions *= 2

# Do the inverse QFT:
qpe.append(QFT(3, inverse=True), [0, 1, 2])

for n in range(3):
    qpe.measure(n, n)

qpe.draw(output="mpl")

aer_sim = AerSimulator()
shots = 4096

pm = generate_preset_pass_manager(backend=aer_sim, optimization_level=1)
t_qpe = pm.run(qpe)

sampler = Sampler(mode=aer_sim)
job = sampler.run([t_qpe], shots=shots)
result = job.result()
answer = result[0].data.c.get_counts()

plot_histogram(answer)

4. Qiskit Runtime Sampler primitive을 사용한 실행

실제 양자 장치를 사용하여 QPE를 수행하고, Qiskit 패턴의 4단계를 따릅니다.

1. 문제를 양자 네이티브 형식으로 매핑하기
2. Circuit 최적화하기
3. 대상 Circuit 실행하기
4. 결과 후처리하기

from qiskit_ibm_runtime import QiskitRuntimeService
from qiskit_ibm_runtime import Sampler

# Loading your IBM Quantum® account(s)

service = QiskitRuntimeService()

4.1 1단계: 문제를 양자 Circuit 및 연산자로 매핑하기

qpe = QuantumCircuit(4, 3)
qpe.x(3)
for qubit in range(3):
    qpe.h(qubit)
repetitions = 1
for counting_qubit in range(3):
    for i in range(repetitions):
        qpe.cp(pi / 4, counting_qubit, 3)  # This is C-U
    repetitions *= 2
qpe.append(QFT(3, inverse=True), [0, 1, 2])
for n in range(3):
    qpe.measure(n, n)
qpe.draw(output="mpl")

backend = service.least_busy(simulator=False, operational=True, min_num_qubits=4)

print(backend)

<IBMBackend('ibm_strasbourg')>

4.2 2단계: 대상 하드웨어에 맞게 최적화하기

# Transpile the circuit into basis gates executable on the hardware
pm = generate_preset_pass_manager(backend=backend, optimization_level=2)
qc_compiled = pm.run(qpe)

qc_compiled.draw("mpl", idle_wires=False)

4.3 3단계: 대상 하드웨어에서 실행하기

real_sampler = Sampler(mode=backend)
job = real_sampler.run([qc_compiled], shots=1024)
job_id = job.job_id()
print("job id:", job_id)

job id: d13p4zb5z6q00087ag00

job = service.job(job_id)  # Input your job-id between the quotations
job.status()

'DONE'

result_real = job.result()
print(result_real)

PrimitiveResult([SamplerPubResult(data=DataBin(c=BitArray(<shape=(), num_shots=1024, num_bits=3>)), metadata={'circuit_metadata': {}})], metadata={'execution': {'execution_spans': ExecutionSpans([DoubleSliceSpan(<start='2025-06-09 22:39:00', stop='2025-06-09 22:39:00', size=1024>)])}, 'version': 2})

4.4 4단계: 결과 후처리하기

from qiskit.visualization import plot_histogram

plot_histogram(result_real[0].data.c.get_counts())

# See the version of Qiskit
import qiskit

qiskit.__version__

'2.0.2'