第2章Deutsch-JozsaとBernstein-Vazirani — 干渉で答えを読む

この章の目標

2.1 問題設定（約束付き問題）

Deutsch-Jozsa問題

$f: \{0,1\}^n \to \{0,1\}$ が次のどちらかであることが約束されている：

どちらかを判定せよ。古典の決定的アルゴリズムは最悪 $2^{n-1} + 1$ 回のクエリが必要（半分＋1個まで同じ値が続いても、まだ確定しない）。量子は1回で確定判定する。

2.2 回路と計算 — 3幕をそのまま実行する

|0⟩ ──[H]──┐          ┌──[H]──[M]══
|0⟩ ──[H]──┤   O_f    ├──[H]──[M]══   全ビットが0 → 定数
  ⋮         │ (位相)   │    ⋮          それ以外   → バランス
|0⟩ ──[H]──┘          └──[H]──[M]══

第1幕（広げる）：$H^{\otimes n}|0\cdots0\rangle = \frac{1}{\sqrt{2^n}}\sum_x |x\rangle$。

第2幕（刻む）：位相オラクルで $\frac{1}{\sqrt{2^n}}\sum_x (-1)^{f(x)}|x\rangle$。

第3幕（畳む）：$H^{\otimes n}$ を掛け、第1章の一般式 $H^{\otimes n}|x\rangle = \frac{1}{\sqrt{2^n}}\sum_z (-1)^{x \cdot z}|z\rangle$ を代入： $$\text{最終状態} = \sum_z \left[\frac{1}{2^n}\sum_x (-1)^{f(x) + x \cdot z}\right] |z\rangle$$

各 $|z\rangle$ の振幅が角括弧の中です。特に $z = 0\cdots0$ の振幅（$x \cdot z = 0$）を見ると： $$c_{0\cdots0} = \frac{1}{2^n}\sum_x (-1)^{f(x)} = \begin{cases} \pm 1 & f \text{ が定数（全項が同符号で満額回収）} \\ 0 & f \text{ がバランス（}+1\text{ と }-1\text{ が正確に半々で全滅）} \end{cases}$$

直観: 多数決ではなく「全会一致か、真っ二つか」

$|0\cdots0\rangle$ の振幅は「全成分の符号の平均」です。定数なら符号が全会一致で振幅 $\pm1$（確率1）、バランスなら符号がちょうど半々で完全に打ち消し合い振幅0（確率0）。測定結果が全ビット0なら定数、1が混ざればバランス——確率1で判定完了、クエリは1回。第1章の実験1で「見えない」はずだった符号のパターンが、$H^{\otimes n}$ という干渉装置を通した瞬間に、くっきりした確率の差になって現れました。これが「干渉で答えを浮かび上がらせる」の完全な最小例です。

2.3 Bernstein-Vazirani — 隠れた文字列を1回で抜く

同じ回路を1文字も変えずに別の問題に使えます。$f(x) = s \cdot x$（未知の $n$ ビット列 $s$ との内積 mod 2）と約束されているとき、$s$ を求めたい。古典では1クエリごとに1次方程式が1本手に入るだけなので$n$ 回必要。量子では最終状態の $|z\rangle$ の振幅が $$c_z = \frac{1}{2^n}\sum_x (-1)^{s \cdot x + x \cdot z} = \frac{1}{2^n}\sum_x (-1)^{x \cdot (s \oplus z)} = \begin{cases} 1 & z = s \\ 0 & z \ne s \end{cases}$$ （総和の消滅は演習2-3で証明します）。つまり測定すると確率1で $s$ がそのまま出てきます。1クエリで $n$ ビットの答え——ホレヴォ限界（$n$ 量子ビットから最大 $n$ ビット）を目一杯使い切る、気持ちのよい設計です。

実験2: Deutsch-Jozsa / Bernstein-Vazirani シミュレータ（n = 3）

オラクルの $f$ を選んで実行すると、最終状態の測定分布が出ます。定数なら $000$ に全確率が集中し、バランスなら $000$ の確率が厳密に0になること、BV型（$f = s \cdot x$）では $s$ そのものにピークが立つことを確認してください。

正直な評価

Deutsch-Jozsaの「指数的高速化」は決定的（誤り確率ゼロ）アルゴリズム同士の比較です。古典でも乱択なら、数回のサンプルで誤り確率を好きなだけ小さくできます（$k$ 回一致を見れば誤り $2^{-k+1}$ 以下）。つまり実用的な差はほぼありません。それでもこのアルゴリズムが重要なのは、(1) 干渉による読み出しの設計図を最小構成で示したこと、(2) この設計図がGrover・Shorという「乱択でも勝てない」本物の高速化に発展したこと。Bernstein-Vaziraniの $n$ 倍高速化は乱択古典に対しても成り立ちます。「何と比べて速いか」を言い分けられること——これがこの欄の練習です。

Qiskitで試す 
from qiskit import QuantumCircuit
from qiskit_aer import AerSimulator

n = 3; s = "101"                      # BV: 隠れた文字列
qc = QuantumCircuit(n + 1, n)
qc.x(n); qc.h(n)                      # 標的を |−⟩ に
for i in range(n): qc.h(i)            # 第1幕
for i, bit in enumerate(reversed(s)): # 第2幕: f = s·x のオラクル
    if bit == "1": qc.cx(i, n)        #   （s_i = 1 のビットから標的へCNOT）
for i in range(n): qc.h(i)            # 第3幕
qc.measure(range(n), range(n))
print(AerSimulator().run(qc, shots=100).result().get_counts())
# → {'101': 100} — 1クエリで s がそのまま出る

演習2

問 2-1ウォームアップ

$n = 1$（Deutschのアルゴリズム、ステップ2問7-6）を2.2節の一般式で解き直せ：$c_0 = \frac12\big((-1)^{f(0)} + (-1)^{f(1)}\big)$ を4通りの $f$ について評価し、定数⇔$c_0 = \pm1$、バランス⇔$c_0 = 0$ を確認せよ。

解答を見る

$f \equiv 0$: $c_0 = 1$。$f \equiv 1$: $c_0 = -1$（確率はどちらも1）。$f(x) = x$: $\frac12(1 - 1) = 0$。$f(x) = \bar{x}$: $\frac12(-1 + 1) = 0$。ステップ2で回路を直接追った結果と一致します。一般式は「手計算の答えを整理棚に入れたもの」——先に手を動かしたからこそ、式が読める状態になっています。

問 2-2ウォームアップ

$n = 2$、バランス関数 $f(x_1 x_2) = x_1$ でDeutsch-Jozsaを実行する。第2幕後の状態と、第3幕後の最終状態を具体的に計算し、測定結果を予言せよ。

解答を見る

第2幕後：$\frac12(|00\rangle + |01\rangle - |10\rangle - |11\rangle)$（$x_1 = 1$ の項が反転）。因数分解すると $\frac{(|0\rangle - |1\rangle)}{\sqrt2} \otimes \frac{(|0\rangle + |1\rangle)}{\sqrt2} = |-\rangle|+\rangle$。第3幕 $H \otimes H$ で $|1\rangle|0\rangle = |10\rangle$。測定結果は確率1で 10——0でないので「バランス」と正しく判定（しかも $10$ は $s = 10$、つまり $f = s \cdot x$ の $s$ が出ている：BVの視点）。符号パターンが積状態に分解できたおかげで、干渉の行き先が1点に定まる様子がよく見えます。

問 2-3基本

【消滅補題】$a \ne 0\cdots0$ のとき $\sum_{x \in \{0,1\}^n} (-1)^{x \cdot a} = 0$ を証明せよ。ヒント: $a$ のあるビット $a_i = 1$ に注目し、$x$ を「$x_i = 0$ の組」と「$x_i = 1$ の組」にペア分けする。この補題がBVの式 $c_z = \delta_{z,s}$ を完成させることを確認せよ。

解答を見る

$a_i = 1$ なるビット $i$ を取る。任意の $x$ に対し、$x$ と「$x$ の第 $i$ ビットだけ反転した $x'$」をペアにすると、$x \cdot a$ と $x' \cdot a$ は第 $i$ ビットの寄与だけ違うので偶奇が逆、つまり $(-1)^{x \cdot a} + (-1)^{x' \cdot a} = 0$。全体は $2^{n-1}$ 組のペアの和なので $0$。$\blacksquare$ BVでは $a = s \oplus z$：$z = s$ なら $a = 0$ で総和 $2^n$（$c_s = 1$）、$z \ne s$ なら補題により $0$。「半分が $+$、半分が $-$ で厳密に消える」——量子アルゴリズムの証明はほとんどこの型の消滅計算でできています。

問 2-4基本

$f(x) = s \cdot x$（$s = 101$）のビットオラクルを、CNOTだけで構成せよ（Qiskitコラムのコードを手で導出する）。なぜ $s_i = 1$ のビットからだけCNOTを張ればよいのか。

解答を見る

$s \cdot x = x_1 \oplus x_3$（$s = 101$ の1が立つ位置）。XORはCNOTの標的への追記そのもの（ステップ2第6章）なので、$x_1$ と $x_3$ のワイヤから標的 $y$ へCNOTを1本ずつ張れば $y \oplus x_1 \oplus x_3$ が計算されます。$s_i = 0$ のビットは和に寄与しないので何も張らない。オラクルは魔法の箱ではなく、ステップ2の可逆回路の練習問題だと確認できる例です。

問 2-5基本

実験2の「多数決」関数（3ビット中2ビット以上が1なら1）はバランス関数である（8入力中ちょうど4つで1）。Deutsch-Jozsa回路にかけたとき、(a) $000$ の測定確率、(b) 測定分布が単一ピークにならない理由、を述べよ。(b) はBV型（$f = s \cdot x$）との違いに注目。

解答を見る

(a) バランスなので $c_{000} = 0$、確率0。判定は正しく「バランス」になる。(b) BV型の $f$ は符号パターンが $(-1)^{s \cdot x}$ という「きれいな縞模様」なので、干渉後の振幅が1点 $|s\rangle$ に完全集中します。多数決は線形関数でない（$s \cdot x$ の形に書けない）ため符号パターンが縞模様にならず、エネルギーが複数の $z$ に分散します（実験2で確認できます：$001, 010, 100$ 等に分布）。「オラクルの構造」と「干渉後のピークの形」が対応する——この対応の最も豊かな形が、周期構造→QFTピーク（第4章）です。

問 2-6考え方

古典乱択アルゴリズム「ランダムに $k$ 個の入力を選んで $f$ を評価し、全部同じ値なら『定数』と答える」の誤り確率を評価せよ（$f$ がバランスのとき、$k$ 個全部が偶然同じ値になる確率）。$k = 20$ でどうなるか。この結果を踏まえ、「Deutsch-Jozsaは古典より指数的に速い」という表現の正確な言い方を書け。

解答を見る

バランスなら各評価は独立にほぼ半々なので、$k$ 個一致の確率は約 $2 \cdot 2^{-k} = 2^{-k+1}$。$k = 20$ で約 $2 \times 10^{-6}$——実用上、古典乱択は20クエリで十分です。正確な言い方：「誤り確率ゼロを要求する決定的計算モデルにおいて、量子1クエリ vs 古典 $2^{n-1}+1$ クエリの分離がある」。乱択を許すと分離はほぼ消えます。論文やニュースの「指数的高速化」は、比較対象のモデル（決定的か乱択か、オラクルか実問題か）を確認しないと評価できない——第7章のニュース読解で使う視点の第一号です。

問 2-7考え方

Deutsch-Jozsa回路の第3幕を省略して（オラクル直後に）測定すると、定数の場合とバランスの場合で測定分布に差はあるか。この問いへの答えが、第0章の3幕構成の「畳む」の必要性をどう裏付けるか述べよ。

解答を見る

差はありません。どちらも振幅の絶対値はすべて $\frac{1}{\sqrt{2^n}}$ で、分布は一様（第1章の実験1で見た通り、符号は確率に出ない）。定数とバランスの違いは符号の相対的なパターンだけにあり、それを確率差に変換するのが第3幕の $H^{\otimes n}$ です。「オラクルを通した状態をそのまま測ればいいのでは？」という自然な発想が正確に潰されることで、干渉パートこそがアルゴリズムの本体だと確認できます。以降のGrover（拡散演算子）もShor（QFT）も、第3幕の設計こそが発明の中身です。

理解チェックリスト