Deutsch-Jozsaアルゴリズム

このQiskit in Classroomsモジュールでは、以下のパッケージがインストールされた Python 環境が必要です：

qiskit v2.1.0 または新しい
qiskit-ibm-runtime v0.40.1 または新しい
qiskit-aer v0.17.0 または新しい
qiskit.visualization
numpy
pylatexenc

上記のパッケージをセットアップしてインストールするには、 Qiskitのインストールガイドをご覧ください。実際の量子コンピュータでジョブを実行するには、 IBM Quantum® のアカウントを設定する必要があります。 IBM Cloud アカウントの設定ガイドの手順に従ってください。

このモジュールはテストされ、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-Jozsaの拡張）は、特に有用というわけではないが、それでもいくつかの理由から本当に重要なものである：

歴史的に見ても、量子アルゴリズムが古典アルゴリズムに勝ることが実証された最初の例である。それらを理解することで、量子コンピューティングに関するコミュニティの考え方がどのように進化してきたかを理解することができる。
驚くほど微妙な疑問に対する答えの一端を理解するのに役立つだろう：量子コンピュータのパワーの源は何か？量子コンピューターは、指数関数的にスケーリングする巨大な並列プロセッサーと比較されることもある。でも、これはちょっと違う。この疑問に対する答えの一端は、いわゆる「量子並列性」にあるが、1回の実行で可能な限り多くの情報を引き出すことは、微妙な技術である。 DeutschとDeutsch-Jozsaアルゴリズムは、これがどのようにできるかを示している。

このモジュールでは、Deutschのアルゴリズム、Deutsch-Jozsaアルゴリズム、そしてそれらが量子コンピューティングの力について教えてくれるものについて学ぶ。

量子並列処理とその限界

量子コンピューティングのパワーの一部は「量子並列性」に由来するこれは、量子ビットの入力状態が古典的に許容される複数の状態の重ね合わせになり得るため、本質的に複数の入力に対して同時に演算を実行する能力である。しかし、量子回路は一度に複数の入力状態を評価できるかもしれないが、一度にすべての情報を抽出することは不可能である。

ここで私が言いたいことを理解するために、あるビット、 $x$ と、そのビットに適用される関数、 $f(x)$ があるとしよう。ビットを別のビットに変換する2進関数は4つある：

$x$	$f_1(x)$	$f_2(x)$	$f_3(x)$	$f_4(x)$
0	0	0	1	1
1	0	1	0	1

$f(x)$ がどの機能（1-4）なのかを調べたい。古典的には、この関数を2回実行する必要がある。1回は $x=0$ 、もう1回は $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)$ を知るために必要なすべての情報を含んでいる。qubit 0は $x$ が何であるかを教えてくれ、qubit 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で試してみてください：

Qiskitを使って、上記の4つの可能な機能の中からランダムに1つを選び、回路を走らせる。あなたの仕事は、量子回路の測定値を用いて、できるだけ少ない回数で関数を学習することです。

この最初の実験とモジュール全体を通して、私たちは「Qiskitパターン」として知られる量子コンピューティングのフレームワークを使用する：

ステップ1：古典的入力を量子問題にマップする
ステップ2：量子実行のための問題の最適化
ステップ 3: IBM Quantum プリミティブを使用して実行する
ステップ4：後処理と古典的分析

まずは、 IBM Quantum のプリミティブを含む、必要なパッケージをいくつか読み込んでみましょう。また、利用可能な量子コンピュータの中から、稼働率が最も低いものを選定します。

初回使用時に認証情報を保存するためのコードが以下にあります。ノートブックを自分の環境に保存した後、必ずこの情報をノートブックから削除してください。そうすれば、ノートブックを共有するときにあなたの認証情報が誤って共有されることはありません。詳しいガイダンスについては、 IBM Cloud アカウントの設定および信頼できない環境でのサービスの初期化を参照してください。

# Load IBM Quantum Compute 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)

必要なパッケージをロードしたので、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

# you may edit the number inside "twobit_function()" to select among the four valid functions:
# blackbox = twobit_function(2).to_gate()

# 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で回路を実行するために選択したショットの数に応じて、各ショットで2つの量子ビットの測定された状態を表す1本または2本のバーを見ることができます。つまり、量子ビット0からnの状態は右から左の昇順で書かれ、量子ビット0は常に最も右にある。

つまり、量子ビット0は重ね合わせ状態にあったため、回路は $x=0$ と $x=1$ の両方の関数を同時に評価した！しかし、 $f(x)$ 。量子ビットを測定すると、その状態が崩れてしまうのだ。もし、"shots = 1 "を選択して回路を一度だけ実行した場合、上のヒストグラムにはバーが1本しか表示されず、関数に関する情報は不完全なものとなる。

理解度チェック

関数 $f(x)$ を学習するために、上記のアルゴリズムを何回実行しなければならないか？これは古典的な場合よりも良いのでしょうか？この問題を解決するのに、古典コンピュータと量子コンピュータのどちらがいいだろうか？

測定は重ね合わせを崩して1つの値しか返さないので、関数 $f(0)$ と $f(1)$ の両方の出力を返すために、回路を少なくとも 2回実行する必要がある。最良の場合、これは最初の2回のクエリで $f(0)$ と $f(1)$ の両方を計算する古典的なケースと同じようにうまくいきます。しかし、最終的な測定は確率的なものであり、最初の2回は同じ $f(x)$ 値を返すかもしれないので、2回以上実行する必要がある可能性がある。この場合、クラシカルなコンピューターの方がいい。

つまり、量子並列性は適切な使い方をすれば強力な力を発揮するが、量子コンピューターが巨大な古典的並列プロセッサーのように動作するというのは正しくないということだ。測定という行為は量子状態を崩壊させるので、私たちは計算の単一の出力にしかアクセスできない。

ドイッチュのアルゴリズム

量子並列性だけでは古典的なコンピューターに対して優位に立てないが、干渉という別の量子現象と組み合わせることで高速化を実現できる。現在「ドイッチュのアルゴリズム」として知られるアルゴリズムは、これを実現するアルゴリズムの最初の例である。

問題

問題はここからだった：

入力ビット、 $x = \{0,1\}$ 、および入力関数、 $f(x) = \{0,1\}$ が与えられたとき、関数が平衡か 定数かを判断する。つまり、バランスが取れていれば、関数の出力は半分の時間が0、残りの半分の時間が1になる。定数であれば、関数の出力は常に0か常に1のどちらかである。 1ビットを別の1ビットに変換する4つの関数の表を思い出してほしい：

$x$	$f_1(x)$	$f_2(x)$	$f_3(x)$	$f_4(x)$
0	0	0	1	1
1	0	1	0	1

最初と最後の関数、 $f_1(x)$ と $f_4(x)$ は一定で、真ん中の2つの関数、 $f_2(x)$ と $f_3(x)$ はバランスが取れている。

アルゴリズム

ドイッチュがこの問題に取り組んだ方法は、"クエリーモデル "だったクエリーモデルでは、入力関数（上記の $f_i(x)$ ）は "ブラックボックス "の中に入っている。私たちはその中身に直接アクセスすることはできないが、ブラックボックスにクエリーすれば関数の出力を教えてくれる。オラクル」がこの情報を提供すると言うこともある。クエリモデルの詳細については、「量子アルゴリズムの基礎」コースのレッスン 1「量子クエリアルゴリズム」を参照してください。

問い合わせモデルにおいて、量子アルゴリズムが古典アルゴリズムよりも効率的かどうかを判断するには、それぞれのケースでブラックボックスに問い合わせる回数を単純に比較すればよい。古典的なケースでは、ブラックボックスに含まれる関数が釣り合い型か定数型かを知るためには、 $f(0)$ と $f(1)$ の両方を得るために2回問い合わせる必要がある。

しかし、ドイッチュの量子アルゴリズムでは、たった1回の問い合わせで情報を得る方法を発見した！彼は上記の "量子並列 "回路を1つ調整し、量子ビット0だけでなく、 両方の量子ビットに重ね合わせ状態を用意した。そして、関数の2つの出力、 $f(0)$ と $f(1)$ は、両方が0か両方が1の場合は0を返し（この関数は一定）、異なる場合は1を返す（この関数はバランスが取れている）ように干渉した。こうすることで、ドイッチュは1回のクエリーで定数と釣り合いの取れた関数を区別できるようになった。

これがドイッチュのアルゴリズムの回路図である：

このアルゴリズムがどのように機能するかを理解するために、上の図に記した3つの点における量子ビットの量子状態を見てみよう。クリックして答えを見る前に、自分で州を考えてみてください：

理解度チェック

$|\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)$ の場合、2つの項は同じように変換され、2つの項間の相対符号は正のままですが、 $f(0)\neq f(1)$ の場合、第2項は第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: 量子クエリアルゴリズム」で詳しく説明されています。

このアルゴリズムの仕組みを理解したところで、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
    # you may edit the number (1-4) inside "twobit_function()" to select among the four valid functions
).to_gate()
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年、ドイチュと彼の同僚であるリチャード・ヨッツァは、オリジナルの2量子ビット・アルゴリズムをさらに多くの量子ビットに拡張した。ある関数が釣り合っているか、 定数であるかを判断する問題である。しかし今回は、 $n$ ビットからシングルビットになった。関数が0と1を同じ回数だけ返す（ 釣り合いが取れている）か、関数が常に1か常に0を返す（一定である）かのどちらかである。

これがアルゴリズムの回路図である：

このアルゴリズムは、ドイチュのアルゴリズムと同じように機能する。位相キックバックにより、量子ビット0の状態を読み出して、関数が一定か平衡かを判断することができる。 2量子ビットのドイチュのアルゴリズムの場合よりも、状態が $n$ 量子ビットの和を含むので、見るのは少し難しい。このアルゴリズムは、関数が定数であればすべて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"))

Output:

これはオラクル関数であり、バランスが取れているか、一定しているかのどちらかである。最後の量子ビットの出力が、最初の $n$ 最後のqubitの出力が最初の $n$ qubitに依存する場合、その依存する出力がバランスしているかどうかわかりますか？

上の回路を見れば、この関数が釣り合っているのか、一定なのかがわかるが、この問題のために、この関数を "ブラックボックス "と考えることを忘れないでほしい回路図を見るために箱の中を覗くことはできない。その代わりに、ボックスに問い合わせる必要がある。

ボックスに問い合わせるには、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

上記、出力の最初の行は、測定結果のビット列である。 2行目は、そのビット列が、関数が釣り合い型であることを意味するのか、定数型であることを意味するのかを出力する。ビット列がすべてゼロを含んでいれば定数であり、そうでなければバランスしている。つまり、上記の量子回路を1回走らせるだけで、関数が一定か均衡かを判断することができる！

理解度チェック

ある関数が定数か釣り合い型かを100％確実に決定するために、古典的なコンピューターは何回クエリーを繰り返せばいいのだろう？覚えておいてほしいのは、古典的には、単一のクエリでは単一のビット文字列にしか関数を適用できないということだ。

チェックするビット列は $2^n$ 、最悪の場合、 $2^n/2+1$ 。例えば、関数が定数で、関数の出力として "1 "を計測し続けたとしたら、結果の半分以上をチェックするまで、本当に定数であるかどうかを確信することはできない。それ以前は、バランス関数で "1 "を計測し続けるのは非常に不運なことだったかもしれない。コインを何度もひっくり返して、毎回表が出るようなものだ。可能性は低いが、不可能ではない。

一方の結果（均衡か一定か）が他方より可能性が高くなるまで測定しなければならないとしたら、上記の答えはどう変わるだろうか？この場合、何回のクエリーが必要ですか？

この場合、2回測ればいい。 2つの測定値が異なれば、その関数がバランスしていることがわかる。もし2つの測定値が同じであれば、バランスが取れている可能性もあるし、一定している可能性もある。この一連の測定で釣り合う確率は、 $\frac{1}{2}\frac{2^n /2 - 1}{2^n-1}$ 。これは1/2より小さいので、この場合は関数が一定である可能性が高い。

つまり、Deutsch-Jozsaアルゴリズムは、 決定論的な古典的アルゴリズム（100％確実に答えを返すもの）に対して指数関数的なスピードアップを示したが、 確率論的アルゴリズム（正解である可能性が高い結果を返すもの）に対しては大きなスピードアップは見られなかった。

バーンスタイン・ヴァジラニ問題

1997年、Ethan BernsteinとUmesh Vaziraniは、Deutsch-Jozsa問題と比較して、より具体的で限定された問題を解くためにDeutsch-Jozsaアルゴリズムを使用した。 BernsteinとVaziraniは、D-Jのケースのように単に2つの異なるクラスの関数を区別しようとするのではなく、Deutsch-Jozsaアルゴリズムを使って、関数にエンコードされた文字列を実際に学習した。問題はここからだ：

関数 $f:\{0,1\}^n \rightarrow \{0,1\}$ は、 $n$ ビットの文字列を受け取り、1ビットを出力する。しかし今、関数が釣り合うか定数であることを約束する代わりに、関数は入力文字列 $x$ と、ある秘密の $n$ -ビット文字列 $s$ 、2のモジュロとの間のドット積であることを約束している。 (この2モジュロのドット積は「2進ドット積」と呼ばれる）問題は、秘密の $n$ -bit文字列が何であるかを突き止めることだ。

別の言い方をすれば、ある文字列 $s$ に対して $f(x) = s \cdot x$ を満たすブラックボックス関数 $f: {0,1}^n \rightarrow {0,1}$ が与えられ、その文字列 $s$ を学習したいとする。

D-Jアルゴリズムがこの問題をどのように解決するか見てみよう：

まず、ハダマードゲートが $n$ 入力量子ビットに適用され、NOTゲートとハダマードが出力量子ビットに適用され、状態が作られる：

|\Psi\rangle = |-\rangle_{n} \otimes |+\rangle_{n-1} \otimes |+\rangle_{n-2} \otimes ... \otimes |+\rangle_0

量子ビット1から $n$ までの状態は、 $n$ -qubit基底状態 $|00...00\rangle, |00...01\rangle, |000...11\rangle, ..., |111...11\rangle$ のすべて $2^n$ に対する和として、より単純に書くことができる。これらの基底状態の集合を $\Sigma^n$ と呼ぶ。 (詳しくは量子アルゴリズムの基礎を参照）

|\Psi\rangle = |-\rangle \otimes \frac{1}{\sqrt{2^n}}\sum\limits_{x \in \Sigma^n}{|x\rangle}

次に、 $U_f$ ゲートが量子ビットに適用される。 $|- \oplus f(x)\rangle$ このゲートは最初のn個の量子ビットを入力とし（n個のビット列の等しい重ね合わせの状態にある）、出力量子ビットに関数 $f(x)=s \cdot x$ を適用する。位相キックバック機構のおかげで、この量子ビットの状態は変化しませんが、入力量子ビットの状態のいくつかの項がマイナス符号になります：

|\Psi\rangle = |-\rangle \otimes \frac{1}{\sqrt{2^n}}\sum\limits_{x \in \Sigma^n}{(-1)^{f(x)}|x\rangle}

さて、次のハダマードのセットは0から $n-1$ までの量子ビットに適用される。この場合、マイナス符号を追跡するのは難しい。標準的な基底状態（ $|x\rangle$ ）の $n$ 量子ビットにハダマードのレイヤーを適用すると、次のように書けることを知っておくと役に立つ：

H^{\otimes n} |x\rangle = \frac{1}{\sqrt{2^n}}\sum\limits_{y \in \Sigma^n}{(-1)^{x \cdot y}|y\rangle}

だから、状態はこうなる：

|\Psi\rangle = |-\rangle \otimes \frac{1}{2^n}\sum\limits_{x \in \Sigma^n}\sum\limits_{y \in \Sigma^n}{(-1)^{(s \cdot x) + (x \cdot y)}|y\rangle}

次のステップは、最初の $n$ ビットを測定することである。しかし、何を測定するのだろうか？上の状態が単純化されることがわかった： $|\Psi\rangle = |-\rangle \otimes |s\rangle$ しかし、それは明らかではない。もし、数学について詳しく知りたいのであれば、ジョン・ワトラスの「量子アルゴリズムの基礎」コースを参照されたい。しかし重要なのは、位相キックバックのメカニズムによって、入力量子ビットは $|s\rangle$ の状態になるということだ。つまり、秘密の文字列 $s$ が何であったかを知るには、単に量子ビットを測定すればよい！

理解度チェック

上記のステップ3からの状態が、 $n=1$ の特別な場合の状態 $|s\rangle$ であることを確認する。

つの和を明示的に書き出すと、4つの項を持つ状態が得られるはずである（ここでは出力状態 $|-\rangle$ を省略しよう）：
$|\Psi\rangle = \frac{1}{2}[|0\rangle + (-1)^s |0\rangle + |1\rangle + (-1)^{(s+1)} |1\rangle]$
$s=0$ の場合、最初の2項が構成的に加算され、最後の2項が相殺され、 $|\Psi\rangle = |0\rangle$ が残る。 $s=1$ の場合、最後の2項が構成的に加算され、最初の2項が相殺され、 $|\Psi\rangle = |1\rangle$ が残る。つまり、どちらの場合でも、 $|\Psi\rangle = |s\rangle$ 。この最も単純なケースで、 $n$ の量子ビットを持つ一般的なケースがどのように機能するか、おわかりいただけたでしょうか。 $|s\rangle$ でない項はすべて干渉し、 $|s\rangle$ の状態だけが残ります。

同じアルゴリズムでBernstein-Vazirani問題とDeutsch-Jozsa問題を解くことができるのか？これを理解するために、Bernstein-Vazirani関数について考えてみよう。Bernstein-Vazirani関数は $f(x) = s \cdot x$ の形をしている。これらの関数もDeutsch-Jozsa関数なのだろうか？つまり、この形式の関数が、ドイチュ・ヨッツァ問題の約束事である「 定数か 均衡か 」を満たすかどうかを判断するのである。同じアルゴリズムが2つの異なる問題をどのように解決するのかを理解する上で、これがどのように役立つのだろうか？

もし s=00...00 であれば、その関数は定数である（すべての文字列xに対して常に0を返す）。 $f(x) = s \cdot x$ の形のすべてのBernstein-Vazirani関数は、Deutsch-Jozsa問題の約束も満たしている。 sがそれ以外の文字列の場合、この関数は釣り合う。そこで、Deutsch-Jozsaアルゴリズムをこれらの関数の一方に適用することで、両方の問題を同時に解決する！文字列が返され、その文字列が00...00であれば、それが定数であることがわかる。文字列の中に少なくとも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"))

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アルゴリズムをBernstein-Vazirani問題に適用すると、たった1回のクエリーで、関数: $f(x)=x \cdot s$ で使用されている文字列 $s$ が返される。古典的なアルゴリズムでは、同じ問題を解くのに $n$ 。

おわりに

これらの簡単な例を検討することで、量子コンピュータがどのように重ね合わせ、もつれ、干渉を利用し、古典的なコンピュータを凌駕するパワーを発揮できるのかについて、より直感的に理解していただけたと思う。

Deutsch-Jozsaアルゴリズムは、古典的アルゴリズムを上回るスピードアップを初めて実証したため、歴史的に非常に重要である。 Deutsch-Jozsaアルゴリズムは物語の始まりに過ぎない。

このアルゴリズムを使って問題を解いた後、BernsteinとVaziraniはこれを基に、 再帰的フーリエ・サンプリング問題と呼ばれる、より複雑で再帰的な問題に取り組んだ。彼らの解決策は、古典的なアルゴリズムに比べて超多項式のスピードアップを提供した。そして、バーンスタインとヴァジラニよりも前に、ピーター・ショーはすでに、量子コンピューターが古典的アルゴリズムよりも指数関数的に速く大きな数を因数分解できるようにする有名なアルゴリズムを考え出していた。これらの結果は総体として、未来の量子コンピュータが持つエキサイティングな可能性を示し、物理学者とエンジニアをこの未来の実現に向けて駆り立てた。

質問

指導者は、このノートがどのように使用されているかについての簡単なアンケートに答えることで、解答と一般的なカリキュラムにおける配置についてのガイダンスが付いたバージョンのノートを要求することができる。

重要な概念

DeutschアルゴリズムとDeutsch-Jozsaアルゴリズムは、量子並列性と干渉を組み合わせることで、古典的なコンピュータよりも速く問題の答えを見つけることができる。
位相キックバック・メカニズムとは、ある量子ビット上の演算を別の量子ビットの位相に転送するという、直感に反する量子現象である。 DeutschとDeutsch-Jozsaアルゴリズムはこのメカニズムを利用している。
Deutsch-Jozsaアルゴリズムは、いかなる決定論的古典アルゴリズムよりも多項式的なスピードアップを提供する。
Deutsch-Jozsaアルゴリズムは、Bernstein-Vazirani問題と呼ばれる、関数に符号化された隠れた文字列を見つける別の問題に適用することができる。

True/False

T/F DeutschのアルゴリズムはDeutsch-Jozsaアルゴリズムの特殊なケースであり、入力は1量子ビットである。
T/F DeutschアルゴリズムとDeutsch-Jozsaアルゴリズムは、量子重ね合わせと干渉を利用して効率性を実現している。
T/F Deutsch-Jozsaアルゴリズムは、関数が定数か均衡かを決定するために複数の関数評価を必要とする。
T/F "Bernstein-Vaziraniアルゴリズム "は実はDeutsch-Jozsaアルゴリズムと同じで、別の問題に適用されたものである。
T/F Bernstein-Vaziraniアルゴリズムは複数の秘密文字列を同時に見つけることができる。

簡潔な回答

古典的アルゴリズムがドイチュ・ヨッツァ問題を解くのにかかる時間は、最悪の場合どれくらいか？
ベルンシュタイン＝ヴァジラニ問題を古典的アルゴリズムで解くと、どのくらいの時間がかかるだろうか？この場合、DJアルゴリズムはどのようなスピードアップをもたらすのでしょうか？
位相キックバック機構について説明し、それがドイチュ・ヨツァ問題とベルンシュタイン・バジラニ問題を解くためにどのように働くかを説明しなさい。

課題問題

Deutsch-Jozsaアルゴリズム：上で、Deutschアルゴリズムの中間量子ビット状態 $\pi_1$ 、 $\pi_2$ を求める問題があったことを思い出してほしい。 Deutsch-Jozsa アルゴリズムの中間 $n+1$ -qubit状態 $\pi_1$ 、 $\pi_2$ 、 $n=2$ という特定の場合について同じことを行う。次に、 $\pi_3 = |-\rangle \otimes \sum\limits_{x_0...x_n}(-1)^{f(x_0...x_n)}|x_0 ... x_n\rangle$ を、 $n=2$ という特定の場合について検証する。

このページは役に立ちましたか？

バグや誤字の報告、またはコンテンツの要求はGitHubで行ってください。