ドイッチュ・ジョサのアルゴリズム

ドイッチュ・ジョサのアルゴリズムは、量子アルゴリズムであり、1992年にデイビッド・ドイッチュ（英語版）とリチャード・ジョサ（英語版）によって提案され[1]、 Richard Cleve, Artur Ekert, Chiara Macchiavello, そして Michele Mosca によって 1998 年に改良された[2]。実用性は限られるが、既存のどの決定論的古典アルゴリズムよりも指数関数的に早い量子アルゴリズムのうち最も早期に発見されたものの一つである。また、これは決定的アルゴリズムであり、常に解を得ることができ、またその解は常に正しい。

問題設定

ドイッチュ・ジョサの問題では、オラクルと呼ばれるある関数 ${\displaystyle f:\{0,1\}^{n}\rightarrow \{0,1\}}$ が実装されたブラックボックス量子コンピュータが与えられている。 わかりやすく言えば、オラクルはn桁の2進数値を入力として受け取り、0または1を出力する。

ここで、関数${\displaystyle f}$は定値 (すべての量子ビットが0 またはすべての量子ビットが1)であるか、均等 (量子ビットの丁度半数が1で、残りの半数が0)であることが保証されている。

問題は、オラクルを用いて関数が定値か均等かを決定することである。

動機

ドイッチュ・ジョサの問題は、量子アルゴリズムで解きやすく、かつ、決定的古典アルゴリズムでは解くのが難しいよう明示的に意図された問題である。 この問題の動機付けは、決定的古典コンピューターでは問題を解くのに大量のクエリを必要とするブラックボックス問題を、量子コンピューターが誤りなく効率的に解くことが可能であることを示すことにある。

ドイッチュ・ジョサのアルゴリズムのQiskit実装

以下では、IBMが提供するオープンソースの量子コンピューティング用ソフトウェア開発フレームワークであるQiskitを使って、ドイッチュ・ジョサのアルゴリズムをPythonで実装する簡単な例を示す。理論がどのように動作する量子回路に変換されるかを段階的に解説する。

1. 必要なライブラリのインポート

from qiskit import QuantumCircuit, transpile
from qiskit_aer import Aer

2. オラクルを作成するためのヘルパー関数の定義

def create_constant_oracle(n_qubits, output):
    """
    'constant' オラクルを作成。

    `output` が 0 の場合、このオラクルは常に 0 を返す。
    `output` が 1 の場合、このオラクルは常に 1 を返す。

    Args:
        n_qubits (int): 入力量子ビットの数。
        output (int): 関数が返す定数値 (0 または 1)。

    Returns:
        QuantumCircuit: 定数オラクルを実装した量子回路。
    """
    oracle = QuantumCircuit(n_qubits + 1)

    # もしオラクルが常に1を返す場合、"output"量子ビットをXゲートで反転させる
    # （量子ビットに対するNOTゲートと考えられる）。
    if output == 1:
        oracle.x(n_qubits)

    return oracle


def create_balanced_oracle(n_qubits):
    """
    'balanced' オラクルを作成。

    入力ビットパターンの半分に対しては 0 を、もう半分に対しては 1 を返す。

    デモとして、この関数では単純なバランス関数を実装している。
    入力の最初の量子ビットを制御としてXゲートを配置し、
    半分の入力に対して出力量子ビットを反転させる。

    Args:
        n_qubits (int): 入力量子ビットの数。

    Returns:
        QuantumCircuit: バランスオラクルを実装した量子回路。
    """
    oracle = QuantumCircuit(n_qubits + 1)

    # シンプルなパターンを使用する: 最初の量子ビットが1なら出力を反転する。
    # これにより、可能な入力の半分で出力が変わる。
    oracle.cx(0, n_qubits)

    return oracle

3. ドイッチュ・ジョサ回路を組み立てる関数

def deutsch_jozsa_circuit(oracle, n_qubits):
    """
    ドイッチュ・ジョサ量子回路を組み立てる。

    回路は以下のステップを実行する:
    1. すべての「入力」量子ビットを |0> に初期化する。
    2. 「出力」量子ビットを |1> に初期化する。
    3. すべての量子ビットにアダマールゲートを適用する。
    4. オラクルを適用する。
    5. 入力量子ビットに再度アダマールゲートを適用する。
    6. 入力量子ビットを測定する。

    Args:
        oracle (QuantumCircuit): 「謎」の関数 f(x) をエンコードした回路。
        n_qubits (int): 入力量子ビットの数。

    Returns:
        QuantumCircuit: 実行準備のできた完全なドイッチュ・ジョサ回路。
    """
    # 入力として n_qubits、出力として 1 つの量子ビットを足した合計
    dj_circuit = QuantumCircuit(n_qubits + 1, n_qubits)

    # 1. 入力量子ビットはすでに |0> 状態。
    # 2. 出力量子ビットを |1> にセットする。Xゲートを使うことで実現可能。
    dj_circuit.x(n_qubits)

    # 3. 入力 + 出力の全量子ビットにアダマールゲートを適用。
    for qubit in range(n_qubits + 1):
        dj_circuit.h(qubit)

    # 4. オラクル回路を追加。
    dj_circuit.compose(oracle, inplace=True)

    # 5. 入力量子ビットのみに再度アダマールゲートを適用。
    for qubit in range(n_qubits):
        dj_circuit.h(qubit)

    # 6. 最後に入力量子ビットを測定。
    for qubit in range(n_qubits):
        dj_circuit.measure(qubit, qubit)

    return dj_circuit

4. 定数オラクルとバランスオラクルをテストする関数

def run_deutsch_jozsa_test(n_qubits, oracle_type='constant', constant_output=0):
    """
    定数オラクルまたはバランスオラクル用のドイッチュ・ジョサ回路を構築して実行し、
    結果を表示する。

    Args:
        n_qubits (int): 入力量子ビットの数。
        oracle_type (str): 'constant' または 'balanced' のいずれかを指定。
        constant_output (int): 定数オラクルの場合、0 または 1 を返すように設定。
    """
    # 選択されたオラクルを作成
    if oracle_type == 'constant':
        oracle = create_constant_oracle(n_qubits, constant_output)
        print(f"Using a CONSTANT oracle that always returns {constant_output}")
    else:
        oracle = create_balanced_oracle(n_qubits)
        print("Using a BALANCED oracle.")

    # ドイッチュ・ジョサ回路を作成
    dj_circ = deutsch_jozsa_circuit(oracle, n_qubits)

    # 参考のため回路を描画
    display(dj_circ.draw())

    # シミュレータを使用して回路を実行
    simulator = Aer.get_backend('aer_simulator')
    transpiled_circ = transpile(dj_circ, simulator)
    job = simulator.run(transpiled_circ, shots=1)
    result = job.result()
    counts = result.get_counts(transpiled_circ)

    print("Measurement outcomes:", counts)

    # 測定結果を解釈
    # もしすべてのビットが 0（例: 3量子ビットなら '000'）なら関数は定数、
    # それ以外ならバランスと判断する。
    measured_result = max(counts, key=counts.get)  # 最も確率の高い結果
    if measured_result == '0' * n_qubits:
        print("Conclusion: f(x) is CONSTANT.")
    else:
        print("Conclusion: f(x) is BALANCED.")

5. 実行例

# 3量子ビットでテスト
run_deutsch_jozsa_test(n_qubits=3, oracle_type='constant', constant_output=0)

print("\n" + "="*50 + "\n")

run_deutsch_jozsa_test(n_qubits=3, oracle_type='balanced')

出力例:

Using a CONSTANT oracle that always returns 0
     ┌───┐┌───┐┌─┐      
q_0: ┤ H ├┤ H ├┤M├──────
     ├───┤├───┤└╥┘┌─┐   
q_1: ┤ H ├┤ H ├─╫─┤M├───
     ├───┤├───┤ ║ └╥┘┌─┐
q_2: ┤ H ├┤ H ├─╫──╫─┤M├
     ├───┤├───┤ ║  ║ └╥┘
q_3: ┤ X ├┤ H ├─╫──╫──╫─
     └───┘└───┘ ║  ║  ║ 
c: 3/═══════════╩══╩══╩═
                0  1  2 
Measurement outcomes: {'000': 1}
Conclusion: f(x) is CONSTANT.

==================================================

Using a BALANCED oracle.
     ┌───┐          ┌───┐   ┌─┐
q_0: ┤ H ├───────■──┤ H ├───┤M├
     ├───┤┌───┐  │  └┬─┬┘   └╥┘
q_1: ┤ H ├┤ H ├──┼───┤M├─────╫─
     ├───┤├───┤  │   └╥┘ ┌─┐ ║ 
q_2: ┤ H ├┤ H ├──┼────╫──┤M├─╫─
     ├───┤├───┤┌─┴─┐  ║  └╥┘ ║ 
q_3: ┤ X ├┤ H ├┤ X ├──╫───╫──╫─
     └───┘└───┘└───┘  ║   ║  ║ 
c: 3/═════════════════╩═══╩══╩═
                      1   2  0 
Measurement outcomes: {'001': 1}
Conclusion: f(x) is BALANCED.

コードの解説

1. ライブラリのインポート

Qiskitのコア要素を使用する

• QuantumCircuit – 量子回路を構築するため
• Aer、transpile、run – 古典シミュレータ上で回路を実行するため

2. オラクルの作成

• 定数オラクル: どの入力に対しても同じ値（0 または 1）を返すオラクル。コードでは、常に1を返したい場合に出力量子ビットをXゲートで反転させている。
• バランスオラクル: 入力の半分に対して0、残りの半分に対して1を返すオラクル。ここでは CNOT (cx) を使って、最初の入力量子ビットが1の場合に出力量子ビットを反転させるようにしている。

3. ドイッチュ・ジョサ回路の構築

1. 入力量子ビットを ${\displaystyle \vert 0\rangle }$ に初期化する。出力量子ビットはXゲートで ${\displaystyle \vert 1\rangle }$ とする。

2. 全ての量子ビットにアダマールゲート](dj_circuit.h(qubit)) を適用し、${\displaystyle \vert 0\rangle }$ と ${\displaystyle \vert 1\rangle }$ の重ね合わせを作る。

3. 関数 (f) に従って出力量子ビットを変化させるオラクル回路を追加。

4. 入力量子ビットに再度アダマールゲートを適用して、干渉パターンを作り出し、(f) が定数かバランスかを判別できるようにする。

5. 最後に、入力量子ビットを測定。

4. 結果の解釈

1. (f) が 定数 なら、測定結果は ${\displaystyle \vert 0...0\rangle }$（すべて0）になる。

2. (f) が バランス なら、測定結果はすべて0以外のパターンになる。

5. アルゴリズムの実行

Aerの aer_simulator を用いて回路を実行する。ドイッチュ・ジョサのアルゴリズムは関数 (f) を区別するのに1回の呼び出し（およびいくつかの量子ゲート）だけで十分で、100%の確率で定数かバランスかを区別できる。したがって、複数回ショットを打っても同じ結果が得られる。

古典的な決定性アルゴリズムよりも速い理由

古典的な場合、"謎の"ブラックボックス関数 (f) が定数かバランスかを確実に判定するためには、最悪の場合 ${\displaystyle 2^{n-1}+1}$ 回も関数を呼び出す必要があるかもしれない。しかし、量子版のこの問題は、オラクルを1回呼び出していくつかの追加の量子ゲートを適用するだけで解決できる。ドイッチュ・ジョサのアルゴリズム自体は教育的な例と考えられているが、超位置と干渉を活用して関数呼び出しの回数を大幅に削減できるという、量子アルゴリズムの重要な考え方を示してる。

脚注

1. Deutsch, D.; Jozsa, R. (1992-12-08). “Rapid Solution of Problems by Quantum Computation” (英語). Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 439 (1907): 553–558. doi:10.1098/rspa.1992.0167. ISSN 1364-5021. http://rspa.royalsocietypublishing.org/cgi/doi/10.1098/rspa.1992.0167. 
2. Cleve, R.; Ekert, A.; Macchiavello, C.; Mosca, M. (1998-01-08). “Quantum algorithms revisited” (英語). Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences 454 (1969): 339–354. doi:10.1098/rspa.1998.0164. ISSN 1471-2946. http://www.royalsocietypublishing.org/doi/10.1098/rspa.1998.0164.