ドイチュ–ジョザのアルゴリズム

「量子は本当に速いのか」への最初の答え

ドイチュ–ジョザのアルゴリズムは、量子計算が古典計算を明確に上回れることを、誤りゼロで示した最初の例です。実務で解きたい問題そのものではありませんが、後の ショアやグローバー を含むほぼすべての量子アルゴリズムが使う3つの道具——量子並列性・位相キックバック・干渉——が最小構成で凝縮されています。ここではその仕掛けを、なぜ1回の問い合わせで答えが出るのかまで分解します。

扱う問題はこうです。n ビットのビット列を入力に取り、0か1を返す関数 f があります。この f は次のどちらかであることが保証されています。

• 定数（constant）: すべての入力に対して同じ値を返す（常に0、または常に1）。
• 均衡（balanced）: 入力 2^n 個のうち、ちょうど半数で0、残り半数で1を返す。

f の中身は見えず、値を知るには「入力を与えて出力を得る」問い合わせ（オラクル）だけが許されます。どちらのタイプかを当てよ、というのが問題です。

道具1：量子並列性で全入力を一度に載せる

量子ビット n 個を、すべて |0> からアダマール変換 H にかけると、2^n 通りの入力すべての均等な重ね合わせが作れます。1量子ビットでは H|0> = (|0>+|1>)/√2 です。これを n 個並べると次のようになります。

H^⊗n |00…0> = (1/√(2^n)) Σ_x |x>    （x は 0 から 2^n−1 の全ビット列）

この1本の状態の中に、2^n 個の入力がすべて等しい振幅で含まれています。ここに f を1回作用させれば、原理的には全入力に対する f の評価が同時に進みます。これが量子並列性です。

ただし注意が必要です。重ね合わせに f を効かせても、そのまま測定すれば得られるのはランダムな1つの f(x) だけ。全部を一度に読み出すことはできません。並列に計算した結果を答えに変えるには、次の位相キックバックと干渉が要る——ここが「速そうに見えて実は難しい」核心です。

道具2：位相キックバックで f を位相に移す

量子オラクルは可逆でなければならないため、f は入力を壊さない形 U_f: |x>|y> → |x>|y ⊕ f(x)> で与えられます（⊕ は排他的論理和、y は補助の出力ビット）。素直に使うと f(x) は出力ビットに書き込まれますが、ここに巧妙な準備を施します。

出力ビットを |1> にしてから H をかけ、|−> = (|0>−|1>)/√2 にしておくのです。この状態に U_f を作用させると、次が成り立ちます。

U_f |x>|−> = |x> · (|0 ⊕ f(x)> − |1 ⊕ f(x)>)/√2
           = (−1)^f(x) · |x>|−>

f(x)=0 なら符号はそのまま、f(x)=1 なら符号が反転する——つまり f(x) の値が、出力ビットではなく |x> 側の「位相 (−1)^f(x)」として跳ね返って きます。これが位相キックバック（phase kickback）です。補助ビット |−> は最後まで変化せず、実質的に入力レジスタだけに (−1)^f(x) という符号が刻まれます。

重ね合わせ全体に効かせると、入力レジスタはこうなります。

(1/√(2^n)) Σ_x (−1)^f(x) |x>

各入力 x の振幅の符号に f(x) が乗った状態です。ここまでで f の情報はすべて位相に載りました。オラクル U_f を使った回数は1回だけです。

道具3：アダマール干渉で答えを1点に集める

最後に入力レジスタへ再び H^⊗n をかけ、全状態を干渉させます。アダマール変換の一般式を使うと、出力が |00…0>（全ビット0）である振幅は次のように書けます。

状態 |00…0> の振幅 = (1/2^n) Σ_x (−1)^f(x)

この和 Σ_x (−1)^f(x) が決定的に効きます。

• 定数のとき: すべての (−1)^f(x) が同符号なので、和は ±2^n。振幅は ±1、確率は1。測定すると必ず全ビット0 が得られる。
• 均衡のとき: +1 と −1 がちょうど半々で完全に打ち消し合い、和は0。振幅は0、確率は0。全ビット0 は絶対に観測されない。

したがって判定規則は明快です。測定結果が全ビット0なら定数、1ビットでも1が立っていれば均衡。干渉が「定数なら全確率を原点に集中、均衡なら原点の確率を完全に消す」という両極端を作り出すため、1回の測定で誤りなく確定します。

全体の流れと計算量

回路全体は「重ね合わせを作る → オラクルで位相を刻む → 干渉させて測る」という3段構成です。

|0>^n ─ H^⊗n ─┐              ┌─ H^⊗n ─ 測定（入力レジスタ）
              │   U_f (1回)   │
|1>   ─ H ────┘              └─ （|−> のまま・破棄）

問い合わせ回数の差が、このアルゴリズムの主張です。

まとめ

ドイチュ–ジョザのアルゴリズムは、量子並列性で全入力を重ね合わせ、位相キックバックで f を測れない位相に隠し、アダマール干渉でそれを1つの読み出しへ凝縮するという三段の流れそのものです。速さの正体は「たくさん計算するから」ではなく、位相に載せた情報を干渉で強め合わせ・打ち消し合わせて答えを1点に集められるから——ここが古典の総当たりと決定的に違います。実用性より原理の教材価値が高く、プログラミング 的な可逆回路の考え方や、AI で用いる線形代数（ユニタリ行列とテンソル積）に慣れていると、後続の量子アルゴリズムへの橋渡しがぐっと楽になります。