Deutsch-Jozsaアルゴリズム
この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が最初の「汎用量子コンピューター」を記述したときです。この同じ論文の中で、彼は量子コンピューターが古典コンピューターよりも効率的に解ける最初の問題例を提示しました。この最初のトイ例は現在「Deutschのアルゴリズム」として知られています。Deutschのアルゴリズムによる改善は控えめなものでしたが、数年後にDeutschはRichard Jozsaと共同研究を行い、古典コンピューターと量子コンピューターの差をさらに広げました。
これらのアルゴリズム――Deutschのアルゴリズムと、Deutsch-Jozsaの拡張版――は特別実用的ではありませんが、いくつかの理由から非常に重要です。
- 歴史的に、これらは古典的 な対応アルゴリズムを上回ることが実証された最初の量子アルゴリズムのうちの一部です。これらを理解することで、量子コンピューティングに関するコミュニティの考え方がどのように発展してきたかを理解するのに役立ちます。
- 意外なほど微妙な問いへの回答の一側面を理解するのに役立ちます。その問いとは「量子コンピューティングの力の源泉は何か？」です。量子コンピューターは、指数関数的にスケーリングする巨大な並列プロセッサーに例えられることがあります。しかし、これは正確ではありません。答えの一部は「量子並列性」にありますが、1回の実行でできる限り多くの情報を引き出すことは、微妙な技術です。DeutschとDeutsch-Jozsaのアルゴリズムは、これをどのように実現できるかを示しています。
このモジュールでは、Deutschのアルゴリズム、Deutsch-Jozsaアルゴリズム、そしてそれらが量子コンピューティングの力について何を教えてくれるかを学びます。
量子並列性とその限界
量子コンピューティングの力の一部は「量子並列性」から生まれます。これは本質的に、Qubitの入力状態が複数の古典的に許容された状態の重ね合わせにあり得るため、複数の入力に対して同時に演算を実行できる能力です。ただし、量子回路が複数の入力状態を同時に評価できる一方で、その情報のすべてを一度に取り出すことは不可能です。
ここで言 いたいことを理解するために、ビット と、そのビットに適用される関数 があるとしましょう。1ビットを別の1ビットに対応させる可能な2値関数は4つあります。
| 0 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 |
私たちは、 がこれら4つの関数（1〜4）のどれであるかを知りたいとします。古典的には、関数を2回実行する必要があります―― に対して1回、 に対して1回です。しかし、量子回路でより良い方法ができないか見てみましょう。次のGateを使って関数について学ぶことができます。
ここで、 GateはQubit 0の状態を として を計算し、それをQubit 1に適用します。したがって、 のとき、結果の状態 は単に となります。これには関数 を知るために必要な情報がすべて含まれています。Qubit 0が を、Qubit 1が を伝えます。そこで、 と初期化すると、両Qubitの最終状態は となります。しかし、その情報にどうやってアクセスすればよいのでしょうか？
2.1. Qiskitで試してみましょう
Qiskitを使って、上記の4つの可能な関数からランダムに1つを選び、回路を実行します。そして、できるだけ少ない実行回数で関数を知るために量子回路の測定を使うことが、あなたのタスクです。
この最初の実験とモジュール全体を通じて、「Qiskitパターン」として知られる量子コンピューティングのフレームワークを使用します。このフレームワークはワークフローを以下のステップに分解します。
- ステップ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パターンのワークフローを進めることができます。以下のマッピングステップでは、まず1ビットを別の1ビットに対応させる4つの可能な関数の中から選択する関数を作成します。
# 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")
上記の回路では、アダマールGate「H」がQubit 0（初期状態 ）を重ね合わせ状態 に変換します。その後、 が関数 を評価してQubit 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)
上記は結果のヒストグラムです。ステップ3で回路を実行するために選択したショット数によって、1本または2本のバーが表示されることがあり、各ショットにおける2つのQubitの測定状態を表しています。Qiskitとこのノートブック全体でいつものように、「リトルエンディアン」表記を使用します。つまり、Qubit 0からQubit nまでの状態は右から左へ昇順に記述されるため、Qubit 0は常に最も右に位置します。
Qubit 0が重ね合わせ状態にあったため、回路は と の両方に対して同時に関数を評価しま した――これは古典コンピューターにはできないことです！しかし、関数 について知りたいとき、問題が生じます。Qubitを測定すると、それらの状態が崩壊します。回路を1回だけ実行するために「shots = 1」を選択すると、ヒストグラムには1本のバーしか表示されず、関数に関する情報は不完全になります。
理解度チェック
以下の問いを読み、答えを考えてから、三角形をクリックして解答を確認してください。
関数 を知るために、上記のアルゴリズムを何回実行する必要がありますか？これは古典的な場合と比べて優れていますか？この問題を解くには古典コンピューターと量子コンピューターのどちらを使いたいですか？
解答：
測定によって重ね合わせが崩壊し、1つの値しか返さないため、関数の両方の出力 と を得るには回路を少なくとも2回実行する必要があります。最良の場合でも、最初の2回のクエリで と の両方を計算する古典的な場合と同等のパフォーマンスです。しかし、最終的な測定は確率的であり、最初の2回で同じ の値が返される可能性があるため、2回以上実行する必要があるかもしれません。この場合は古典コンピューターの方が望ましいです。
つまり、量子並列性は正しい方法で使えば強力ですが 、量子コンピューターがまるで巨大な古典的並列プロセッサーのように機能するというのは正確ではありません。測定という行為によって量子状態が崩壊するため、計算の出力を一度にアクセスできるのは常に1つだけです。
Deutschのアルゴリズム
量子並列性だけでは古典コンピューターに対する優位性は得られませんが、これを別の量子現象である干渉と組み合わせることで、高速化を実現できます。「Deutschのアルゴリズム」として知られるアルゴリズムは、これを実現した最初のアルゴリズムの例です。
問題の設定
問題はこうです。
入力ビット と入力関数 が与えられたとき、関数がバランス型か定数型かを判定してください。バランス型であれば、関数の出力は半分の場合に0、残り半分の場合に1となります。定数型であれば、関数の出力は常に0か常に1のどちらかです。1ビットを別の1ビットに対応させる4つの可能な関数の表を思い出してください。
| 0 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 |
最初と最後の関数 と は定数型で、中間の2つの関数 と はバランス型です。
アルゴリズム
Deutschがこの問題にアプローチした方法は「クエリモデル」を通じてでした。クエリモデルでは、入力関数（上記の ）が「ブラックボックス」に含まれています――その内容に直接アクセスすることはできませんが、ブラックボックスに問い合わせれば関数の出力を得ることができます。この情報を提供するものを「オラクル」と呼ぶこともあります。クエリモデルの詳細については、Fundamentals of Quantum Algorithmsコースのレッスン1：量子クエリアルゴリズムを参照してください。
クエリモデルにおいて量子アルゴリズムが古典アルゴリズムよりも効率的かどうかを判断するには、各場合でブラックボックスに必要なクエリ数を比較するだけです。古典的な場合、ブラックボックスに含まれる関数がバランス型か定数型かを知るには、 と の両方を得るためにボックスを2回クエリする必要があります。
しかし、Deutschの量子アルゴリズムでは、たった1回のクエリで情報を得る方法を見つけました！彼は上記の「量子並列性」回路に1つの調整を加え、Qubit 0だけでなく両方のQubitに重ね合わせ状態を準備しました。すると、関数の2つの出力 と が干渉し、両方が0または両方が1（関数が定数型）の場合は0を返し、異なる場合（関数がバランス型）は1を返します。このようにして、Deutschは1回のクエリで定数型とバランス型の関数を区別できるようになりました。
以下はDeutschのアルゴリズムのCircuit図です。
このアルゴリズムがどのように機能するかを理解するために、上図で示された3つのポイントでのQubitの量子状態を見てみましょう。解答を見る前に、自分で状態を導き出してみてください。
理解度チェック
以下の問いを読み、答えを考えてから、三角形をクリックして解答を確認してください。
状態 は何ですか？
解答：
アダマール変換を適用すると、状態 は に、状態 は に変換されます。したがって、全体の状態は次のようになります。
状態 は何ですか？
解答：
を適用する前に、それが何をするかを思い出しましょう。Qubit 0の状態に基づいてQubit 1の状態を変化させます。そこで、Qubit 0の状態を因数分解することが理にかなっています。。そして、 であれば、2つの項は同じように変換され、2つの項の間の相対符号は正のままですが、 であれば、2番目の項が最初の項に対してマイナス符号を持つようになり、Qubit 0の状態が から に変化します。したがって：
状態 は何ですか？
解答：
今、Qubit 0の状態は、関数に応じて または のどちらかです。アダマール変換を適用すると、それぞれ または が得られます。
上記の問いへの解答を見ると、少し驚くべきことが起きていることに気づきます。 はQubit 0の状態に対して明示的には何もしていないにもかかわらず、Qubit 0の状態に基づいてQubit 1を変化させるため、Qubit 0に位相シフトが生じる可能性があります。これは「位相キックバック」現象として知られており、Fundamentals of Quantum Algorithmsコースのレッスン1：量子クエリアルゴリズムでより詳しく説明されています。
アルゴリズムの仕組みを理解したところで、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
Deutsch-Jozsaアルゴリズム
Deutschのアルゴリズムは、量子コンピューターが古典コンピューターよりも効率的になり得ることを示す重要な第一歩でしたが、それはわずかな改 善にすぎませんでした。古典的な場合の2クエリに対し、1クエリのみで済みました。1992年に、Deutschとその同僚Richard Jozsaは、元の2Qubitアルゴリズムをより多くのQubitに拡張しました。問題は同じです。関数がバランス型か定数型かを判定することです。しかし今回は、関数は ビットから1ビットへの対応です。関数が0と1を同数回返す場合（バランス型）、または常に1か常に0を返す場合（定数型）です。
以下はアルゴリズムのCircuit図です。
このアルゴリズムはDeutschのアルゴリズムと同じ方法で機能します。位相キックバックにより、Qubit 0の状態を読み出して関数が定数型かバランス型かを判定できます。2QubitのDeutschのアルゴリズムの場合よりも少し複雑です。状態には 個のQubitにわたる和が含まれるため、それらの状態の導出はモジュールの最後のオプション演習として残しておきます。アルゴリズムは、関数が定数型であればすべて0のビット列を返し、バランス型であれば少なくとも1つの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"))
これがオラクル関数で、バランス型か定数型かのどちらかです。最後のQubitの出力が最初の 個のQubitに入力された値に依存しているかどうか、見ただけでわかりますか？最後のQubitの出力が最初の 個のQubitに依存している場合、その依存する出力がバランス型かどうかわかりますか？
上記の回路を見れば関数がバランス型か定数型かを判断できますが、この問題では、この関数を「ブラックボックス」として扱うことに注意してください。ボックスの中を覗いて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
上記では、出力の1行目が測定結果のビット列です。2行目は、そのビット列が関数がバランス型か定数型かを示しているかどうかを出力します。ビット列がすべて0であれば定数型、そうでなければバランス型です。つまり、上記の量子Circuit를1回実行するだけで、関数が定数型かバランス型かを判定できます！
理解度チェック
以下の質問を読み、答えを考えてから、三角形をクリックして解答を確認してください。
古典コンピュータが、ある関数が定数型かバランス型かを100%の確実性で判断するには、何回のクエリが必要でしょうか？古典的には、1回のクエリで関数を適用できるのは1つのビット列のみであることを思い出してください。
解答：
確認可能なビット列は 通りあり、最悪の場合、そのうち 個を調べる必要があります。例えば、関数が定数型であっても、出力として「1」を測定し 続けた場合、結果の半数以上を確認するまで、本当に定数型であると断言することはできません。それ以前では、バランス型の関数でたまたま「1」を測定し続けていた可能性が否定できないからです。コインを何度も投げるたびに表が出るのに似ており、可能性は低いものの、不可能ではありません。
一方の結果（バランス型または定数型）の方が他方よりも可能性が高くなるまで測定するだけでよい場合、上記の答えはどう変わるでしょうか？その場合、何回のクエリが必要になりますか？
解答：
この場合、2回測定するだけで済みます。2回の測定結果が異なれば、関数がバランス型であることがわかります。2回の測定結果が同じであれば、バランス型の場合も定数型の場合もありえます。この測定セットでバランス型である確率は です。これは1/2未満なので、この場合は定数型である可能性の方が高いといえます。
つまり、Deutsch-Jozsaアルゴリズムは決定論的な古典アルゴリズム（100%の確実性で答えを返すもの）に対して指数的な高速化を実証しましたが、確率論的アルゴリズム（正しい答えである可能性が高い結果を返すもの）に対しては大きな高速化をもたらしませんでした。
Bernstein-Vazirani問題
1997年、Ethan BernsteinとUmesh Vaziraniは、Deutsch-JozsaアルゴリズムをD-J問題と比べてより具体的で制限された問題の解法に応用しました。D-Jの場合のように2つの異なる関数クラスを単に区別しようとするのではなく、BernsteinとVaziraniはDeutsch-Jozsaアルゴリズムを使って関数の中にエンコードされた文字列を実際に学習しました。問題の内容は次の通りです：
関数 は引き続き ビットの文字列を受け取り、1ビットを出力します。しかし今回は、関数がバランス型か定数型であるという約束の代わりに、関数は入力文字列 と何らかの秘密の ビット文字列 との内積を2で割った余り（mod 2）であるという約束がなされています。（このmod 2の内積は「二値内積」と呼ばれます。）問題は、秘密の ビット文字列が何であるかを突き止めることです。
別の言い方をすると、ある文字列 に対して を満たすブラックボックス関数 が与えられており、文字列 を求めたいということです。
D-Jアルゴリズムがこの問題をどのように解くか見ていきましょう：
- まず、 個の入力Qubitにアダマールゲートが適用され、出力QubitにはNOTゲートとアダマールゲートが適用されて、次の状態になります：
Qubit 1から までの状態は、 個すべての -Qubit基底状態 の和として、より簡潔に書くことができます。これらの基底状態の集合を と呼びます。（詳細は量子アルゴリズムの基礎を参照してください。）
- 次に、 ゲートがQubitに適用されます。このゲートは最初の 個のQubit（現在はすべての可能な ビット文字列の等しい重ね合わせにある）を入力として受け取り、関数 を出力Qubitに適用することで、このQubitが の状態になります。位相キックバックの仕組みにより、このQubitの状態は変化しませんが、入力Qubitの状態の一部の項にマイナス符号が付きます：
- 次に、Qubit 0から に対して次のアダマールゲートが適用されます。この場合、マイナス符号を追跡するのは難しい場合があります。 個のQubitに対してアダマール層を適用した場合、標準基底状態 に対する結果は次のように書けることを知っておくと役立ちます：
したがって、状態は次のようになります：
- 次のステップは最初の ビットを測定することです。しかし、何を測定することになるのでしょうか？実は上記の状態は に簡略化されますが、それは一見明らかではありません。数学的な計算を追いたい場合は、John Watrousの量子アルゴリズムの基礎コースをご覧ください。重要な点は、位相キックバックの仕組みにより入力Qubitが状態 になるということです。つまり、秘密文字列 が何であるかを知るには、単純にQubitを測定するだけでよいのです！
理解度チェック
以下の質問を読み、答えを考えてから、三角形をクリッ クして解答を確認してください。
の特別なケースについて、上記のステップ3の状態が確かに状態 であることを確認してください。
解答：
2つの和を明示的に展開すると、4つの項を持つ状態が得られます（出力状態 は省略します）：
の場合、最初の2項は建設的に加算され、最後の2項は打ち消し合い、 が残ります。 の場合、最後の2項は建設的に加算され、最初の2項は打ち消し合い、 が残ります。したがって、いずれの場合も となります。この最も単純なケースが、 Qubitの一般的なケースでどのように機能するかの直感を与えてくれることを願っています： でないすべての項が干渉によって消え去り、状態 だけが残ります。
同じアルゴリズムがどのようにBernstein-VaziraniとDeutsch-Jozsaの両方の問題を解くことができるのでしょうか？これを理解するために、 の形のBernstein-Vazirani関数について考えてください。これ らの関数はDeutsch-Jozsa関数でもあるでしょうか？つまり、この形の関数がDeutsch-Jozsa問題の約束（定数型かバランス型のいずれかである）を満たすかどうかを判断してください。これにより、同じアルゴリズムが2つの異なる問題を解く仕組みをどう理解できるでしょうか？
解答：
の形のすべてのBernstein-Vazirani関数は、Deutsch-Jozsa問題の約束も満たします： の場合、関数は定数型（すべての文字列 に対して常に0を返す）です。 が他の任意の文字列の場合、関数はバランス型です。したがって、これらの関数の1つにDeutsch-Jozsaアルゴリズムを適用すると、両方の問題を同時に解くことができます！文字列が返され、その文字列が であれば定数型であることがわかり、文字列に少なくとも1つの「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}
このように、たった1回のクエリで、Deutsch-Jozsaアルゴリズムは Bernstein-Vazirani 問題に適用した場合、関数 に使われた文字列 を返します。古典的なアルゴリズムでは、同じ問題を解くために 回のクエリが必要になります。
まとめ
これらのシンプルな例を検討することで、量子コンピュータが重ね合わせ、エンタングルメント、干渉をどのように活用して古典コンピュータに対する優位性を実現しているかについて、より深い直感を得ていただけたことを願っています。
Deutsch-Jozsaアルゴリズムは、古典アルゴリズムに対して何らかの高速化を実証した最初のアルゴリズムとして歴史的に非常に重要ですが、それは多項式的な高速化に過ぎませんでした。Deutsch-Jozsaアルゴリズムは、物語の始まりに過ぎません。
BernsteinとVaziraniは自分たちの問題を解くためにこのアルゴリズムを使った後、これを基盤として再帰的フーリエサンプリング問題と呼ばれるより複雑な再帰的問題に取り組みました。彼らの解法は古典アルゴリズムに対して超多項式的な高速化をもたらしました。そしてBernsteinとVaziraniより前に、Peter Shorはすでに量子コンピュータが任意の古典アルゴリズムよりも指数的に速く大きな数を因数分解できる画期的なアルゴリズムを考案していました。これらの成果は総合して、将来の量子コンピュータの exciting な可能性を示し、物理学者やエンジニアがこの未来を現実にするよう駆り立てました。
問題
インストラクターは、これらのノートブックの解答キー付きバージョンおよび一般的なカリキュラムへの配置に関するガイダンスを、ノートブックの使用方法に関するこの簡単なアンケートに回答することでリクエストでき ます。
重要概念
- DeutschおよびDeutsch-Jozsaアルゴリズムは、量子並列性と干渉を組み合わせて、古典コンピュータよりも速く問題の答えを見つけます。
- 位相キックバックの仕組みは、あるQubitに対する操作を別のQubitの位相に転送する直感に反する量子現象です。DeutschおよびDeutsch-Jozsaアルゴリズムはこの仕組みを活用しています。
- Deutsch-Jozsaアルゴリズムは、任意の決定論的な古典アルゴリズムに対して多項式的な高速化を提供します。
- Deutsch-Jozsaアルゴリズムは、Bernstein-Vazirani問題と呼ばれる別の問題に適用して、関数にエンコードされた隠れた文字列を見つけることができます。
正誤問題
- 正/誤 Deutschのアルゴリズムは、入力が1つの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状態 および を計算してください。次に、再び の特定のケースについて、 が成立することを確認してください。