Deutsch-Jozsa 알고리즘

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

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

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

이 모듈은 테스트를 거쳐 4초의 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'

아래에서 케이티 박사( McCormick )의 모듈 워크스루를 시청하거나 여기를 클릭하여 YouTube 에서 시청하세요.

소개

1980년대 초, 양자 물리학자와 컴퓨터 과학자들은 양자역학을 활용해 기존 컴퓨터보다 훨씬 더 강력한 계산을 할 수 있다는 막연한 생각을 가지고 있었습니다. 기존 컴퓨터로는 양자 시스템을 시뮬레이션하기 어렵지만, 양자 컴퓨터는 이를 더 효율적으로 수행할 수 있어야 한다는 것이 그들의 추론이었습니다. 양자 컴퓨터가 양자 시스템을 더 효율적으로 시뮬레이션할 수 있다면, 아마도 기존 컴퓨터보다 더 효율적으로 수행할 수 있는 다른 작업도 있을 것입니다.

논리는 타당했지만 세부 사항은 아직 해결해야 할 부분이 남아있었습니다. 이는 1985년 데이비드 도이치가 최초의 "범용 양자 컴퓨터"를 설명하면서 시작되었습니다 이 논문에서 그는 양자 컴퓨터가 기존 컴퓨터보다 더 효율적으로 문제를 해결할 수 있는 최초의 예제 문제를 제시했습니다. 이 첫 번째 장난감 사례는 이제 "도이치의 알고리즘"으로 알려져 있습니다 Deutsch의 알고리즘 개선은 미미했지만, 몇 년 후 Deutsch는 Richard Jozsa와 협력하여 클래식 컴퓨터와 양자 컴퓨터 간의 격차를 더욱 벌렸습니다.

이러한 알고리즘인 Deutsch와 Deutsch-Jozsa 확장은 특별히 유용하지는 않지만 몇 가지 이유로 여전히 매우 중요합니다:

1. 역사적으로 이 알고리즘은 기존 알고리즘을 능가하는 것으로 입증된 최초의 양자 알고리즘 중 일부입니다. 이를 이해하면 시간이 지남에 따라 양자 컴퓨팅에 대한 커뮤니티의 생각이 어떻게 발전해왔는지 이해하는 데 도움이 될 수 있습니다.
2. 양자 컴퓨팅은 놀랍도록 미묘한 질문에 대한 해답의 일부 측면을 이해하는 데 도움이 될 수 있습니다: 양자 컴퓨팅의 힘은 무엇일까요? 때때로 양자 컴퓨터는 기하급수적으로 확장되는 거대한 병렬 프로세서에 비유되기도 합니다. 하지만 이것은 옳지 않습니다. 이 질문에 대한 해답의 일부가 소위 '양자 병렬 처리'에 있지만, 한 번의 실행으로 최대한 많은 정보를 추출하는 것은 미묘한 기술입니다. Deutsch 및 Deutsch-Jozsa 알고리즘은 이를 수행하는 방법을 보여줍니다.

이 모듈에서는 도이치의 알고리즘인 도이치-조자 알고리즘에 대해 알아보고, 양자 컴퓨팅의 힘에 대해 배울 수 있습니다.

양자 병렬 처리와 그 한계

양자 컴퓨팅의 성능 중 일부는 "양자 병렬 처리"에서 파생됩니다 이는 본질적으로 큐비트 입력 상태가 고전적으로 허용되는 여러 상태의 중첩에 있을 수 있기 때문에 동시에 여러 입력에 대한 연산을 수행할 수 있는 기능입니다. 그러나 양자 회로는 한 번에 여러 입력 상태를 평가할 수 있지만, 모든 정보를 한 번에 추출하는 것은 불가능합니다.

여기서 무슨 뜻인지 알아보기 위해 비트( $x$ )와 그 비트에 적용된 함수( $f(x)$ )가 있다고 가정해 보겠습니다. 단일 비트를 다른 단일 비트에 적용하는 이진 함수는 네 가지가 있습니다:

다음 기능(1~4) 중 $f(x)$ 이 어떤 기능인지 알아보고 싶습니다. 일반적으로는 $x=0$ 에 대해 한 번, $x=1$ 에 대해 한 번 함수를 두 번 실행해야 합니다. 하지만 양자 회로를 사용하면 더 잘할 수 있는지 살펴봅시다. 다음 게이트를 통해 기능에 대해 알아볼 수 있습니다:

여기서 $U_f$ 게이트는 $f(x)$, 여기서 $x$ 는 큐비트 0의 상태를 계산하고 이를 큐비트 1에 적용합니다. 따라서 결과 상태인 $|x\rangle|y\oplus f(x)\rangle$ 는 $|y\rangle = |0\rangle$ 일 때 $|x\rangle|f(x)\rangle$ 이 됩니다. 여기에는 함수 $f(x)$ : 큐비트 0은 $x$ 이 무엇인지, 큐비트 1은 $f(x)$ 이 무엇인지 알려주는 모든 정보가 포함되어 있습니다. 따라서 $|x\rangle = \frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$ 을 초기화하면 두 큐비트의 최종 상태는 다음과 같습니다: $|y\rangle|x\rangle = \frac{1}{\sqrt{2}}(|f(0)\rangle|0\rangle+|f(1)\rangle|1\rangle)$. 하지만 이 정보에 어떻게 접근할 수 있을까요?

2.1. Qiskit에서 시도해 보세요:

키스킷을 사용하여 위의 네 가지 함수 중 하나를 무작위로 선택하고 회로를 실행해 보겠습니다. 그런 다음 양자 회로의 측정값을 사용하여 가능한 한 적은 실행으로 함수를 학습하는 것이 과제입니다.

이 첫 번째 실험과 모듈 전체에서 "키스킷 패턴"이라는 양자 컴퓨팅 프레임워크를 사용하여 워크플로우를 다음 단계로 나눌 것입니다:

• 1단계: 기존 입력을 양자 문제에 매핑하기
• 2단계: 양자 실행을 위한 문제 최적화
• 3단계: Qiskit Runtime 프리미티브를 사용하여 실행하기
• 4단계: 후처리 및 고전적 분석

Qiskit Runtime 프리미티브 등 몇 가지 필요한 패키지를 로드하는 것으로 시작하겠습니다. 또한 사용 가능한 양자 컴퓨터 중 가장 사용량이 적은 컴퓨터를 선택합니다.

처음 사용할 때 자격 증명을 저장하는 코드는 아래에 있습니다. 노트북을 공유할 때 실수로 자격 증명이 공유되지 않도록 노트북을 환경에 저장한 후 이 정보를 노트북에서 삭제해야 합니다. 자세한 안내는 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)

Output:

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)

이제 필요한 패키지를 로드했으니 키스킷 패턴 워크플로우를 진행할 수 있습니다. 아래 매핑 단계에서는 먼저 단일 비트를 다른 단일 비트로 가져가는 네 가지 가능한 함수 중 하나를 선택하는 함수를 만듭니다.

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

Output:

위의 회로에서 하다마드 게이트 "H"는 처음에 $|0\rangle$ 상태에 있는 큐비트 0을 중첩 상태 $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$ 로 가져옵니다. 그런 다음 $U_f$ 는 $f(x)$ 함수를 평가하고 이를 큐비트 1에 적용합니다.

다음으로 양자 컴퓨터에서 실행할 회로를 최적화하고 트랜스파일링해야 합니다:

# 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.meas.get_counts()

# Step 4: Visualize and analyze results

## Analysis
from qiskit.visualization import plot_histogram

plot_histogram(counts)

Output:

위는 결과의 히스토그램입니다. 위 3단계에서 회로를 실행하기 위해 선택한 샷 수에 따라 각 샷에서 두 큐비트의 측정된 상태를 나타내는 막대를 하나 또는 두 개 볼 수 있습니다. 키스킷과 이 노트북에서는 항상 그렇듯이, 0에서 n까지의 큐비트 상태를 오른쪽에서 왼쪽으로 오름차순으로 표기하는 "리틀 엔디안" 표기법을 사용하므로, 큐비트 0은 항상 가장 오른쪽에 있습니다.

따라서 큐비트 0이 중첩 상태에 있었기 때문에 이 회로는 기존 컴퓨터로는 할 수 없는 $x=0$ 와 $x=1$ 의 함수를 동시에 평가했습니다! 하지만 문제는 큐비트를 측정할 때 상태를 축소하는 $f(x)$ 함수에 대해 알아보고자 할 때 발생합니다. 회로를 한 번만 실행하기 위해 "샷 = 1"을 선택하면 위의 히스토그램에 막대가 하나만 표시되며, 함수에 대한 정보가 불완전하게 표시됩니다.

이해도 점검

$f(x)$ 함수를 학습하려면 위의 알고리즘을 몇 번 실행해야 하나요? 이것이 고전적인 경우보다 나은가요? 이 문제를 해결하기 위해 클래식 컴퓨터와 양자 컴퓨터 중 어떤 것을 사용하시겠습니까?

• 답변

  측정은 중첩을 축소하고 하나의 값만 반환하므로 $f(0)$ 및 $f(1)$ 함수의 두 출력을 모두 반환하려면 회로를 최소 두 번 실행해야 합니다. 가장 좋은 경우, 처음 두 쿼리에서 $f(0)$ 와 $f(1)$ 를 모두 계산하는 고전적인 경우와 동일한 성능을 발휘합니다. 하지만 최종 측정값은 확률적이기 때문에 처음 두 번은 동일한 $f(x)$ 값을 반환할 수 있으므로 두 번 이상 실행해야 할 가능성이 있습니다. 이 경우에는 차라리 클래식 컴퓨터를 사용하고 싶습니다.

따라서 양자 병렬 처리가 올바른 방식으로 사용될 경우 강력할 수 있지만, 양자 컴퓨터가 거대한 고전적 병렬 프로세서처럼 작동한다고 말하는 것은 옳지 않습니다. 측정 행위는 양자 상태를 붕괴시키기 때문에 우리는 오직 하나의 계산 결과에만 접근할 수 있습니다.

도이치 알고리즘

양자 병렬 처리만으로는 기존 컴퓨터보다 유리하지 않지만, 이를 또 다른 양자 현상인 간섭과 결합하여 속도를 높일 수 있습니다. 현재 '도이치 알고리즘'으로 알려진 알고리즘은 이를 달성하는 알고리즘의 첫 번째 예입니다.

문제점

여기에 문제가 있었습니다:

입력 비트 $x = \{0,1\}$ 와 입력 함수 $f(x) = \{0,1\}$ 가 주어지면 함수가 균형인지 상수인지 결정합니다. 즉, 균형이 맞으면 함수의 출력은 절반은 0이고 나머지 절반은 1입니다. 상수인 경우 함수의 출력은 항상 0이거나 항상 1입니다. 단일 비트를 다른 단일 비트로 변환하는 네 가지 가능한 함수의 표를 떠올려보세요:

첫 번째와 마지막 함수인 $f_1(x)$ 및 $f_4(x)$ 은 상수이고, 중간 두 함수인 $f_2(x)$ 및 $f_3(x)$ 은 균형이 잡혀 있습니다.

알고리즘

Deutsch가 이 문제에 접근한 방식은 "쿼리 모델"이었습니다 쿼리 모델에서 입력 함수(위의 $f_i(x)$ )는 '블랙박스'에 포함되어 있어 그 내용에 직접 액세스할 수는 없지만 블랙박스를 쿼리하면 함수의 출력을 알려줍니다. 우리는 때때로 이 정보를 '오라클'이 제공한다고 말합니다. 쿼리 모델에 대한 자세한 내용은 양자 알고리즘 기초 과정의 수업 1: 양자 쿼리 알고리즘을 참조하세요.

쿼리 모델에서 양자 알고리즘이 기존 알고리즘보다 더 효율적인지 판단하려면 각 경우의 블랙박스 쿼리 수를 간단히 비교하면 됩니다. 고전적인 경우, 블랙박스에 포함된 함수가 균형인지 상수인지 알기 위해서는 $f(0)$ 와 $f(1)$ 를 모두 얻기 위해 두 번 쿼리해야 합니다.

하지만 도이치의 양자 알고리즘에서는 단 한 번의 쿼리로 정보를 얻을 수 있는 방법을 찾아냈습니다! 그는 위의 '양자 병렬성' 회로를 한 번 조정하여 큐비트 0에만 중첩 상태를 준비하는 것이 아니라 두 큐비트 모두에 중첩 상태를 준비했습니다. 그런 다음 함수의 두 출력인 $f(0)$ 및 $f(1)$ 이 서로 간섭하여 둘 다 0이거나 둘 다 1이면 0을 반환하고(함수가 상수), 서로 다르면 1을 반환합니다(함수가 균형 잡힌 경우). 이러한 방식으로 Deutsch는 단일 쿼리로 상수와 균형 함수를 구분할 수 있었습니다.

다음은 Deutsch 알고리즘의 회로도입니다:

이 알고리즘이 어떻게 작동하는지 이해하기 위해 위 다이어그램에 표시된 세 지점에서 큐비트의 양자 상태를 살펴봅시다. 클릭하여 답을 보기 전에 직접 상태를 계산해 보세요:

이해도 점검

상태는 무엇입니까 $|\pi_1\rangle$?

• 답변

  하다마드를 적용하면 상태 $|0\rangle$ 가 $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$ 로, 상태 $|1\rangle$ 가 $\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$ 로 변환됩니다. 따라서 전체 상태가 됩니다: $|\pi_1\rangle = [\frac{|0\rangle-|1\rangle}{\sqrt{2}}][\frac{|0\rangle+|1\rangle}{\sqrt{2}}]$

상태는 무엇입니까 $|\pi_2\rangle$?

• 답변

  적용하기 전에 $U_f$ 의 기능을 기억하세요. 큐비트 0의 상태를 기반으로 큐비트 1의 상태를 변경합니다. 따라서 큐비트 0의 상태를 다음과 같이 인수분해하는 것이 합리적입니다: $|\pi_1\rangle = \frac{1}{2} (|0\rangle-|1\rangle)|0\rangle+\frac{1}{2}(|0\rangle-|1\rangle)|1\rangle$. $f(0)=f(1)$ 이면 두 항은 같은 방식으로 변환되고 두 항 사이의 상대 부호는 양수로 유지되지만 $f(0)\neq f(1)$ 이면 두 번째 항이 첫 번째 항에 대해 마이너스 부호를 갖게 되어 큐비트 0의 상태가 $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$ 에서 $\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$ 으로 변경됩니다:

  $$|\pi_2\rangle = \begin{cases} \pm[\frac{|0\rangle-|1\rangle}{\sqrt{2}}][\frac{|0\rangle+|1\rangle}{\sqrt{2}}] & \text{if} & f(0) = f(1) \\ \pm[\frac{|0\rangle-|1\rangle}{\sqrt{2}}][\frac{|0\rangle-|1\rangle}{\sqrt{2}}] &\text{if} & f(0) \neq f(1) \\ \end{cases}$$

상태는 무엇입니까 $|\pi_3\rangle$?

• 답변

  이제 큐비트 0의 상태는 함수에 따라 $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$ 또는 $\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$ 입니다. 하다마드를 적용하면 각각 $|0\rangle$ 또는 $|1\rangle$ 이 표시됩니다.

  $$|\pi_3\rangle = \begin{cases} \pm[\frac{|0\rangle-|1\rangle}{\sqrt{2}}]|0\rangle & \text{if} & f(0) = f(1) \\ \pm[\frac{|0\rangle-|1\rangle}{\sqrt{2}}]|1\rangle &\text{if} & f(0) \neq f(1) \\ \end{cases}$$

위의 질문에 대한 답변을 살펴보면 조금 놀라운 점이 있습니다. $U_f$ 은 큐비트 0의 상태에 명시적으로 아무것도 하지 않지만, 큐비트 0의 상태를 기반으로 큐비트 1을 변경하기 때문에 큐비트 0의 위상 이동을 유발할 수 있습니다. 이는 "위상 반동" 현상으로 알려져 있으며, 양자 알고리즘 기초 과정의 수업 1: 양자 쿼리 알고리즘 에서 더 자세히 논의됩니다.

이제 이 알고리즘이 어떻게 작동하는지 이해했으니, 키스킷으로 구현해 보겠습니다.

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

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

Output:

{'1': 1}
balanced

Deutsch-Jozsa 알고리즘

도이치의 알고리즘은 양자 컴퓨터가 기존 컴퓨터보다 더 효율적일 수 있다는 것을 입증하는 중요한 첫 단계였지만, 기존 컴퓨터의 경우 두 번의 쿼리가 필요했던 것에 비해 단 한 번의 쿼리가 필요했을 정도로 소폭의 개선에 불과했습니다. 1992년, Deutsch와 그의 동료인 Richard Jozsa는 원래의 2큐비트 알고리즘을 더 많은 큐비트로 확장했습니다. 함수가 균형인지 상수인지 판단하는 문제는 동일하게 유지되었습니다. 하지만 이번에는 이 함수가 $n$ 비트에서 단일 비트로 변경됩니다. 함수가 0과 1을 같은 횟수만큼 반환하거나( 균형 ), 함수가 항상 1 또는 항상 0을 반환합니다( 상수 ).

다음은 알고리즘의 회로도입니다:

이 알고리즘은 도이치의 알고리즘과 동일한 방식으로 작동합니다. 위상 킥백을 통해 큐비트 0의 상태를 읽어 함수가 일정하거나 균형 잡힌지 여부를 판단할 수 있습니다. 2큐비트 도이치 알고리즘의 경우보다 보기가 조금 더 까다로운데, 상태에는 $n$ 큐비트 이상의 합이 포함되므로 이러한 상태를 계산하는 것은 모듈의 마지막에 선택 사항으로 남겨집니다. 알고리즘은 함수가 상수인 경우 0이 모두 포함된 비트스트링을 반환하고, 함수가 균형인 경우 1이 하나 이상 포함된 비트스트링을 반환합니다.

키스킷에서 알고리즘이 어떻게 작동하는지 보려면, 먼저 오라클, 즉 상수 또는 균형이 보장되는 랜덤 함수를 생성해야 합니다. 아래 코드는 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"))

Output:

이것은 오라클 함수이며, 균형이 잡혀 있거나 상수입니다. 마지막 큐비트의 출력이 첫 번째 $n$ 큐비트에 입력된 값에 따라 달라지는지 확인하실 수 있나요? 마지막 큐비트의 출력이 첫 번째 $n$ 큐비트에 의존하는 경우, 그 종속 출력이 균형을 이루는지 아닌지 알 수 있나요?

위의 회로를 보면 함수가 균형을 이루는지 일정한지 알 수 있지만, 이 문제를 해결하기 위해 이 함수를 "블랙박스"로 생각한다는 점을 기억하세요 회로도를 보기 위해 상자를 들여다볼 수는 없습니다. 대신 상자를 쿼리해야 합니다.

상자를 쿼리하기 위해 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")

Output:

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

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_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.

Output:

{'110': 1}
balanced

위 출력의 첫 번째 줄은 측정 결과의 비트 문자열입니다. 두 번째 줄은 비트 문자열이 함수의 균형이 잡혔는지 또는 상수인지 여부를 출력합니다. 비트 문자열에 0이 모두 포함되어 있으면 상수이고, 그렇지 않으면 균형이 잡힌 것입니다. 따라서 위의 양자 회로를 한 번만 실행하면 함수가 일정한지 또는 균형이 잡혀 있는지 확인할 수 있습니다!

이해도 점검

함수가 상수인지 균형인지 100% 확실하게 판단하려면 기존 컴퓨터로 몇 번의 쿼리를 수행해야 할까요? 일반적으로 단일 쿼리는 단일 비트 문자열에만 함수를 적용할 수 있다는 점을 기억하세요.

• 답변

  확인할 수 있는 $2^n$ 가능한 비트 문자열이 있으며, 최악의 경우 이 중 $2^n/2+1$ 을 테스트해야 합니다. 예를 들어 함수가 상수이고 함수의 출력으로 '1'을 계속 측정하는 경우, 결과의 절반 이상을 확인하기 전까지는 함수가 정말 상수인지 확신할 수 없습니다. 그 전에는 밸런스 함수에서 계속 '1'을 측정하는 것이 매우 운이 나빴을 수도 있습니다. 마치 동전을 계속 뒤집으면 매번 앞면이 나오는 것과 같습니다. 가능성은 낮지만 불가능하지는 않습니다.

한 결과(균형 또는 일정)가 다른 결과보다 높을 때까지만 측정해야 한다면 위의 답변은 어떻게 달라질까요? 이 경우 얼마나 많은 쿼리가 필요하나요?

• 답변

  이 경우 두 번 측정하면 됩니다. 두 측정값이 다르면 기능이 균형 잡힌 것입니다. 두 측정값이 같으면 균형이 맞거나 일정할 수 있습니다. 이 측정값 세트와 균형이 맞을 확률은 $\frac{1}{2}\frac{2^n /2 - 1}{2^n-1}$ 입니다. 이 값은 1/2보다 작으므로 이 경우 함수가 일정할 가능성이 더 높습니다.

따라서 Deutsch-Jozsa 알고리즘은 결정론적 알고리즘(100% 확실하게 답을 반환하는 알고리즘)에 비해 기하급수적인 속도 향상을 보여주었지만 확률론적 알고리즘(정답일 가능성이 있는 결과를 반환하는 알고리즘)에 비해서는 큰 속도 향상을 보여주지 못했습니다.

번스타인-바지라니 문제

1997년에 에단 번스타인과 우메시 바지라니는 도이치-조자 알고리즘을 사용하여 도이치-조자 문제보다 더 구체적이고 제한된 문제를 해결했습니다. 번스타인과 바지라니는 D-J 사례에서처럼 단순히 서로 다른 두 종류의 함수를 구별하는 것이 아니라, 실제로 함수에 인코딩된 문자열을 학습하기 위해 Deutsch-Jozsa 알고리즘을 사용했습니다. 여기에 문제가 있습니다:

$f:\{0,1\}^n \rightarrow \{0,1\}$ 함수는 여전히 $n$ -비트 문자열을 받아 단일 비트를 출력합니다. 하지만 이제 함수가 균형 또는 일정하다는 약속 대신 입력 문자열 $x$ 과 일부 비밀 $n$ -비트 문자열 $s$, 모듈로 2 사이의 점 곱이라는 약속을 하게 됩니다. (이 도트 곱 모듈로 2를 '이진 도트 곱'이라고 합니다.) 문제는 $n$ -비트 문자열의 비밀이 무엇인지 알아내는 것입니다.

다른 방식으로 작성하면, 어떤 문자열 $s$ 에 대해 $f(x) = s \cdot x$ 을 만족하는 블랙박스 함수 $f: {0,1}^n \rightarrow {0,1}$ 가 주어지고, 문자열 $s$ 을 학습하고자 합니다.

D-J 알고리즘이 이 문제를 어떻게 해결하는지 살펴보겠습니다:

1. 먼저 $n$ 입력 큐비트에 하다마드 게이트가 적용되고, 출력 큐비트에 NOT 게이트와 하다마드가 적용되어 상태가 만들어집니다:

$2^n$ 큐비트 1부터 $n$ 까지의 상태는 $n$ -큐비트 기저 상태 $|00...00\rangle, |00...01\rangle, |000...11\rangle, ..., |111...11\rangle$ 를 모두 합한 값으로 더 간단하게 나타낼 수 있습니다. 이러한 기저 상태의 집합을 $\Sigma^n$ 이라고 부릅니다. (자세한 내용은 양자 알고리즘의 기초를 참조하세요.)

2. 다음으로 $U_f$ 게이트가 큐비트에 적용됩니다. 이 게이트는 처음 n개의 큐비트를 입력으로 받아(이제 가능한 모든 n비트 문자열이 동일하게 중첩되어 있음) 출력 큐비트에 $f(x)=s \cdot x$ 함수를 적용하여 이 큐비트가 $|- \oplus f(x)\rangle$ 상태가 되도록 합니다. 위상 킥백 메커니즘 덕분에 이 큐비트의 상태는 변하지 않지만 입력 큐비트 상태의 일부 항은 마이너스 기호가 나타납니다:

3. 이제 다음 하다마드 세트는 0부터 $n-1$ 까지의 큐비트에 적용됩니다. 이 경우 마이너스 기호를 추적하는 것은 까다로울 수 있습니다. 표준 기준 상태인 $n$ 큐비트에 하다마드 레이어를 적용하면 $|x\rangle$ 으로 작성할 수 있다는 점을 알아두면 도움이 됩니다:

따라서 상태는 다음과 같습니다:

4. 다음 단계는 첫 번째 $n$ 비트를 측정하는 것입니다. 하지만 무엇을 측정할까요? 위의 상태는 다음과 같이 단순화됩니다: $|\Psi\rangle = |-\rangle \otimes |s\rangle$ 로 단순화되지만 이는 분명하지 않습니다. 수학을 더 자세히 알고 싶으시다면 John Watrous의 양자 알고리즘의 기초 강좌를 참조하세요. 하지만 위상 킥백 메커니즘으로 인해 입력 큐비트가 $|s\rangle$ 상태가 된다는 것이 핵심입니다. 따라서 $s$ 의 비밀 문자열이 무엇인지 알아내려면 큐비트를 측정하기만 하면 됩니다!

이해도 점검

위 3단계의 상태가 $n=1$ 의 특수 케이스에 대해 실제로 $|s\rangle$ 상태인지 확인합니다.

• 답변

  두 합계를 명시적으로 작성하면 네 개의 항이 있는 상태를 얻을 수 있습니다(여기서는 $|-\rangle$ 출력 상태는 생략하겠습니다):

  $$|\Psi\rangle = \frac{1}{2}[|0\rangle + (-1)^s |0\rangle + |1\rangle + (-1)^{(s+1)} |1\rangle]$$

  $s=0$ 이면 처음 두 항이 건설적으로 더하고 마지막 두 항이 취소되어 $|\Psi\rangle = |0\rangle$ 이 됩니다. $s=1$ 이면 마지막 두 항이 건설적으로 더하고 처음 두 항이 취소되어 $|\Psi\rangle = |1\rangle$ 이 됩니다. 따라서 두 경우 모두 $|\Psi\rangle = |s\rangle$ 입니다. 이 가장 간단한 경우를 통해 $n$ 큐비트의 일반적인 경우가 어떻게 작동하는지 이해할 수 있기를 바랍니다: $|s\rangle$ 이 아닌 모든 용어는 간섭하고 $|s\rangle$ 상태만 남습니다.

동일한 알고리즘으로 어떻게 번스타인-바지라니 문제와 도이치-요사 문제를 모두 해결할 수 있을까요? 이를 이해하기 위해 $f(x) = s \cdot x$ 형식의 번스타인-바지라니 함수를 생각해 보세요. 이 함수들도 도이치-조싸 함수일까요? 즉, 이 형식의 함수가 일정하거나 균형이 잡힌다는 도이치-요사 문제 약속을 만족하는지 확인합니다. 동일한 알고리즘으로 두 가지 다른 문제를 해결하는 방법을 이해하는 데 어떻게 도움이 될까요?

• 답변

  $f(x) = s \cdot x$ 형식의 모든 번스타인-바지라니 함수는 도이치-요사 문제 약속도 만족합니다: s=00...00 이면 함수는 상수입니다(모든 문자열 x에 대해 항상 0을 반환합니다). S가 다른 문자열이면 함수가 균형을 이룹니다. 따라서 이러한 함수 중 하나에 Deutsch-Jozsa 알고리즘을 적용하면 두 가지 문제를 동시에 해결할 수 있습니다! 문자열을 반환하며, 문자열이 00...00이면 상수이고, 문자열에 "1"이 하나 이상 있으면 균형이 잡힌 것으로 알 수 있습니다.

또한 이 알고리즘을 실험적으로 테스트하여 번스타인-바지라니 문제를 성공적으로 해결한다는 것을 확인할 수 있습니다. 먼저 블랙박스 내부에 있는 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"))

Output:

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

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

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)

Output:

{'0000': 1}

따라서 단 한 번의 쿼리만으로 Deutsch-Jozsa 알고리즘은 함수에 사용된 $s$ 문자열을 반환합니다( $f(x)=x \cdot s$, 번스타인-바지라니 문제에 적용 시). 기존 알고리즘을 사용하면 같은 문제를 해결하려면 $n$ 쿼리가 필요합니다.

결론

이 간단한 예시를 통해 양자 컴퓨터가 어떻게 중첩, 얽힘, 간섭을 활용하여 기존 컴퓨터보다 강력한 성능을 발휘할 수 있는지 직관적으로 이해할 수 있기를 바랍니다.

Deutsch-Jozsa 알고리즘은 기존 알고리즘보다 속도가 빨라진 것을 최초로 입증했기 때문에 역사적으로 매우 중요하지만, 이는 다항식 속도 향상에 불과했습니다. Deutsch-Jozsa 알고리즘은 이야기의 시작에 불과합니다.

번스타인과 바지라니는 이 알고리즘을 사용해 문제를 해결한 후, 이를 재귀 푸리에 샘플링 문제라는 더 복잡한 재귀적 문제의 기초로 사용했습니다. 이 솔루션은 기존 알고리즘에 비해 초다항식 속도 향상을 제공했습니다. 번스타인과 바지라니보다 앞서 피터 쇼어는 이미 양자 컴퓨터가 기존 알고리즘보다 기하급수적으로 빠르게 큰 수를 인수분해할 수 있는 유명한 알고리즘을 고안해냈습니다. 이러한 결과는 미래 양자 컴퓨터의 흥미로운 가능성을 보여 주었고, 물리학자와 엔지니어들이 이 미래를 현실로 만들기 위해 박차를 가하게 했습니다.

질문

교수자는 노트북이 어떻게 사용되고 있는지에 대한 이 간단한 설문조사를 작성하여 공통 커리큘럼에 배치하는 방법에 대한 안내와 답안지가 포함된 노트북 버전을 요청할 수 있습니다.

핵심 개념

• deutsch 및 Deutsch-Jozsa 알고리즘은 양자 병렬 처리와 간섭을 결합하여 기존 컴퓨터보다 더 빠르게 문제에 대한 답을 찾습니다.
• 위상 킥백 메커니즘은 한 큐비트의 연산을 다른 큐비트의 위상으로 전송하는 반직관적인 양자 현상입니다. Deutsch 및 Deutsch-Jozsa 알고리즘은 이 메커니즘을 활용합니다.
• Deutsch-Jozsa 알고리즘은 결정론적 고전 알고리즘에 비해 다항식 속도 향상을 제공합니다.
• Deutsch-Jozsa 알고리즘을 번스타인-바지라니 문제라는 다른 문제에도 적용하여 함수에 인코딩된 숨겨진 문자열을 찾을 수 있습니다.

true/false

1. T/F Deutsch의 알고리즘은 입력이 단일 큐비트인 Deutsch-Jozsa 알고리즘의 특수한 경우입니다.
2. T/F Deutsch 및 Deutsch-Jozsa 알고리즘은 양자 중첩과 간섭을 사용하여 효율성을 달성합니다.
3. T/F Deutsch-Jozsa 알고리즘은 함수의 상수 또는 균형 여부를 결정하기 위해 여러 번의 함수 평가가 필요합니다.
4. T/F '번스타인-바지라니 알고리즘'은 사실 도이치-요사 알고리즘과 동일하지만, 다른 문제에 적용되었습니다.
5. T/F 번스타인-바지라니 알고리즘은 여러 개의 비밀 문자열을 동시에 찾을 수 있습니다.

단답형 응답

1. 최악의 경우 고전적인 알고리즘으로 도이치-조자 문제를 푸는 데 얼마나 걸릴까요?

2. 기존 알고리즘으로 번스타인-바지라니 문제를 푸는 데 얼마나 걸릴까요? 이 경우 DJ 알고리즘은 어떤 속도 향상을 제공하나요?

3. 위상 킥백 메커니즘과 이 메커니즘이 도이치-요사 및 번스타인-바지라니 문제를 해결하는 방법을 설명하세요.

도전 문제

1. 도이치-조싸 알고리즘: 위에서 도이치 알고리즘의 중간 큐비트 상태 $\pi_1$ 와 $\pi_2$ 를 계산해 달라는 질문이 있었다는 것을 기억하세요. $n=2$ 중간 $n+1$ -쿼비트 상태 $\pi_1$ 와 Deutsch-Jozsa 알고리즘의 $\pi_2$ 에 대해서도 동일하게 수행합니다. 그런 다음 $\pi_3 = |-\rangle \otimes \sum\limits_{x_0...x_n}(-1)^{f(x_0...x_n)}|x_0 ... x_n\rangle$, 다시 특정 사례에 대해 $n=2$ 을 확인합니다.