도이치-요자 알고리즘
이 Qiskit in Classrooms 모듈을 사용하려면, 학생들의 Python 환경에 다음 패키지가 설치되어 있 어야 합니다:
qiskitv2.1.0 이상qiskit-ibm-runtimev0.40.1 이상qiskit-aerv0.17.0 이상qiskit.visualizationnumpypylatexenc
위 패키지 설치 및 설정 방법은 Qiskit 설치 가이드를 참고하세요. 실제 양자 컴퓨터에서 작업을 실행하려면, IBM Cloud 계정 설정 가이드의 단계에 따라 IBM Quantum® 계정을 만들어야 합니다.
이 모듈은 테스트 시 QPU 시간 4초를 사용했습니다. 이는 추정치이며, 실제 사용량은 다를 수 있습니다.
# 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'
아래에서 Dr. Katie McCormick의 모듈 안내 영상을 시청하거나, 여기를 클릭하여 YouTube에서 시청하세요.
소개
1980년대 초, 양자 물리학자들과 컴퓨터 과학자들 은 양자역학을 활용하면 고전 컴퓨터보다 훨씬 강력한 연산을 수행할 수 있다는 막연한 개념을 갖고 있었습니다. 그 근거는 다음과 같았습니다: 고전 컴퓨터로 양자 시스템을 시뮬레이션하기는 어렵지만, 양자 컴퓨터는 이를 더 효율적으로 처리할 수 있을 것이었습니다. 그리고 양자 컴퓨터가 양자 시스템을 더 효율적으로 시뮬레이션할 수 있다면, 고전 컴퓨터보다 더 효율적으로 수행할 수 있는 다른 작업도 있을 것이라고 생각했습니다.
논리는 타당했지만, 세부 사항은 아직 정립되지 않았습니다. 이 흐름은 1985년 David Deutsch가 최초의 "범용 양자 컴퓨터"를 기술하면서 시작되었습니다. 같은 논문에서 그는 양자 컴퓨터가 고전 컴퓨터보다 더 효율적으로 해결할 수 있는 최초의 예시 문제를 제시했습니다. 이 첫 번째 장난감 예시는 현재 "도이치 알고리즘"으로 알려져 있습니다. 도이치 알고리즘의 개선은 미미했지만, 도이치는 몇 년 후 Richard Jozsa와 함께 고전 컴퓨터와 양자 컴퓨터 사이의 격차를 더욱 넓혔습니다.
도이치 알고리즘과 도이치-요자 확장 알고리즘은 특별히 실용적이지는 않지만, 여러 이유로 매우 중요합니다:
- 역사적으로, 이 알고리즘들은 고전 알고리즘을 능가한다고 증명된 최초의 양자 알고리즘 중 일부였습니다. 이를 이해하면 양자 컴퓨팅에 대한 커뮤니티의 사고 방식이 어떻게 발전해 왔는지 파악하는 데 도움이 됩니다.
- 이 알고리즘들은 놀라울 정도로 미묘한 질문에 대한 답의 몇 가지 측면을 이해하는 데 도움이 됩니다: 양자 컴퓨팅의 힘은 어디서 나오는가? 때때로 양자 컴퓨터는 지수적으로 확장되는 거대한 병렬 프로세서에 비유됩니다. 하지만 이는 완전히 정확한 설명이 아닙니다. 이 질문에 대한 답의 일부는 소위 "양자 병렬성"에 있지만, 단 한 번의 실행에서 최대한 많은 정보를 추출하는 것은 섬세한 기술입니다. 도이치 및 도이치-요자 알고리즘은 이를 어떻게 구현할 수 있는지 보여줍니다.
이 모듈에서는 도이치 알고리즘, 도이치-요자 알고리즘, 그리고 이들이 양자 컴퓨팅의 힘에 대해 가르쳐 주는 것들을 배웁니다.
양자 병렬성과 그 한계
양자 컴퓨팅의 힘 중 일부는 "양자 병렬성"에서 비롯됩니다. 이는 본질적으로 여러 입력에 대해 동시에 연산을 수행하는 능력으로, Qubit 입력 상태가 여러 고전적으로 허용된 상태의 중첩 상태에 있을 수 있기 때문입니다. 그러나 양자 Circuit이 여러 입력 상태를 동시에 평가할 수 있다 하더라도, 그 모든 정보를 한 번에 추출하는 것은 불가능합니다.
이를 이해하기 위해, 비트 와 그 비트에 적용되는 함수 가 있다고 가정해 봅시다. 단일 비트를 다른 단일 비트로 취하는 이진 함수는 네 가지가 있습니다:
| 0 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 |
우리는 가 이 함수들(1~4) 중 어떤 것인지 알고 싶습니다. 고전적으로는 함수를 두 번 실행해야 합니다 — 으로 한 번, 로 한 번. 하지만 양자 Circuit으로 더 잘 할 수 있는지 살펴봅시다. 다음 Gate를 사용하여 함수에 대해 알아볼 수 있습니다:
여기서 Gate는 를 계산합니다. 여기서 는 Qubit 0의 상태이고, 이를 Qubit 1에 적용합니다. 따라서 결과 상태 는 일 때 단순히 이 됩니다. 이는 함수 를 알기 위해 필요한 모든 정보를 포함합니다: Qubit 0은 가 무엇인지, Qubit 1은 가 무엇인지 알려줍니다. 따라서 으로 초기화하면, 두 Qubit의 최종 상태는 다음과 같습니다: . 그렇다면 그 정보에 어떻게 접근할 수 있을까요?
2.1. Qiskit으로 시도해 보세요:
Qiskit을 사용하여 위의 네 가지 가능한 함수 중 하나를 무작위로 선택하고 Circuit을 실행합니다. 그런 다음 양자 Circuit의 측정값을 사용하여 최대한 적은 실행 횟수로 함수를 알아내는 것이 여러분의 과제입니다.
이 첫 번째 실험과 모듈 전반에 걸쳐, 워크플로우를 다음 단계로 분류하는 "Qiskit patterns"라는 양자 컴퓨팅 프레임워크를 사용합니다:
- 1단계: 고전적 입력을 양자 문제로 매핑
- 2단계: 양자 실행을 위한 문제 최적화
- 3단계: Qiskit Runtime Primitives를 사용하여 실행
- 4단계: 후처리 및 고전적 분석
먼저 Qiskit Runtime Primitives를 포함한 필요한 패키지를 로드합니다. 또한 우리에게 사용 가능한 가장 한가한 양자 컴퓨터를 선택합니다.
아래에는 처음 사용 시 자격 증명을 저장하는 코드가 있습니다. 환경에 저장한 후에는 노트북에서 이 정보를 반드시 삭제하세요. 그래야 노트북을 공유할 때 자격 증명이 실수로 공유되지 않습니다. 자세한 안내는 IBM Cloud 계정 설정 및 신뢰할 수 없는 환경에서 서비스 초기화를 참고하세요.
# 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
# Syntax for first saving your token. Delete these lines after saving your credentials.
# QiskitRuntimeService.save_account(channel='ibm_quantum_platform', instance = '<YOUR_IBM_INSTANCE_CRN>', token='<YOUR_API_KEY>', overwrite=True, set_as_default=True)
# service = QiskitRuntimeService(channel='ibm_quantum_platform')
# Load saved credentials
service = QiskitRuntimeService()
# Use the least busy backend, or uncomment the loading of a specific backend like "ibm_brisbane".
# backend = service.least_busy(operational=True, simulator=False, min_num_qubits = 127)
backend = service.backend("ibm_brisbane")
print(backend.name)
sampler = Sampler(mode=backend)
ibm_brisbane
아래 셀을 통해 노트북 전반에 걸쳐 시뮬레이터와 실제 하드웨어 사용 간에 전환할 수 있습니다. 지금 실행하는 것을 권장합니다:
# 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
# Alternatively, load a fake backend with generic properties and define a simulator.
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)
# You could also define a simulator-based sampler using a generic backend:
# backend_gen = GenericBackendV2(num_qubits=18)
# sampler_gen = BackendSamplerV2(backend=backend_gen)
필요한 패키지를 로드했으니 이제 Qiskit patterns 워크플로우를 진행할 수 있습니다. 아래 매핑 단계에서는 먼저 단일 비트를 다른 단일 비트로 취하는 네 가지 가능한 함수 중 하나를 선택하는 함수를 만듭니다.
# Step 1: Map
from qiskit import QuantumCircuit
qc = QuantumCircuit(2)
def twobit_function(case: int):
"""
Generate a valid two-bit function as a `QuantumCircuit`.
"""
if case not in [1, 2, 3, 4]:
raise ValueError("`case` must be 1, 2, 3, or 4.")
f = QuantumCircuit(2)
if case in [2, 3]:
f.cx(0, 1)
if case in [3, 4]:
f.x(1)
return f
# first, convert oracle circuit (above) to a single gate for drawing purposes. otherwise, the circuit is too large to display
# blackbox = twobit_function(2).to_gate() # you may edit the number inside "twobit_function()" to select among the four valid functions
# blackbox.label = "$U_f$"
qc.h(0)
qc.barrier()
qc.compose(twobit_function(2), inplace=True)
qc.measure_all()
qc.draw("mpl")
위 Circuit에서 Hadamard Gate "H"는 초기 상태 에 있는 Qubit 0을 중첩 상태 으로 변환합니다. 그런 다음 는 함수 를 평가하고 이를 Qubit 1에 적용합니다.
다음으로 Circuit을 양자 컴퓨터에서 실행할 수 있도록 최적화하고 Transpile해야 합니다:
# 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)
마지막으로, Transpile된 Circuit을 양자 컴퓨터에서 실행하고 결과를 시각화합니다:
# Step 3: Run the job on a real quantum computer
job = sampler.run([qc_isa], shots=1)
# job = sampler_sim.run([qc_isa],shots=1) # uncomment this line to run on simulator instead
res = job.result()
counts = res[0].data.meas.get_counts()
# Step 4: Visualize and analyze results
## Analysis
from qiskit.visualization import plot_histogram
plot_histogram(counts)
위는 결과의 히스토그램입니다. 3단계에서 Circuit을 실행하도록 선택한 shots 수에 따라, 각 shot에서 두 Qubit의 측정된 상태를 나타내는 막대가 하나 또는 두 개 보일 수 있습니다. Qiskit에서는 항상 그렇듯이, 이 노트북에서도 "little endian" 표기법을 사용합니다. 이는 Qubit 0부터 n까지의 상태가 오른쪽에서 왼쪽으로 오름차순으로 작성됨을 의미하며, Qubit 0은 항상 가장 오른쪽에 위치합니다.
따라서 Qubit 0이 중첩 상태에 있었기 때문에, Circuit은 과 모두에 대해 동시에 함수를 평가했습니다 — 고전 컴퓨터는 이를 할 수 없습니다! 하지만 문제는 함수 에 대한 정보를 얻으려 할 때 발생합니다 — Qubit을 측정하면 상태가 붕괴됩니다. "shots = 1"을 선택하여 Circuit을 한 번만 실행하면, 위 히스토그램에서 막대가 하나만 보이고 함수에 대한 정보가 불완전하게 됩니다.
이해도 확인
아래 질문을 읽고 답을 생각해 본 다음, 삼각형을 클릭하여 정답을 확인하세요.
함수 를 알아 내기 위해 위 알고리즘을 몇 번 실행해야 할까요? 이것이 고전적인 경우보다 더 나을까요? 이 문제를 해결하기 위해 고전 컴퓨터와 양자 컴퓨터 중 어떤 것을 선택하시겠습니까?
정답:
측정이 중첩을 붕괴시키고 하나의 값만 반환하기 때문에, 함수의 두 출력 과 을 모두 얻으려면 Circuit을 최소 두 번 실행해야 합니다. 최선의 경우, 이는 처음 두 쿼리에서 과 모두를 계산하는 고전적 경우와 동일한 성능을 냅니다. 하지만 최종 측정이 확률적이기 때문에 처음 두 번 모두 같은 값이 반환될 수 있으며, 그 경우 두 번 이상 실행해야 할 수도 있습니다. 이 경우에는 고전 컴퓨터가 더 낫겠습니다.
따라서 양자 병렬성은 올바른 방식으로 사용될 때 강력할 수 있지만, 양자 컴퓨터가 거대한 고전 병렬 프로세서처럼 작동한다고 말하는 것은 옳지 않습니다. 측정 행위가 양자 상태를 붕괴시키므로, 연산의 단일 출력만 접근할 수 있습니다.
Deutsch의 알고리즘
양자 병렬성만으로는 고전 컴퓨터에 비해 이점을 얻기 어렵지만, 이를 또 다른 양자 현상인 간섭(interference)과 결합하면 속도 향상을 달성할 수 있습니다. "Deutsch의 알고리즘"으로 알려진 이 알고리즘이 바로 그 첫 번째 사례입니다.
문제
문제는 다음과 같았습니다:
입력 비트 와 입력 함수 가 주어졌을 때, 함수가 *균형(balanced)*인지 *상수(constant)*인지 판별하세요. 균형 함수라면 함수의 출력이 절반은 0, 나머지 절반은 1입니다. 상수 함수라면 함수의 출력이 항상 0이거나 항상 1입니다. 단일 비트를 단일 비트로 매핑하는 가능한 네 가지 함수 표를 다시 살펴보세요:
| 0 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 |
첫 번째와 마지막 함수인 와 는 상수 함수이고, 중간의 두 함수인 와 는 균형 함수입니다.
알고리즘
Deutsch가 이 문제에 접근한 방식은 "쿼리 모델(query model)"을 통해서였습니다. 쿼리 모델에서는 입력 함수(위의 )가 "블랙박스(black box)" 안에 들어 있습니다. 블랙박스의 내용에는 직접 접근할 수 없지만, 블랙박스에 쿼리를 하면 함수의 출력을 받을 수 있습니다. 이 정보를 제공하는 것을 "오라클(oracle)"이라고 표현하기도 합니다. 쿼리 모델에 대한 자세한 내용은 Fundamentals of Quantum Algorithms 과정의 Lesson 1: Quantum Query Algorithms을 참고하세요.
쿼리 모델에서 양자 알고리즘이 고전 알고리즘보다 효율적인지 판단하려면, 각각의 경우에 블랙박스에 쿼리해야 하는 횟수를 비교하면 됩니다. 고전적인 경우에는 블랙박스에 담긴 함수가 균형인지 상수인지 알기 위해 과 을 모두 얻으려면 두 번의 쿼리가 필요합니다.
그러나 Deutsch의 양자 알고리즘에서는 단 한 번의 쿼리로 정보를 얻을 방법을 찾아냈습니다! 위의 "양자 병렬성" Circuit에서 한 가지를 수정하여, Qubit 0에만 중첩 상태를 준비하는 대신 두 Qubit 모두에 중첩 상태를 준비했습니다. 그러면 함수의 두 출력 과 이 간섭하여, 둘 다 0이거나 둘 다 1이면(함수가 상수이면) 0을 반환하고, 서로 다르면(함수가 균형이면) 1을 반환합니다. 이 방식으로 Deutsch는 단 한 번의 쿼리로 상수 함수와 균형 함수를 구별할 수 있었습니다.
다음은 Deutsch의 알고리즘의 Circuit 다이어그램입니다:
이 알고리즘이 어떻게 작동하는지 이해하기 위해, 위 다이어그램에 표시된 세 지점에서의 Qubit 양자 상태를 살펴봅시다. 답을 클릭해서 확인하기 전에 직접 상태를 계산해 보세요:
이해도 확인
아래 질문을 읽고 답을 생각한 다음, 삼각형을 클릭해서 해답을 확인하세요.
상태 은 무엇인가요?
답:
Hadamard를 적용하면 상태 은 으로, 상태 은 으로 변환됩니다. 따라서 전체 상태는 다음과 같습니다:
상태 은 무엇인가요?
답:
를 적용하기 전에, 가 무엇을 하는지 기억해 봅시다. 는 Qubit 0의 상태에 따라 Qubit 1의 상태를 변경합니다. 따라서 Qubit 0의 상태를 인수분해하는 것이 합리적입니다: . 그런 다음, 이면 두 항이 같은 방식으로 변환되어 두 항 사이의 상대적 부호가 양수를 유지하지만, 이면 두 번째 항이 첫 번째 항에 비해 음의 부호를 갖게 되어 Qubit 0의 상태가 에서 으로 변합니다. 따라서:
상태 은 무엇인가요?
답:
이제 Qubit 0의 상태는 함수에 따라 또는 중 하나입니다. Hadamard를 적용하면 각각 또는 이 됩니다.
위의 질문들에 대한 답을 살펴보면, 다소 놀라운 일이 일어납니다. 가 Qubit 0의 상태를 명시적으로 변경하지 않음에도 불구하고, Qubit 0의 상태에 따라 Qubit 1을 변경하기 때문에 Qubit 0에 위상 이동(phase shift)이 발생할 수 있습니다. 이를 "위상 역전(phase-kickback)" 현상이라고 하며, Fundamentals of Quantum Algorithms 과정의 Lesson 1: Quantum Query Algorithms에서 더 자세히 다루고 있 습니다.
이 알고리즘이 어떻게 작동하는지 이해했으니, 이제 Qiskit으로 구현해 봅시다.
## Deutsch's algorithm:
## Step 1: Map the problem
# first, convert oracle circuit (above) to a single gate for drawing purposes. otherwise, the circuit is too large to display
blackbox = twobit_function(
3
).to_gate() # you may edit the number (1-4) inside "twobit_function()" to select among the four valid functions
blackbox.label = "$U_f$"
qc_deutsch = QuantumCircuit(2, 1)
qc_deutsch.x(1)
qc_deutsch.h(range(2))
qc_deutsch.barrier()
qc_deutsch.compose(twobit_function(2), inplace=True)
qc_deutsch.barrier()
qc_deutsch.h(0)
qc_deutsch.measure(0, 0)
qc_deutsch.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_deutsch)
# Step 3: Run the job on a real quantum computer
job = sampler.run([qc_isa], shots=1)
# job = sampler_sim.run([qc_isa],shots=1) # uncomment this line to run on simulator instead
res = job.result()
counts = res[0].data.c.get_counts()
# Step 4: Visualize and analyze results
## Analysis
print(counts)
if "1" in counts:
print("balanced")
else:
print("constant")
{'1': 1}
balanced
The Deutsch-Jozsa algorithm
Deutsch의 알고리즘은 양자 컴퓨터가 고전 컴퓨터보다 더 효율적일 수 있다는 것을 보여주는 중요한 첫걸음이었지만, 그 개선은 modest했습니다. 고전적인 경우의 두 번에 비해 단 한 번의 질의만 필요했습니다. 1992년, Deutsch와 그의 동료 Richard Jozsa는 원래의 두-Qubit 알고리즘을 더 많은 Qubit으로 확장했습니다. 문제는 동일하게 유지되었습니다: 함수가 *균형(balanced)*인지 *상수(constant)*인지 판별하는 것입니다. 하지만 이번에는 함수가 개의 비트에서 단일 비트로 대응됩니다. 함수가 0과 1을 동일한 횟수로 반환하면 (균형), 항상 1 또는 항상 0만 반환하면 (상수)입니다.
다음은 이 알고리즘의 Circuit 다이어그램입니다:
이 알고리즘은 Deutsch의 알고리즘과 동일한 방식으로 작동합니다. 위상 반작용(phase-kickback)을 통해 Qubit 0의 상태를 읽어 함수가 상수인지 균형인지 판별합니다. 두-Qubit Deutsch 알고리즘의 경우보다 조금 더 파악하기 어려운데, 상태가 개의 Qubit에 대한 합산을 포함하기 때문입니다. 그 상태를 계산하는 것은 모듈 마지막의 선택적 연습 문제로 남겨두겠습니다. 이 알고리즘은 함수가 상수이면 모두 0인 비트열을 반환하고, 함수가 균형이면 적어도 하나의 1을 포함하는 비트열을 반환합니다.
Qiskit에서 알고리즘이 어떻게 동작하는지 보기 위해, 먼저 오라클을 생성해야 합니다. 오라클은 상수이거나 균형임이 보장된 무작위 함수입니다. 아래 코드는 50%의 확률로 균형 함수를, 50%의 확률로 상수 함수를 생성합니다. 코드를 완전히 이해하지 못해도 괜찮습니다 — 복잡하며 양자 알고리즘을 이해하는 데 반드시 필요한 것은 아닙니다.
from qiskit import QuantumCircuit
import numpy as np
def dj_function(num_qubits):
"""
Create a random Deutsch-Jozsa function.
"""
qc_dj = QuantumCircuit(num_qubits + 1)
if np.random.randint(0, 2):
# Flip output qubits with 50% chance
qc_dj.x(num_qubits)
if np.random.randint(0, 2):
# return constant circuit with 50% chance.
return qc_dj
# If the "if" statement above was "TRUE" then we've returned the constant
# function and the function is complete. If not, we proceed in creating our
# balanced function. Everything below is to produce the balanced function:
# select half of all possible states at random:
on_states = np.random.choice(
range(2**num_qubits), # numbers to sample from
2**num_qubits // 2, # number of samples
replace=False, # makes sure states are only sampled once
)
def add_cx(qc_dj, bit_string):
for qubit, bit in enumerate(reversed(bit_string)):
if bit == "1":
qc_dj.x(qubit)
return qc_dj
for state in on_states:
# qc_dj.barrier() # Barriers are added to help visualize how the functions are created. They can safely be removed.
qc_dj = add_cx(qc_dj, f"{state:0b}")
qc_dj.mcx(list(range(num_qubits)), num_qubits)
qc_dj = add_cx(qc_dj, f"{state:0b}")
# qc_dj.barrier()
return qc_dj
n = 3 # number of input qubits
oracle = dj_function(n)
display(oracle.draw("mpl"))
이것이 오라클 함수이며, 균형이거나 상수입니다. 이 Circuit을 보고 마지막 Qubit의 출력이 처음 개의 Qubit에 입력된 값에 의존하는지 알 수 있나요? 마지막 Qubit의 출력이 처음 개의 Qubit에 의존한다면, 그 의존적 출력이 균형인지 아닌지 알 수 있나요?
이 Circuit을 보면 함수가 균형인지 상수인지 알 수 있습니다. 하지만 이 문제에서 우리는 이 함수를 "블랙박스"로 취급한다는 점을 기억하세요. 박스 안을 들여다보고 Circuit 다이어그램을 볼 수 없습니다. 대신, 박스에 질의해야 합니다.
박스에 질의하기 위해 Deutsch-Jozsa 알고리즘을 사용하여 함수가 상수인지 균형인지 판별합니다:
blackbox = oracle.to_gate()
blackbox.label = "$U_f$"
qc_dj = QuantumCircuit(n + 1, n)
qc_dj.x(n)
qc_dj.h(range(n + 1))
qc_dj.barrier()
qc_dj.compose(blackbox, inplace=True)
qc_dj.barrier()
qc_dj.h(range(n))
qc_dj.measure(range(n), range(n))
qc_dj.decompose().decompose()
qc_dj.draw("mpl")
# Step 1: Map the problem
qc_dj = QuantumCircuit(n + 1, n)
qc_dj.x(n)
qc_dj.h(range(n + 1))
qc_dj.barrier()
qc_dj.compose(oracle, inplace=True)
qc_dj.barrier()
qc_dj.h(range(n))
qc_dj.measure(range(n), range(n))
qc_dj.decompose().decompose()
qc_dj.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_dj)
# Step 3: Run the job on a real quantum computer
job = sampler.run([qc_isa], shots=1)
# job = sampler_sim.run([qc_isa],shots=1) # uncomment this line to run on simulator instead
res = job.result()
counts = res[0].data.c.get_counts()
# Step 4: Visualize and analyze results
## Analysis
print(counts)
if (
"0" * n in counts
): # The D-J algorithm returns all zeroes if the function was constant
print("constant")
else:
print("balanced") # anything other than all zeroes means the function is balanced.
{'110': 1}
balanced
위에서 출력의 첫 번째 줄은 측정 결과의 비트열입니다. 두 번째 줄은 그 비트열이 함수가 균형인지 상수인지를 나타냅니다. 비트열이 모두 0이면 상수이고, 그렇지 않으면 균형입니다. 즉, 위의 양자 Circuit을 단 한 번만 실행하여 함수가 상수인지 균형인지 판별할 수 있습니다!
이해도 확인
아래 질문을 읽고 답을 생각한 후, 삼각형을 클릭하여 정답을 확인하세요.
고전 컴퓨터가 함수가 상수인지 균형인지 100% 확실하게 판별하려면 몇 번의 질의가 필요할까요? 고전적으로는 한 번의 질의로 하나의 비트열에만 함수를 적용할 수 있다는 점을 기억하세요.
답:
확인해야 할 비트열은 가지이며, 최악의 경우 그 중 개를 테스트해야 합니다. 예를 들어 함수가 상수인데 계속 "1"이 출력된다면, 절반 이상의 결과를 확인하기 전까지는 진정 상수인지 확신할 수 없습니다. 그전까지는 균형 함수에서 운 나쁘게 계속 "1"이 나온 것일 수도 있기 때문입니다. 동전을 던져 계속 앞면이 나오는 경우와 같습니다. 가능성은 낮지만 불가능하지는 않습니다.
한 결과(균형 또는 상수)가 다른 결과보다 더 가능성이 높다고 판단될 때까지만 측정한다면 위의 답이 어떻게 달라질까요? 이 경우 몇 번의 질의가 필요할까요?
답:
이 경우, 두 번만 측정하면 됩니다. 두 측정값이 다르면 함수가 균형임을 알 수 있습니다. 두 측정값이 같다면 균형일 수도, 상수일 수도 있습니다. 이 측정 결과로 균형일 확률은 입니다. 이는 1/2보다 작으므로, 이 경우 함수가 상수일 가능성이 더 높습니다.
따라서 Deutsch-Jozsa 알고리즘은 결정론적 고전 알고리즘(100% 확실한 답을 반환하는 알고리즘)에 비해 지수적 속도 향상을 보여주었지만, 확률론적 알고리즘(올바른 답일 가능성이 높은 결과를 반환하는 알고리즘)에 비해서는 유의미한 속도 향상이 없었습니다.
The Bernstein - Vazirani problem
1997년, Ethan Bernstein과 Umesh Vazirani는 Deutsch-Jozsa 알고리즘을 사용하여 Deutsch-Jozsa 문제에 비해 더 구체적이고 제한된 문제를 풀었습니다. D-J의 경우처럼 단순히 두 가지 다른 함수 클래스를 구별하는 것이 아니라, Bernstein과 Vazirani는 Deutsch-Jozsa 알고리즘을 사용하여 함수에 인코딩된 문자열을 실제로 알아냈습니다. 문제는 다음과 같습니다:
함수 은 여전히 비트 문자열을 입력으로 받아 단일 비트를 출력합니다. 그런데 이번에는 함수가 균형이거나 상수라고 보장하는 대신, 함수가 입력 문자열 와 어떤 비밀 비트 문자열 의 내적을 모듈로 2로 취한 값이라고 보장합니다. (이 모듈로 2의 내적을 "이진 내적(binary dot product)"이라고 합니다.) 문제는 비밀 비트 문자열이 무엇인지 알아내는 것입니다.
다시 말하면, 어떤 문자열 에 대해 를 만족하는 블랙박스 함수 가 주어지고, 우리는 그 문자열 를 알고 싶습니다.
D-J 알고리즘이 이 문제를 어떻게 해결하는지 살펴보겠습니다:
- 먼저, 개의 입력 Qubit에 Hadamard Gate를 적용 하고, 출력 Qubit에 NOT Gate와 Hadamard를 적용하여 다음 상태를 만듭니다:
Qubit 1부터 까지의 상태는 모든 개의 -Qubit 기저 상태 에 대한 합으로 더 간단히 쓸 수 있습니다. 이 기저 상태들의 집합을 이라고 합니다. (자세한 내용은 Fundamentals of Quantum Algorithms를 참조하세요.)
- 다음으로, Gate를 Qubit에 적용합니다. 이 Gate는 처음 n개의 Qubit을 입력으로 받고(이제 가능한 모든 n비트 문자열의 균등한 중첩 상태에 있습니다) 출력 Qubit에 함수 를 적용하여, 이 Qubit이 상태 가 되도록 합니다. 위상 반작용 메커니즘 덕분에 이 Qubit의 상태는 변하지 않지만, 입력 Qubit 상태의 일부 항이 마이너스 부호를 얻게 됩니다:
- 이제 Qubit 0부터 까지 다음 Hadamard 집합을 적용합니다. 이 경우 마이너스 부호를 추적하는 것이 까다로울 수 있습니다. 표준 기저 상태 에 있는 개의 Qubit에 Hadamard 층을 적용하면 다음과 같이 쓸 수 있다는 것을 알아두면 도움이 됩니다:
따라서 상태는 다음과 같이 됩니다:
- 다음 단계는 처음 개의 비트를 측정하는 것입니다. 그런데 무엇을 측정하게 될까요? 위의 상태가 로 단순화된다는 것이 밝혀졌습니다. 하지만 이것이 명백하지는 않습니다. 수학적 과정을 따라가고 싶다면 John Watrous의 Fundamentals of Quantum Algorithms 강좌를 참조하세요. 핵심은, 위상 반작용 메커니즘이 입력 Qubit을 상태 로 만든다는 것입니다. 따라서 비밀 문자열 가 무엇인지 알아내려면 그냥 Qubit을 측정하기만 하면 됩니다!
이해도 확인
아래 질문을 읽고 답을 생각한 후, 삼각형을 클릭하여 정답을 확인하세요.
위의 3단계 상태가 인 특수한 경우에 실제로 상태 임을 검증하세요.
답:
두 합산식을 명시적으로 쓰면 네 항을 가진 상태를 얻을 수 있습니다(출력 상태 는 생략합니다):
이면 처음 두 항이 보강 간섭을 하고 마지막 두 항이 상쇄되어 이 됩니다. 이면 마지막 두 항이 보강 간섭을 하고 처음 두 항이 상쇄되어 이 됩니다. 따라서 두 경우 모두 입니다. 이 가장 단순한 경우가 개의 Qubit으로 된 일반적인 경우가 어떻게 작동하는지 직관을 줄 것입니다: 이 아닌 모든 항들이 간섭으로 사라지고 상태만 남습니다.
같은 알고리즘이 어떻게 Bernstein-Vazirani 문제와 Deutsch-Jozsa 문제 둘 다를 풀 수 있을까요? 이를 이해하기 위해, 형태의 Bernstein-Vazirani 함수에 대해 생각해 보세요. 이 함수들이 Deutsch-Jozsa 함수이기도 할까요? 즉, 이 형태의 함수가 Deutsch-Jozsa 문제의 조건 — 함수가 상수 또는 균형이어야 한다는 조건 — 을 만족하는지 판별하세요. 이것이 같은 알고리즘이 두 가지 다른 문제를 풀 수 있다는 것을 이해하는 데 어떻게 도움이 되나요?
답:
형태의 모든 Bernstein-Vazirani 함수는 Deutsch-Jozsa 문제의 조건도 만족합니다: s=00...00이면 함수는 상수입니다(모든 문자열 x에 대해 항상 0을 반 환합니다). s가 다른 어떤 문자열이면 함수는 균형입니다. 따라서 이런 함수에 Deutsch-Jozsa 알고리즘을 적용하면 두 문제를 동시에 풀 수 있습니다! 문자열을 반환하고, 그 문자열이 00...00이면 상수임을 알 수 있으며, 문자열에 적어도 하나의 "1"이 있으면 균형임을 알 수 있습니다.
이 알고리즘이 Bernstein-Vazirani 문제를 성공적으로 해결하는지 실험적으로도 검증할 수 있습니다. 먼저 블랙박스 안에 있는 B-V 함수를 생성합니다:
# Step 1: Map the problem
def bv_function(s):
"""
Create a Bernstein-Vazirani function from a string of 1s and 0s.
"""
qc = QuantumCircuit(len(s) + 1)
for index, bit in enumerate(reversed(s)):
if bit == "1":
qc.cx(index, len(s))
return qc
display(bv_function("1000").draw("mpl"))
string = "1000" # secret string that we'll pretend we don't know or have access to
n = len(string)
qc = QuantumCircuit(n + 1, n)
qc.x(n)
qc.h(range(n + 1))
qc.barrier()
# qc.compose(oracle, inplace = True)
qc.compose(bv_function(string), inplace=True)
qc.barrier()
qc.h(range(n))
qc.measure(range(n), range(n))
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
job = sampler.run([qc_isa], shots=1)
# job = sampler_sim.run([qc_isa],shots=1) # uncomment this line to run on simulator instead
res = job.result()
counts = res[0].data.c.get_counts()
# Step 4: Visualize and analyze results
## Analysis
print(counts)
{'0000': 1}
따라서 단 한 번의 질의만으로 Deutsch-Jozsa 알고리즘을 Bernstein-Vazirani 문제에 적용하면 함수 에 사용된 문자열 를 반환합니다. 고전 알고리즘으로 동일한 문제를 풀려면 번의 질의가 필요합니다.
결론
이 간단한 예제들을 살펴봄으로써, 양자 컴퓨터가 어떻게 중첩, 얽힘, 간섭을 활용하여 고전 컴퓨터보다 강력한 성능을 발휘하는지에 대한 더 나은 직관을 갖게 되셨길 바랍니다.
Deutsch-Jozsa 알고리즘은 고전 알고리즘보다 처음으로 속도 향상을 보여준 알고리즘이기 때문에 역사적으로 매우 중요한 의미를 가집니다. 하지만 이는 다항식적인 속도 향상에 불과했습니다. Deutsch-Jozsa 알고리즘은 이 이야기의 시작에 불과합니다.
Bernstein과 Vazirani는 이 알고리즘을 사용해 자신들의 문제를 해결한 후, 이를 기반으로 재귀적 푸리에 샘플링 문제라는 더 복잡하고 재귀적인 문제를 제안했습니다. 그들의 해법은 고전 알고리즘에 비해 초다항식적인 속도 향상을 제공했습니다. 그리고 Bernstein과 Vazirani보다 앞서, Peter Shor는 이미 양자 컴퓨터가 어떤 고전 알고리즘보다 지수적으로 빠르게 큰 수를 인수분해할 수 있도록 하는 그의 유명한 알고리즘을 개발한 바 있었습니다. 이러한 결과들은 총체적으로 미래 양자 컴퓨터의 흥미로운 가능성을 보여주었고, 물리학자와 공학자들이 이 미래를 현실로 만들기 위해 박차를 가하도록 이끌었습니다.
문제
강사는 노트북이 어떻게 사용되고 있는지에 대한 이 간단한 설문을 작성하면 정답 및 일반 커리큘럼에서의 배치 가이드가 포함된 노트북 버전을 요청할 수 있습니다.
핵심 개념
- Deutsch 및 Deutsch-Jozsa 알고리즘은 양자 병렬성과 간섭을 결합하여 고전 컴퓨터보다 빠르게 문제의 답을 찾습니다.
- 위상 반동 메커니즘은 한 Qubit에 대한 연산이 다른 Qubit의 위상으로 전달되는 직관에 반하는 양자 현상입니다. Deutsch 및 Deutsch-Jozsa 알고리즘은 이 메커니즘을 활용합니다.
- Deutsch-Jozsa 알고리즘은 모든 결정론적 고전 알고리즘에 비해 다항식적인 속도 향상을 제공합니다.
- Deutsch-Jozsa 알고리즘은 함수에 인코딩된 숨겨진 문자열을 찾기 위해 Bernstein-Vazirani 문제라는 다른 문제에 적용될 수 있습니다.
참/거짓
- 참/거짓 Deutsch의 알고리즘은 입력이 단일 Qubit인 Deutsch-Jozsa 알고리즘의 특수한 경우입니다.
- 참/거짓 Deutsch 및 Deutsch-Jozsa 알고리즘은 양자 중첩과 간섭을 사용하여 효율성을 달성합니다.
- 참/거짓 Deutsch-Jozsa 알고리즘은 함수가 상수인지 균형인지 판단하기 위해 여러 번의 함수 평가가 필요합니다.
- 참/거짓 "Bernstein-Vazirani 알고리즘"은 실제로 Deutsch-Jozsa 알고리즘을 다른 문제에 적용한 것입니다.
- 참/거짓 Bernstein-Vazirani 알고리즘은 여러 개의 비밀 문자열을 동시에 찾을 수 있습니다.
단답형
-
고전 알고리즘이 최악의 경우 Deutsch-Jozsa 문제를 풀기 위해 얼마나 걸릴까요?
-
고전 알고리즘이 Bernstein-Vazirani 문제를 풀기 위해 얼마나 걸릴까요? 이 경우 DJ 알고리즘은 어느 정도의 속도 향상을 제공하나요?
-
위상 반동 메커니즘이 무엇인지, 그리고 Deutsch-Jozsa 및 Bernstein-Vazirani 문제를 해결하는 데 어떻게 작동하는지 설명하세요.
도전 문제
- Deutsch-Jozsa 알고리즘: 위에서 Deutsch 알고리즘의 중간 Qubit 상태 과 를 계산하는 질문이 있었음을 상기하세요. 인 특수한 경우에 대해 Deutsch-Jozsa 알고리즘의 중간 -Qubit 상태 과 에 대해 동일하게 수행해 보세요. 그런 다음, 다시 인 특수한 경우에 대해 임을 검증하세요.