ドイチュのアルゴリズム

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

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

$$\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\}\rightarrow\{0,1\}$
出力: $f$ が定数関数なら $0$、$f$ が平衡関数なら $1$

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

$$\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(1)$ をクエリしなければなりません。 たとえば $f(1) = 1$ とわかっていても、$f(0) = 1$ か $f(0) = 0$ かによって答えは $0$ にも $1$ にもなり得ます。 他のケースも同様で、2ビットのうち1つしか知らなければ、そのパリティについての情報はまったく得られません。 したがって、前節で説明したブール回路が、この問題を解くのに必要なクエリ数の観点での最善策です。

量子回路の説明

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

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

解析

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

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

$$\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の状態を因数分解したまま残すこと）は直感的でないように感じるかもしれませんが、後の式をよりコンパクトにするためです。

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

$$\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.$$

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

$$\vert 0 \oplus a\rangle - \vert 1 \oplus a\rangle = (-1)^a \bigl( \vert 0\rangle - \vert 1\rangle \bigr)$$

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

$$\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}$$

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

$$\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}$$

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

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

$$\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(0) \oplus f(1)$ が $-1$ の指数として現れていますが、いずれの場合も同じ結果が得られます。 これは、任意の整数 $k$ に対して $(-1)^k$ の値は $k$ が偶数か奇数かにのみ依存するからです。

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

$$\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\in\Sigma$ のすべての選択に対して成り立つことに注目します。

$$\vert b \oplus c\rangle = X^c \vert b \rangle$$

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

$$\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}$$

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

$$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\in\Sigma$ のすべての選択に対して成り立ちます。 この等式が $b=0$ と $b=1$ の両方で成り立つことから、線形性によって次が導かれます。

$$U_f \bigl( \vert \psi \rangle \vert a \rangle \bigr) = \bigl(X^{f(a)}\vert \psi \rangle\bigr) \vert a \rangle$$

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

$$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\vert - \rangle = - \vert - \rangle$ という性質です。 数学的には、ベクトル $\vert - \rangle$ は行列 $X$ の 固有ベクトル であり、固有値 $-1$ を持ちます。

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

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

$$\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つの関数 $f_1,$ $f_2,$ $f_3,$ $f_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 メソッドで確認できます。関数 $f_3$ の回路を以下に示します。

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

次に、ドイチュのアルゴリズムの実際の量子回路を作成します。クエリゲートの部分には、引数として渡された量子回路実装を代入します。先ほど定義した 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"))

最後に、先ほど定義した回路を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'