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

ドイッチュのアルゴリズムは、 $n = 1$ という特例におけるパリティ問題を解くものである。 量子コンピューティングの分野では、この問題は「 ドイッチュの問題 」と呼ばれることもあり、このレッスンではその呼称に従うことにする。

正確には、入力は1ビットから1ビットへの関数（ $f:\Sigma \rightarrow \Sigma$ ）で表される。 このような機能は4つある：

これらの関数の最初と最後は定数であり、真ん中の2つは釣り合いが取れている。つまり、関数の2つの可能な出力値は、入力を範囲指定したときに同じ回数だけ発生する。 ドイッチュの問題は、入力関数がこの2つのカテゴリーのどちらに属するかを決定することである。

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

このように考えると、ドイッチュの問題は、2つのビットのパリティ（あるいは等価的に排他的論理和）を計算することである。

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

量子回路記述

Deutschのアルゴリズムは、単一のクエリーを用いてDeutschの問題を解くため、古典的な計算に対する量子の定量的な利点を提供する。 これはささやかな利点かもしれない。 科学の進歩は時として、一見地味な起源を持つ。

ドイッチュのアルゴリズムを説明する量子回路を紹介しよう：

解析

Deutschのアルゴリズムを解析するために、上の回路の動作をトレースし、この図が示唆する時間における量子ビットの状態を特定する：

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

(いつものように、Qiskitの量子ビットの並び順の規則に従っている。上の量子ビットを右に、下の量子ビットを左に置く) この積の状態を部分的に分散して書くのは直感的でないと感じるかもしれないが（量子ビット1の状態を因数分解したままにしておく）、こうすることで後の式がよりコンパクトになる。

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

この式を単純化するには、次の式を使用する

$a\in\Sigma$ の両方の値について成立する。 より具体的に言えば、2つのケースは以下の通りである。

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

面白いことが起きた！ 標準的な基底状態に対する $U_f$ ゲートの動作は、一番上/右端の量子ビットはそのままにしておき、一番下/左端の量子ビットに関数値をXORします。しかし、ここでは、一番上/右端の量子ビットの状態が（一般的に）変化している一方で、一番下/左端の量子ビットの状態は同じままであることがわかります。具体的には、 $U_f$ ゲートが実行される前と後では、 $\vert - \rangle$ の状態になっています。 この現象はフェイズ・キックバックとして知られており、これについては後ほど詳しく説明する。

最後の単純化として、 $(-1)^{f(0)}$ の因子を和の外側に引っ張り出すことで、状態 $\vert\pi_2\rangle$ の式が得られる：

この式では、 $-1$ の指数に $f(0) \oplus f(1)$ が含まれていることに注意してください。これは、純粋に代数的な観点からは $f(1) - f(0)$ となることが予想されますが、どちらの場合でも同じ結果が得られます。 これは、任意の整数 $k$ に対して、 $(-1)^k$ の値が、 $k$ が偶数か奇数かということのみに依存するためである。

最後のハダマードゲートをトップ量子ビットに適用すると、次のような状態になる

右/一番上の量子ビットが測定されたとき、確率 $1$、正しい結果を導く。

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

次に進む前に、位相のキックバック現象を解明するために、上記の分析を少し違った角度から見てみよう。

まず、次の式が、 $b,c\in\Sigma$ といったあらゆるビットの組み合わせに対して成り立つことに注意してください。

これは、 $c = 0$ と $c = 1$ の2つの可能な値についてチェックすることで検証できる：

この式を使うと、次のようになる

ビットの組み合わせ $a,b\in\Sigma$ について、すべて この式は、 $b=0$ および $b=1$ についても成り立つため、線形性から、

すべての量子ビットの状態ベクトル $\vert \psi\rangle$ について、したがって

これが成り立つ鍵となるのは、 $X\vert - \rangle = - \vert - \rangle$ である。 数学的に言えば、ベクトル $\vert - \rangle$ は、 固有値 $-1$ を持つ行列 $X$ の固有ベクトルである。

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

スカラーはテンソル積を通して自由に浮遊することを念頭に置いて、上記の分析において、 $U_f$ という演算が $\vert \pi_1\rangle$ を $\vert \pi_2\rangle$ に変換する方法を推論する別の方法を見つける：

Qiskitでの実装

では、DeutschのアルゴリズムをQiskitでどのように実装できるかを見てみよう。 まずはバージョンチェックから始め、この実装だけに必要なインポートを実行する。 この後に続く他のアルゴリズムの実装については、モジュール性を高めるために、必要なインポートを個別に行うことにする。

from qiskit import __version__

print(__version__)

Output:

2.1.1

from qiskit import QuantumCircuit
from qiskit_aer import AerSimulator

まず、前述した1ビットから1ビットへの4つの関数（ $f_1$、 $f_2$、 $f_3$、または $f_4$ ）のうちの1つに対応するクエリゲートを実装する量子回路を定義します。 すでに述べたように、クエリゲートの実装は、厳密にはドイッチュのアルゴリズムそのものの一部ではありません。 ここでは、クエリゲートの回路実装という形で、入力を準備する一つの方法を単に示しているに過ぎません。

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

Output:

次に、クエリーゲートを引数として与えられた量子回路実装に置き換えて、ドイチュのアルゴリズムの実際の量子回路を作成する。 まもなく、先に定義した関数 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:

最後に、先に定義した回路を1回実行し、適切な結果を出力する関数を作成する："コンスタント "または "バランス "である

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"

これでDeutschのアルゴリズムを、上で定義した4つの関数のいずれかに対して実行することができる。

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

Output:

'balanced'