ドイチュ・ジョザをQiskitで実装する｜量子並列性を1回で使い切る

量子アルゴリズムが古典に勝つ様子を最短で体感できるのが ドイチュ・ジョザ（Deutsch-Jozsa） です。実用性より「なぜ量子は速いのか」を示す教材として最高。この記事ではQiskitで実装し、古典なら複数回・量子なら1回で答えを出すところまでやります。グローバー実装の前段にどうぞ。

何を解くのか

「入力すべてに同じ値を返す（定数関数）」か「入力の半分で0・半分で1を返す（均等関数）」か——どちらかと約束された関数を見分けます。

準備

pip install qiskit qiskit-aer

① オラクル（判定したい関数）

3入力ビットのオラクルを作ります。均等関数の例として「各入力ビットのXORを出力ビットに書き込む」回路を使います。

from qiskit import QuantumCircuit

def oracle_balanced(n):
    qc = QuantumCircuit(n + 1, name="balanced")
    for i in range(n):
        qc.cx(i, n)   # 各入力を出力ビットにXOR = 均等関数
    return qc

def oracle_constant(n):
    qc = QuantumCircuit(n + 1, name="constant")
    # 何もしない = 常に0を返す定数関数
    return qc

② ドイチュ・ジョザ本体

入力を重ね合わせ、出力ビットを|−⟩にしてオラクルを通し、最後にアダマールで戻して測定します。

from qiskit_aer import AerSimulator

def deutsch_jozsa(oracle, n):
    qc = QuantumCircuit(n + 1, n)
    qc.x(n); qc.h(n)          # 出力ビットを |−⟩ に
    qc.h(range(n))            # 入力を重ね合わせ
    qc.compose(oracle, inplace=True)
    qc.h(range(n))            # 戻す
    qc.measure(range(n), range(n))
    return AerSimulator().run(qc, shots=1000).result().get_counts()

n = 3
print("均等:", deutsch_jozsa(oracle_balanced(n), n))
print("定数:", deutsch_jozsa(oracle_constant(n), n))

結果は 均等関数なら 000 以外、定数関数なら 000 が100%。たった1回のオラクル呼び出しで、000が出るかどうかだけで判定できました。

まとめ

• ドイチュ・ジョザは「定数か均等か」をオラクル1回で見抜く
• 出力ビットを|−⟩にして位相キックバックを起こすのがキモ
• 000が出れば定数、それ以外なら均等
• 量子並列性＋干渉で古典を上回る最小例

もう少し詳しく（背景と理論）

ドイチュ・ジョザは、Deutsch (1985) の1量子ビット版を Deutsch & Jozsa (1992) が n ビットへ一般化したもので¹、量子が古典を確実に上回る最初の例として知られます。ただし確定的（決定的）な分離が示せるのは「関数が定数か均等か」と保証された特殊設定においてで、確率的な古典アルゴリズムを許すと差は縮まります²。それでも、位相キックバックとアダマール変換による干渉という基本部品は、後のバーンスタイン・ヴァジラニやサイモン、そしてショアへと受け継がれる本質的な発想です³。

次の一歩 🌸

探索の高速化はグローバー実装、アルゴリズム全体像は量子アルゴリズム入門、回路の基礎はQiskit入門へどうぞ。

Footnotes

1. Deutsch, D. & Jozsa, R. (1992). "Rapid solution of problems by quantum computation." Proc. R. Soc. Lond. A, 439, 553–558. オラクル1回で定数/均等を確定判定する。 ↩

2. 決定的古典アルゴリズムは最悪 2ⁿ⁻¹+1 回の問い合わせを要するが、誤り確率を許す確率的古典アルゴリズムなら数回のサンプリングで高確率に判定できる。DJの「指数的分離」は決定的計算に対するもの、という限定が付く。 ↩

3. この構造はサイモンのアルゴリズム（Simon, 1994）を経てショアの周期発見に繋がる。DJ 自体は実用問題ではないが、量子アルゴリズム設計の教科書的な出発点。 ↩