メインコンテンツへスキップ

ドイチュのアルゴリズム

ドイチュのアルゴリズムは、n=1n = 1 の特殊なケースにおけるパリティ問題を解きます。 量子計算の文脈では、この問題は ドイチュの問題 と呼ばれることがあり、このレッスンでもその呼称を使用します。

正確に言えば、入力は1ビットから1ビットへの関数 f:Σ→Σf:\Sigma \rightarrow \Sigma で表されます。 このような関数は4つ存在します。

af1(a)0010af2(a)0011af3(a)0110af4(a)0111\rule[-10mm]{0mm}{10mm} \begin{array}{c|c} a & f_1(a)\\ \hline 0 & 0\\ 1 & 0 \end{array} \qquad \begin{array}{c|c} a & f_2(a)\\ \hline 0 & 0\\ 1 & 1 \end{array} \qquad \begin{array}{c|c} a & f_3(a)\\ \hline 0 & 1\\ 1 & 0 \end{array} \qquad \begin{array}{c|c} a & f_4(a)\\ \hline 0 & 1\\ 1 & 1 \end{array}

最初と最後の関数は 定数関数 であり、中央の2つは 平衡関数 です。平衡関数とは、入力全体にわたって関数の2つの出力値が同じ回数だけ現れるものを指します。 ドイチュの問題は、入力関数がどちらのカテゴリに属するかを判定することです。すなわち、定数関数か平衡関数かを判定します。

ドイチュの問題

入力: 関数 f:{0,1}→{0,1}f:\{0,1\}\rightarrow\{0,1\}
出力: ff が定数関数なら 00、ff が平衡関数なら 11

ドイチュの問題における入力関数 ff を文字列へのランダムアクセスとして捉えると、2ビットの文字列 f(0)f(1)f(0)f(1) を考えることになります。

functionstringf100f201f310f411\begin{array}{cc} \mathsf{function} & \mathsf{string}\\ \hline f_1 & 00 \\ f_2 & 01 \\ f_3 & 10 \\ f_4 & 11 \end{array}

このように見ると、ドイチュの問題は2ビットのパリティ（同等に、排他的論理和）を計算することに相当します。

この問題を正しく解く古典的なクエリアルゴリズムは、必ず両方のビット f(0)f(0) と f(1)f(1) をクエリしなければなりません。 たとえば f(1)=1f(1) = 1 とわかっていても、f(0)=1f(0) = 1 か f(0)=0f(0) = 0 かによって答えは 00 にも 11 にもなり得ます。 他のケースも同様で、2ビットのうち1つしか知らなければ、そのパリティについての情報はまったく得られません。 したがって、前節で説明したブール回路が、この問題を解くのに必要なクエリ数の観点での最善策です。

量子回路の説明​

ドイチュのアルゴリズムは、1回のクエリでドイチュの問題を解きます。これにより、量子計算が古典計算に対して定量的な優位性を持つことが示されます。 その優位性は控えめなもの——2回のクエリに対して1回——ではありますが、どこかから始めなければなりません。 科学的な進歩は、一見ささやかな発端から生まれることがあります。

以下は、ドイチュのアルゴリズムを表す量子回路です。

ドイチュのアルゴリズム

解析​

ドイチュのアルゴリズムを解析するため、上記の回路の動作を追いながら、以下の図に示される各時点での量子ビットの状態を確認します。

ドイチュのアルゴリズム中の状態

初期状態は ∣1⟩∣0⟩\vert 1\rangle \vert 0 \rangle であり、回路の左側にある2つのアダマール演算によってこの状態は次のように変換されます。

∣π1⟩=∣−⟩∣+⟩=12(∣0⟩−∣1⟩)∣0⟩+12(∣0⟩−∣1⟩)∣1⟩.\vert \pi_1 \rangle = \vert - \rangle \vert + \rangle = \frac{1}{2} \bigl( \vert 0\rangle - \vert 1\rangle \bigr) \vert 0\rangle + \frac{1}{2} \bigl( \vert 0\rangle - \vert 1\rangle \bigr) \vert 1\rangle.

（常に通り、Qiskit の量子ビット順序の慣例に従い、上の量子ビットを右に、下の量子ビットを左に配置しています。）この積状態を部分的に分散して書くこと（量子ビット1の状態を因数分解したまま残すこと）は直感的でないように感じるかもしれませんが、後の式をよりコンパクトにするためです。

次に、UfU_f ゲートが適用されます。 UfU_f ゲートの定義によれば、上/右端の量子ビットの古典状態に対する関数 ff の値が下/左端の量子ビットに XOR されます。これにより ∣π1⟩\vert \pi_1\rangle は次の状態に変換されます。

∣π2⟩=12(∣0⊕f(0)⟩−∣1⊕f(0)⟩)∣0⟩+12(∣0⊕f(1)⟩−∣1⊕f(1)⟩)∣1⟩.\vert \pi_2 \rangle = \frac{1}{2} \bigl( \vert 0 \oplus f(0) \rangle - \vert 1 \oplus f(0) \rangle \bigr) \vert 0 \rangle + \frac{1}{2} \bigl( \vert 0 \oplus f(1) \rangle - \vert 1 \oplus f(1) \rangle \bigr) \vert 1 \rangle.

次の等式に注目することで、この式を簡略化できます。

∣0⊕a⟩−∣1⊕a⟩=(−1)a(∣0⟩−∣1⟩)\vert 0 \oplus a\rangle - \vert 1 \oplus a\rangle = (-1)^a \bigl( \vert 0\rangle - \vert 1\rangle \bigr)

これは a∈Σa\in\Sigma の両方の値で成り立ちます。 より明示的に示すと、2つのケースは以下の通りです。

∣0⊕0⟩−∣1⊕0⟩=∣0⟩−∣1⟩=(−1)0(∣0⟩−∣1⟩)∣0⊕1⟩−∣1⊕1⟩=∣1⟩−∣0⟩=(−1)1(∣0⟩−∣1⟩)\begin{aligned} \vert 0 \oplus 0\rangle - \vert 1 \oplus 0\rangle & = \vert 0 \rangle - \vert 1 \rangle = (-1)^0 \bigl( \vert 0\rangle - \vert 1\rangle \bigr)\\ \vert 0 \oplus 1\rangle - \vert 1 \oplus 1\rangle & = \vert 1 \rangle - \vert 0\rangle = (-1)^1 \bigl( \vert 0\rangle - \vert 1\rangle \bigr) \end{aligned}

したがって、∣π2⟩\vert\pi_2\rangle を次のように表すこともできます。

∣π2⟩=12(−1)f(0)(∣0⟩−∣1⟩)∣0⟩+12(−1)f(1)(∣0⟩−∣1⟩)∣1⟩=∣−⟩((−1)f(0)∣0⟩+(−1)f(1)∣1⟩2).\begin{aligned} \vert\pi_2\rangle & = \frac{1}{2} (-1)^{f(0)} \bigl( \vert 0 \rangle - \vert 1 \rangle \bigr) \vert 0 \rangle + \frac{1}{2} (-1)^{f(1)} \bigl( \vert 0 \rangle - \vert 1 \rangle \bigr) \vert 1 \rangle \\ & = \vert - \rangle \biggl( \frac{(-1)^{f(0)} \vert 0\rangle + (-1)^{f(1)} \vert 1\rangle}{\sqrt{2}}\biggr). \end{aligned}

ここで興味深いことが起きました！ UfU_f ゲートが標準基底状態に作用するとき、上/右端の量子ビットはそのままにして関数値を下/左端の量子ビットに XOR するはずですが、上/右端の量子ビットの状態が（一般的に）変化し、下/左端の量子ビットの状態は UfU_f ゲートの前後で ∣−⟩\vert - \rangle のまま変わらないことがわかります。 この現象は 位相キックバック と呼ばれており、後でさらに詳しく説明します。

最後の簡略化として (−1)f(0)(-1)^{f(0)} の因数を和の外に出すと、状態 ∣π2⟩\vert\pi_2\rangle の次の表現が得られます。

∣π2⟩=(−1)f(0)∣−⟩(∣0⟩+(−1)f(0)⊕f(1)∣1⟩2)={(−1)f(0)∣−⟩∣+⟩if f(0)⊕f(1)=0(−1)f(0)∣−⟩∣−⟩if f(0)⊕f(1)=1.\begin{aligned} \vert\pi_2\rangle & = (-1)^{f(0)} \vert - \rangle \biggl( \frac{\vert 0\rangle + (-1)^{f(0) \oplus f(1)} \vert 1\rangle}{\sqrt{2}}\biggr) \\ & = \begin{cases} (-1)^{f(0)} \vert - \rangle \vert + \rangle & \text{if $f(0) \oplus f(1) = 0$}\\[1mm] (-1)^{f(0)} \vert - \rangle \vert - \rangle & \text{if $f(0) \oplus f(1) = 1$}. \end{cases} \end{aligned}

この式では、純粋に代数的な観点からは f(1)−f(0)f(1) - f(0) を期待するかもしれないところに f(0)⊕f(1)f(0) \oplus f(1) が −1-1 の指数として現れていますが、いずれの場合も同じ結果が得られます。 これは、任意の整数 kk に対して (−1)k(-1)^k の値は kk が偶数か奇数かにのみ依存するからです。

上の量子ビットに最後のアダマールゲートを適用すると、状態は次のようになります。

∣π3⟩={(−1)f(0)∣−⟩∣0⟩if f(0)⊕f(1)=0(−1)f(0)∣−⟩∣1⟩if f(0)⊕f(1)=1,\vert \pi_3 \rangle = \begin{cases} (-1)^{f(0)} \vert - \rangle \vert 0 \rangle & \text{if $f(0) \oplus f(1) = 0$}\\[1mm] (-1)^{f(0)} \vert - \rangle \vert 1 \rangle & \text{if $f(0) \oplus f(1) = 1$}, \end{cases}

右/上端の量子ビットを測定すると、確率1で正しい結果が得られます。

位相キックバックに関する補足​

次に進む前に、位相キックバック現象に光を当てるために、上記の解析を少し異なる角度から見てみましょう。

まず、次の等式がビット b,c∈Σb,c\in\Sigma のすべての選択に対して成り立つことに注目します。

∣b⊕c⟩=Xc∣b⟩\vert b \oplus c\rangle = X^c \vert b \rangle

これは c=0c = 0 と c=1c = 1 の2つの値を確認することで検証できます。

∣b⊕0⟩=∣b⟩=I∣b⟩=X0∣b⟩∣b⊕1⟩=∣¬b⟩=X∣b⟩=X1∣b⟩.\begin{aligned} \vert b \oplus 0 \rangle & = \vert b\rangle = \mathbb{I} \vert b \rangle = X^0 \vert b \rangle\\ \vert b \oplus 1 \rangle & = \vert \neg b\rangle = X \vert b \rangle = X^1 \vert b \rangle. \end{aligned}

この等式を使うと、次のことがわかります。

Uf(∣b⟩∣a⟩)=∣b⊕f(a)⟩∣a⟩=(Xf(a)∣b⟩)∣a⟩U_f \bigl(\vert b\rangle \vert a \rangle\bigr) = \vert b \oplus f(a) \rangle \vert a \rangle = \bigl(X^{f(a)}\vert b \rangle\bigr) \vert a \rangle

これはビット a,b∈Σa,b\in\Sigma のすべての選択に対して成り立ちます。 この等式が b=0b=0 と b=1b=1 の両方で成り立つことから、線形性によって次が導かれます。

Uf(∣ψ⟩∣a⟩)=(Xf(a)∣ψ⟩)∣a⟩U_f \bigl( \vert \psi \rangle \vert a \rangle \bigr) = \bigl(X^{f(a)}\vert \psi \rangle\bigr) \vert a \rangle

これはすべての量子ビット状態ベクトル ∣ψ⟩\vert \psi\rangle に対して成り立ち、したがって次も成り立ちます。

Uf(∣−⟩∣a⟩)=(Xf(a)∣−⟩)∣a⟩=(−1)f(a)∣−⟩∣a⟩.U_f \bigl( \vert - \rangle \vert a \rangle \bigr) = \bigl(X^{f(a)} \vert - \rangle \bigr) \vert a \rangle = (-1)^{f(a)} \vert - \rangle \vert a \rangle.

これが成り立つ鍵は、X∣−⟩=−∣−⟩X\vert - \rangle = - \vert - \rangle という性質です。 数学的には、ベクトル ∣−⟩\vert - \rangle は行列 XX の 固有ベクトル であり、固有値 −1-1 を持ちます。

固有ベクトルと固有値については、位相推定と因数分解 の今後のレッスンでさらに詳しく説明します。そこでは位相キックバック現象が他のユニタリ演算に一般化されます。

スカラーがテンソル積を自由に通過できることを念頭に置くと、上記の解析において UfU_f が ∣π1⟩\vert \pi_1\rangle を ∣π2⟩\vert \pi_2\rangle に変換する方法を別の形で導くことができます。

∣π2⟩=Uf(∣−⟩∣+⟩)=12Uf(∣−⟩∣0⟩)+12Uf(∣−⟩∣1⟩)=∣−⟩((−1)f(0)∣0⟩+(−1)f(1)∣1⟩2).\begin{aligned} \vert \pi_2 \rangle & = U_f \bigl( \vert - \rangle \vert + \rangle \bigr)\\ & = \frac{1}{\sqrt{2}} U_f \bigl(\vert - \rangle \vert 0\rangle \bigr) + \frac{1}{\sqrt{2}} U_f \bigl(\vert - \rangle \vert 1\rangle \bigr)\\ & = \vert - \rangle \biggl( \frac{(-1)^{f(0)} \vert 0\rangle + (-1)^{f(1)} \vert 1\rangle}{\sqrt{2}}\biggr). \end{aligned}

Qiskit による実装​

それでは、Qiskit でドイチュのアルゴリズムを実装する方法を見ていきましょう。まずバージョン確認を行い、この実装に必要なインポートを実行します。 続いて説明する他のアルゴリズムの実装では、モジュール性を高めるために必要なインポートをそれぞれ別途実行します。

# Added by doQumentation — required packages for this notebook
!pip install -q qiskit qiskit-aer
from qiskit import __version__

print(__version__)
2.1.1
from qiskit import QuantumCircuit
from qiskit_aer import AerSimulator

まず、先ほど説明した1ビットから1ビットへの4つの関数 f1,f_1, f2,f_2, f3,f_3, f4f_4 のいずれかのクエリゲートを実装する量子回路を定義します。すでに述べたように、クエリゲートの実装はドイチュのアルゴリズム自体の一部ではありません。ここでは、クエリゲートの回路実装という形で入力を準備する方法の一例を示しています。

def deutsch_function(case: int):
    # This function generates a quantum circuit for one of the 4 functions
    # from one bit to one bit

    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

各回路がどのような形であるかは、draw メソッドで確認できます。関数 f3f_3 の回路を以下に示します。

display(deutsch_function(3).draw(output="mpl"))

Output of the previous code cell

次に、ドイチュのアルゴリズムの実際の量子回路を作成します。クエリゲートの部分には、引数として渡された量子回路実装を代入します。先ほど定義した deutsch_function が生成する4つの回路のうちの1つをすぐにここに渡します。 バリアは、クエリゲートの実装と回路の残りの部分との視覚的な区切りを示すために含まれています。

def compile_circuit(function: QuantumCircuit):
    # Compiles a circuit for use in Deutsch's algorithm.

    n = function.num_qubits - 1
    qc = QuantumCircuit(n + 1, n)

    qc.x(n)
    qc.h(range(n + 1))

    qc.barrier()
    qc.compose(function, inplace=True)
    qc.barrier()

    qc.h(range(n))
    qc.measure(range(n), range(n))

    return qc

同様に、draw メソッドで回路の形を確認できます。

display(compile_circuit(deutsch_function(3)).draw(output="mpl"))

Output of the previous code cell

最後に、先ほど定義した回路を1回実行し、適切な結果として「constant（定数関数）」または「balanced（平衡関数）」を出力する関数を作成します。

def deutsch_algorithm(function: QuantumCircuit):
    # Determine if a one-bit function is constant or balanced.

    qc = compile_circuit(function)

    result = AerSimulator().run(qc, shots=1, memory=True).result()
    measurements = result.get_memory()
    if measurements[0] == "0":
        return "constant"
    return "balanced"

これで、上で定義した4つの関数のいずれかに対してドイチュのアルゴリズムを実行できます。

f = deutsch_function(3)
display(deutsch_algorithm(f))
'balanced'