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

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

問題設定

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

ここで、関数 $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. 入力量子ビットを $\vert 0\rangle$ に初期化する。出力量子ビットはXゲートで $\vert 1\rangle$ とする。

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

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

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

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

4. 結果の解釈

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

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

5. アルゴリズムの実行

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

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

古典的な場合、"謎の"ブラックボックス関数 (f) が定値か均等かを確実に判定するためには、最悪の場合 $2^{n-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.
^ 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.

この項目は、数学に関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（プロジェクト:数学／Portal:数学）。

[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.

[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.

[1]

[2]

表話編歴量子コンピュータ
全般	量子コンピュータ量子力学
ハードウェア	超伝導イオントラップ型核磁気共鳴光子
アルゴリズム• プログラミング言語	量子プログラミング言語ドイッチュ・ジョサのアルゴリズムグローバーのアルゴリズムショアのアルゴリズム（英語版）
項目	量子ビット量子回路量子テレポーテーション量子暗号量子アニーリング量子状態量子もつれ量子超越性量子ウォーク量子情報
関連分野	量子情報科学情報工学
メーカー	IBM D-Wave Google
実機	九章
人物	ピーター・ショアロブ・グローバー（英語版）デイヴィッド・ドイッチュリチャード・ジョサ（英語版）
カテゴリ