양자 알고리즘: 위상 추정
우에다 켄토 (2024년 5월 15일)
이 노트북은 양자 푸리에 변환(QFT)과 양자 위상 추정(QPE)의 기본 개념과 구현을 제공합니다.
원본 강의의 PDF를 다운로드하세요. 일부 코드 스니펫은 정적 이미지이므로 더 이상 사용되지 않을 수 있습니다.
이 실험을 실행하는 데 걸리는 대략적인 QPU 시간은 7초입니다.
1. 소개
양자 푸리에 변환(QFT)
양자 푸리에 변환은 고전적인 이산 푸리에 변환에 대응하는 양자 변환입니다. 이는 양자 상태에 적용되는 선형 변환으로, 계산 기저를 푸리에 기저 표현에 매핑합니다. QFT는 많은 양자 알고리즘에서 핵심적인 역할을 하며, 양자 상태에서 주기성 정보를 추출하는 효율적인 방법을 제공합니다. QFT는 하다마드 게이트 및 제어 위상 게이트( 큐비트용)와 같은 양자 게이트로 연산을 구현하여 기존 푸리에 변환보다 기하급수적으로 빠른 속도를 구현할 수 있습니다.
- 응용 분야 : 큰 정수를 인수분해하는 쇼의 알고리즘과 이산 로그와 같은 양자 알고리즘의 기초가 되는 부분입니다.
양자 위상 추정(QPE)
양자 위상 추정은 단일 연산자의 고유 벡터와 관련된 위상을 추정하는 데 사용되는 양자 알고리즘입니다. 이 알고리즘은 양자 상태의 추상적인 수학적 특성과 계산 응용 프로그램 사이의 가교 역할을 합니다.
- 응용 분야 : 일차 행렬의 고유값 찾기, 양자 시스템 시뮬레이션과 같은 문제를 해결할 수 있습니다.
QFT와 QPE는 함께 기존 컴퓨터로는 해결할 수 없는 문제를 해결하는 많은 양자 알고리즘의 필수적인 근간을 형성합니다. 이 노트가 끝나면 이러한 기술이 어떻게 구현되는지 이해하게 될 것입니다.
2. 양자 푸리에 변환(QFT)의 기초
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는 큐비트에 대해 양자 상태 에 작용하여 이를 양자 상태 에 매핑합니다.
여기서 .
또는 단일 행렬 표현:
2.1. 직관
양자 푸리에 변환(QFT)은 계산 기저와 푸리에 기저라는 두 기저 사이에서 변환합니다. 그렇다면 이 맥락에서 푸리에 기초는 무엇을 의미할까요? 함수 의 푸리에 변환 은 을 주파수 의 사인 곡선 함수로 컨볼루션하는 것을 설명한다는 것을 기억하실 것입니다. 쉽게 설명하자면, 푸리에 변환은 사인 함수(또는 코사인 함수)에서 함수를 만들기 위해 필요한 각 주파수 의 양을 설명하는 함수입니다. 이 맥락에서 QFT가 무엇을 의미하는지 더 잘 이해하려면 네 개의 큐비트를 사용하여 2진수로 인코딩된 숫자를 보여주는 아래의 단계별 이미지를 고려해 보세요:
계산 기반에서는 및 상태를 사용하여 숫자를 2진수로 저장합니다.
가장 왼쪽 큐비트는 숫자가 1씩 증가할 때마다, 그다음 큐비트는 2씩 증가할 때마다, 세 번째 큐비트는 4씩 증가할 때마다 뒤집히는 식으로 서로 다른 큐비트가 바뀌는 빈도에 주목하세요.
이러한 상태에 양자 푸리에 변환을 적용하면 다음과 같이 매핑됩니다
(물결표(~)를 사용하여 푸리에 단위로 상태를 표시하는 경우가 많습니다).
푸리에 단위에서는 Z축을 중심으로 다양한 회전을 사용하여 숫자를 저장합니다:
IFRAME
저장하려는 숫자는 각 큐비트가 Z축을 중심으로 회전하는 각도를 나타냅니다. 상태 에서 모든 큐비트는 상태 에 있습니다. 위의 예에서 볼 수 있듯이, 4개의 큐비트에 상태 를 인코딩하기 위해 가장 왼쪽 큐비트를 풀턴( 라디안)으로 회전시켰습니다. 다음 큐비트는 이 각도의 두 배( 라디안 또는 풀턴)로 돌리고, 그 다음 큐비트에 대해 이 각도를 두 배로 돌리는 방식으로 진행됩니다.
다시 한 번, 각 큐비트가 변경되는 빈도에 주목하세요. 이 경우 가장 왼쪽 큐비트(qubit 0)의 주파수가 가장 낮고, 가장 오른쪽이 가장 높습니다.
2.2 예시: 1-큐비트 양자장 이론
의 경우를 고려해 보겠습니다.
단일 행렬을 작성할 수 있습니다:
이 작업은 하다마드 게이트( )를 적용한 결과입니다.
2.3 QFT의 제품 표현
상태 에 대해 작동하는 , 에 대한 변환을 일반화해 보겠습니다.
2.4 예시: 3 큐비트 양자장 이론(QFT) 회로 구성
위의 설명만으로는 QFT 회로를 구성하는 방법이 명확하지 않을 수 있습니다. 현재로서는 3개의 큐비트가 서로 다른 '속도'로 진화하는 단계를 가질 것으로 예상하고 있습니다. 이것이 어떻게 회로로 변환되는지 정확히 이해하는 것은 독자의 몫으로 남겨져 있습니다. 강의 PDF에는 여러 가지 도표와 예제가 있습니다. 추가 리소스에는 양자 알고리즘의 기초 과정의 이 강의가 포함되어 있습니다.
저희는 시뮬레이터만을 사용하여 QFT를 시연할 것이며, 따라서 양자 위상 추정으로 넘어갈 때까지 키스킷 패턴 프레임워크는 사용하지 않을 것입니다.
# 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")Output:
qc.h(1)
qc.cp(pi / 2, 0, 1) # Controlled-phase gate from qubit 0 to qubit 1
qc.draw(output="mpl")Output:
qc.h(0)
qc.draw(output="mpl")Output:
qc.swap(0, 2)
qc.draw(output="mpl")Output:
예를 들어 에 QFT를 적용해 보겠습니다.
먼저 정수 5의 이진 표기법을 확인하고 상태 5를 인코딩하는 회로를 생성합니다:
bin(5)Output:
'0b101'
qc = QuantumCircuit(3)
qc.x(0)
qc.x(2)
qc.draw(output="mpl")Output:
Aer 시뮬레이터를 사용하여 양자 상태를 확인합니다:
statevector = Statevector(qc)
plot_bloch_multivector(statevector)Output:
마지막으로 QFT를 추가하고 큐비트의 최종 상태를 확인합니다:
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")Output:
statevector = Statevector(qc)
plot_bloch_multivector(statevector)Output:
QFT 기능이 올바르게 작동하는 것을 확인할 수 있습니다. 큐비트 0은 풀턴, 큐비트 1은 풀턴(풀턴의 에 해당), 큐비트 2는 풀턴(풀턴의 에 해당)으로 회전했습니다.
2.5 연습: QFT
(1) 4 큐비트의 QFT를 구현합니다.
##your code goes here##(2) 에 QFT를 적용하고 블로흐 구를 사용하여 상태벡터를 시뮬레이션하고 플롯합니다.
##your code goes here##연습문제 해답: 양자장론
(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")Output:
(2)
bin(14)Output:
'0b1110'
qc = QuantumCircuit(4)
qc.x(1)
qc.x(2)
qc.x(3)
qc.draw("mpl")Output:
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")Output:
statevector = Statevector(qc)
plot_bloch_multivector(statevector)Output:
3. 양자 위상 추정(QPE)의 기초
단일 연산 이 주어지면 QPE는 이 단일 연산이므로 에서 을 추정하며, 모든 고유값은 1의 규범을 갖습니다.
3.1 절차
1. 설정
는 하나의 큐비트 레지스터 세트에 있습니다. 큐비트 추가 세트는 값 을 저장할 카운팅 레지스터를 형성합니다:
2. 중첩
계수 레지스터에 -비트 하다마드 게이트 연산 을 적용합니다:
3. 통제된 단일 작업
해당 제어 비트가 인 경우에만 대상 레지스터에 단항 연산자 를 적용하는 제어 단항 을 도입해야 합니다. 은 고유 벡터 를 갖는 단일 연산자이므로 이 됩니다:
3.2 예시: T-게이트 QPE
게이트를 QPE의 예로 사용하여 의 위상을 추정해 보겠습니다.
찾을 수 있을 것으로 기대합니다:
여기서,
게이트의 고유 벡터를 게이트를 적용하여 를 초기화합니다:
qpe = QuantumCircuit(4, 3)
qpe.x(3)
qpe.draw(output="mpl")Output:
다음으로 하다마드 게이트를 카운팅 큐비트에 적용합니다:
for qubit in range(3):
qpe.h(qubit)
qpe.draw(output="mpl")Output:
당사는 통제된 단일 작업을 수행합니다:
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")Output:
역 양자 푸리에 변환을 적용하여 계수 레지스터의 상태를 변환한 다음 계수 레지스터를 측정합니다:
from qiskit.circuit.library import QFT# Apply inverse QFT
qpe.append(QFT(3, inverse=True), [0, 1, 2])
qpe.draw(output="mpl")Output:
for n in range(3):
qpe.measure(n, n)
qpe.draw(output="mpl")Output:
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)Output:
우리는 확실하게 하나의 결과(001)를 얻을 수 있으며, 이는 소수로 변환됩니다: 1. 이제 결과(1)를 으로 나누어 을 구해야 합니다:
Shor의 알고리즘을 사용하면 미지수로 회로를 만들고 을 구하여 숫자를 인수분해할 수 있습니다.
3.3 운동
계산에 큐비트 3개, 고유 벡터에 큐비트 1개를 사용하여 을 추정합니다.
. 을 구현하고 싶으므로 을 설정해야 합니다.
##your code goes here##연습 문제 해설:
# 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")Output:
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)Output:
4. ‘ IBM Quantum ’ 샘플러 프리미티브를 사용한 실행
실제 양자 장치를 사용하여 QPE를 수행하고 4단계의 키스킷 패턴을 따릅니다.
- 문제를 퀀텀 네이티브 형식으로 매핑하기
- 회로 최적화
- 대상 회로 실행
- 결과 후처리
from qiskit_ibm_runtime import QiskitRuntimeService
from qiskit_ibm_runtime import Sampler# Loading your IBM Quantum® account(s)
service = QiskitRuntimeService()4.1 1단계: 문제를 양자 회로 및 연산자로 매핑하기
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")Output:
backend = service.least_busy(simulator=False, operational=True, min_num_qubits=4)
print(backend)Output:
<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)Output:
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)Output:
job id: d13p4zb5z6q00087ag00
job = service.job(job_id) # Input your job-id between the quotations
job.status()Output:
'DONE'
result_real = job.result()
print(result_real)Output:
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())Output:
# See the version of Qiskit
import qiskit
qiskit.__version__Output:
'2.0.2'