第1章オラクルと位相オラクル — 道具の準備

この章の目標

1.1 ビットオラクル — 関数の可逆パッケージ

ステップ2第6章で、任意の古典関数 $f: \{0,1\}^n \to \{0,1\}$ は可逆回路（Toffoli等＋アンコンピュート）にできることを見ました。その標準形がビットオラクルです：

定義（ビットオラクル） $$U_f\, |x\rangle|y\rangle = |x\rangle|y \oplus f(x)\rangle$$

入力レジスタ $|x\rangle$（$n$ 量子ビット）は素通しで、答えは標的ビットにXORで追記される。$U_f U_f = I$（自己逆）。

アルゴリズムを学ぶ間、$U_f$ の中身は「作れることは保証済みのブラックボックス」として扱います。クエリ計算量（第0章）で数えるのはこの箱の使用回数です。

1.2 一様重ね合わせと $H^{\otimes n}$ の一般式

第1幕「広げる」の道具を式にしておきます。$|0\rangle^{\otimes n}$ に $H$ を並べると一様重ね合わせ： $$H^{\otimes n}|0\cdots 0\rangle = \frac{1}{\sqrt{2^n}}\sum_{x \in \{0,1\}^n} |x\rangle$$ さらに一般の基底状態 $|x\rangle$ に対しては次の美しい公式が成り立ちます（第3幕「畳む」でフル稼働します）：

アダマール変換の一般式 $$H^{\otimes n}|x\rangle = \frac{1}{\sqrt{2^n}}\sum_{z \in \{0,1\}^n} (-1)^{x \cdot z}\, |z\rangle \qquad x \cdot z = x_1 z_1 \oplus x_2 z_2 \oplus \cdots \oplus x_n z_n$$

$x \cdot z$ はビットごとのANDのXOR（内積 mod 2）。$n = 1$ で確認すると：$H|0\rangle = \frac{|0\rangle + |1\rangle}{\sqrt2}$（$x = 0$ なら符号は全部 $+$）、$H|1\rangle = \frac{|0\rangle - |1\rangle}{\sqrt2}$（$x = 1$ なら $z = 1$ の項が $-$）。確かに一致します。導出は演習1-3で。

1.3 位相オラクル — 答えを符号に変える

ステップ2問7-6のテクニックを $n$ ビットに一般化します。標的を $|-\rangle$ にして $U_f$ を通すと、キックバックにより：

位相オラクル $$U_f\, |x\rangle|-\rangle = (-1)^{f(x)}\, |x\rangle|-\rangle$$

標的は $|-\rangle$ のまま変わらないので省略して、入力レジスタだけの演算子として $$O_f\,|x\rangle = (-1)^{f(x)}|x\rangle$$ と書く。$f(x) = 1$ の成分の符号だけを反転する対角ユニタリである。

一様重ね合わせに $O_f$ を通すと、状態は $$\frac{1}{\sqrt{2^n}}\sum_x (-1)^{f(x)}|x\rangle$$ ——$f$ の全情報が符号のパターンとして1回のクエリで刻まれました。これが第2幕「刻む」の完成形です。ただし：

直観: 刻んだだけでは1ビットも読めない

符号は位相であり、各成分の測定確率 $\left|\pm\frac{1}{\sqrt{2^n}}\right|^2 = \frac{1}{2^n}$ は符号反転の前後でまったく変わりません（ステップ1第2章の教訓の総動員）。つまり $O_f$ 直後に測っても一様ランダムな $x$ が出るだけ。位相のパターンを確率のパターンに変換する第3幕——$H^{\otimes n}$ や QFT——があって初めて情報が取り出せます。「オラクル1回で全情報が刻める。しかし読み出しは干渉の設計次第」。量子アルゴリズムの難しさと面白さの全部がこの一文にあります。

実験1: 位相オラクルを見る（神の視点）

$n = 3$（8成分）の一様重ね合わせに位相オラクルを適用します。マークする $x$ をクリックで選んで「オラクル適用」を押すと、振幅の符号（色）が反転します。棒の高さ（＝測定確率）は何をしても変わらないことを確認してください。この「見えない刻印」を読むのが第2章以降の仕事です。

マークする x（クリックで切替）:
Qiskitで試す 
from qiskit import QuantumCircuit
from qiskit.quantum_info import Statevector

# f(x) = x0 AND x1 の位相オラクル（実は CZ そのもの）
qc = QuantumCircuit(2)
qc.h(0); qc.h(1)      # 一様重ね合わせ
qc.cz(0, 1)           # |11⟩ の符号だけ反転
print(Statevector.from_instruction(qc))
# [0.5, 0.5, 0.5, -0.5] — 符号は刻まれたが、確率は全部 0.25 のまま
$n = 2$ では「$|11\rangle$ をマークする位相オラクル」はCZゲートそのものです。ステップ2で学んだゲートが、アルゴリズムの文脈で別の顔を見せ始めます。

演習1

問 1-1ウォームアップ

$n = 2$、$f(x_1 x_2) = x_1 \wedge x_2$ とする。(a) ビットオラクル $U_f$ をステップ2の語彙で言うと何ゲートか。(b) 位相オラクル $O_f$ を4次元の対角行列として書け。

解答を見る

(a) Toffoli（CCNOT）そのもの：制御2本が $x$、標的が $y$。(b) $f = 1$ となるのは $x = 11$ のみなので $O_f = \mathrm{diag}(1, 1, 1, -1) = $ CZ。ビットオラクル＝Toffoli、位相オラクル＝CZ、という対応はきれいな最小例です。

問 1-2ウォームアップ

一様重ね合わせ $\frac12(|00\rangle + |01\rangle + |10\rangle + |11\rangle)$ に、$f(x) = x_1 \oplus x_2$（XOR）の位相オラクルを適用した状態を書け。この状態を標準基底で測定したときの分布は適用前と変わるか。

解答を見る

$f = 1$ となるのは $01, 10$。よって $\frac12(|00\rangle - |01\rangle - |10\rangle + |11\rangle)$。測定分布は各 $\frac14$ で不変。ちなみにこの状態、因数分解すると $\frac{(|0\rangle - |1\rangle)(|0\rangle - |1\rangle)}{2} = |-\rangle|-\rangle$ の符号違い——積状態です。符号パターンが状態の構造を大きく変えていることが、分解してみると見えます。

問 1-3基本

アダマール変換の一般式を $n = 2$ で導出せよ。すなわち $H \otimes H$ を $|x_1 x_2\rangle$ に適用し、$H|x_i\rangle = \frac{1}{\sqrt2}\sum_{z_i}(-1)^{x_i z_i}|z_i\rangle$ の積から $(-1)^{x \cdot z}$ の形が出ることを確かめよ。

解答を見る

$H|x_1\rangle \otimes H|x_2\rangle = \frac{1}{2}\sum_{z_1}\sum_{z_2}(-1)^{x_1 z_1}(-1)^{x_2 z_2}|z_1 z_2\rangle = \frac{1}{2}\sum_z (-1)^{x_1 z_1 + x_2 z_2}|z\rangle$。指数の和は $(-1)$ の偶奇しか効かないので mod 2 の内積 $x \cdot z$ に置き換えられる。一般の $n$ も全く同様（各ビットの因子の積）。「テンソル積の積が、指数の内積になる」——この計算パターンはQFT（第4章）でも再登場します。

問 1-4基本

一般式を使って $H^{\otimes 2}|11\rangle$ を展開せよ。また「$H^{\otimes n}|x\rangle$ の展開で符号が全部 $+$ になるのは $x = 0\cdots0$ のときだけ」であることを確認せよ。

解答を見る

$x = 11$: 符号は $(-1)^{z_1 \oplus z_2}$……ではなく $(-1)^{z_1 + z_2}$（$x_i$ が両方1なので $x \cdot z = z_1 \oplus z_2$）。展開すると $\frac12(|00\rangle - |01\rangle - |10\rangle + |11\rangle)$。$x = 00$ なら $x \cdot z = 0$ で全項 $+$、つまり一様重ね合わせ。逆に $x \ne 0$ なら約半分の項が $-$ になります。「符号が全部揃っている ⟺ 入力が $|0\cdots0\rangle$」——この対応を逆向きに使う（符号が揃った状態に $H^{\otimes n}$ を掛けると $|0\cdots0\rangle$ に戻る）のがDeutsch-Jozsaの読み出し原理です（第2章）。

問 1-5基本

位相オラクルの導出を自分の手で再現せよ：$U_f|x\rangle|-\rangle = (-1)^{f(x)}|x\rangle|-\rangle$ を、$f(x) = 0$ の場合と $f(x) = 1$ の場合に分けて示せ。

解答を見る

$f(x) = 0$: $|y \oplus 0\rangle = |y\rangle$ なので標的は不変、$|x\rangle|-\rangle$ のまま（$(-1)^0 = 1$ ✓）。$f(x) = 1$: 標的は $|y \oplus 1\rangle$ すなわち $X$ が作用し、$X|-\rangle = -|-\rangle$（ステップ2問1-4）。よって $-|x\rangle|-\rangle$（$(-1)^1$ ✓）。重ね合わせ $\sum_x c_x|x\rangle$ に対しては線形性で各項に符号が付く。ステップ2の位相キックバックそのもので、新しいことは何も起きていません——道具が揃っている感覚を確認してください。

問 1-6考え方

「位相オラクル1回で $f$ の全情報（$2^n$ ビット分の真理値表）が状態に刻まれる。よって量子コンピュータは1クエリで $f$ を完全に学習できる」——この主張の誤りを、ホレヴォ限界的な観点（$n$ 量子ビットの測定から取り出せる情報は最大 $n$ ビット）も踏まえて指摘せよ。

解答を見る

刻まれることは事実ですが、取り出せる量が別問題です。$n$ 量子ビットをどう測定しても得られる古典情報は高々 $n$ ビット（ホレヴォ限界）で、$2^n$ ビットの真理値表には遠く及びません。さらに測定すれば状態は壊れ、2回目の読み出しはありません（no-cloningでコピーも不可）。だからアルゴリズム設計の問いは常に「$f$ の全体から、どの $n$ ビット以下の性質を選んで浮かび上がらせるか」になります。Deutsch-Jozsaは「定数か否か」の1ビット、Bernstein-Vaziraniは隠れた $n$ ビット文字列、Shorは周期。どれも真理値表そのものではなく、巧妙に選ばれた「要約」であることに注目してください。

理解チェックリスト