第0章ガイダンス — 量子アルゴリズムの3幕構成
この章の目標
- 「重ね合わせで並列計算」だけではなぜ勝てないのかを、もう一度明確にする
- 量子アルゴリズムに共通する3幕構成（広げる→刻む→畳む）を掴む
- 「何と比べて速いのか」（クエリ計算量）という土俵を理解する
0.1 素朴な戦略はなぜ負けるか
ステップ2までの道具で、次のことはすでにできます：$n$ 量子ビットに $H$ を並べて $2^n$ 通りの入力の一様重ね合わせを作り（第1章で復習）、可逆化した関数 $U_f$ を1回通せば、すべての $x$ に対する $f(x)$ が1回の実行で重ね合わせの中に計算されます： $$\frac{1}{\sqrt{2^n}}\sum_x |x\rangle|0\rangle \;\xrightarrow{U_f}\; \frac{1}{\sqrt{2^n}}\sum_x |x\rangle|f(x)\rangle$$ これが俗に言う「量子並列性」です。しかしここで測定すると、得られるのはランダムな1個の $x$ とその $f(x)$ だけ（ボルン則）。それなら古典で乱数を振って $f$ を1回評価するのと変わりません。ステップ1演習4-8、ステップ2第5章で確認した「状態の豊かさと取り出せる情報のギャップ」に、正面からぶつかるわけです。
重ね合わせの中の $2^n$ 個の値を全部読むことは絶対にできません。しかし、すべての振幅を干渉させて1つの測定結果に畳み込むことはできます。つまり量子アルゴリズムが取り出せるのは、個々の $f(x)$ ではなく「$f$ は定数か？」「どこにマークがあるか？」「$f$ の周期は？」といった大域的な性質です。「全部計算して全部読む」ではなく「全部を干渉させて、知りたい1つの性質だけ浮かび上がらせる」——この発想の転換がステップ3の全てです。
0.2 3幕構成 — 広げる・刻む・畳む
これから学ぶアルゴリズムは、驚くほど同じ形をしています：
| 幕 | やること | 使う道具 |
|---|---|---|
| 第1幕: 広げる | $H^{\otimes n}$ で一様重ね合わせを作り、全入力に足場を架ける | $H$（ステップ2第1章） |
| 第2幕: 刻む | オラクル・制御ユニタリで、答えの情報を位相に刻む | 位相キックバック（ステップ2第3章） |
| 第3幕: 畳む | $H^{\otimes n}$ またはQFTで位相パターンを干渉させ、答えを確率のピークに変換して測る | H–位相–H変換（ステップ2第2章）の一般化 |
Deutsch-Jozsaは第3幕が $H^{\otimes n}$、Shor系は第3幕がQFT。Groverは第2幕と第3幕を1セットにして繰り返す変奏です。新しく学ぶ数学はQFTまわりだけで、あとはステップ2の部品の組み合わせ——各章でこの3幕のどこにいるかを常に意識してください。
0.3 「速い」の土俵 — クエリ計算量
「量子は速い」と言うとき、何と何を比べているのか。この教材で扱うアルゴリズムの多くはオラクルモデルで語られます：関数 $f$ はブラックボックス（オラクル）として与えられ、$f$ を呼び出した回数（クエリ数）だけを数えます。
- Deutsch-Jozsa: 古典（決定的）$2^{n-1}+1$ 回 → 量子 1回
- Grover: 古典 $O(N)$ 回 → 量子 $O(\sqrt{N})$ 回
- Shor（の心臓部の周期発見）: 古典は既知の方法で準指数時間 → 量子 多項式時間
クエリ数の比較は数学的に厳密ですが、実用上の速さと同じではありません。オラクル1回の実行コスト、量子ビットの品質、エラー訂正のオーバーヘッド……現実の壁は第7章で正面から扱います。各章に「正直な評価」欄を置くのはこのためです。誇大にも悲観にも寄らず、「どの土俵で・何倍速いか」を言えるようになりましょう。
演習0
【ステップ2復習】次を何も見ずに再現できるか確認せよ。(a) $H^{\otimes 2}|00\rangle$ の展開、(b) 位相キックバック：標的が $|-\rangle$ のとき $U_f|x\rangle|-\rangle = (-1)^{f(x)}|x\rangle|-\rangle$ となる理由、(c) H–位相–H の一般式 $P(0) = \cos^2\frac{\phi}{2}$。
解答を見る
(a) $\frac12(|00\rangle + |01\rangle + |10\rangle + |11\rangle)$（ステップ1演習6-2）。(b) $f(x) = 0$ なら標的に何もせず、$f(x) = 1$ なら $X|-\rangle = -|-\rangle$（ステップ2問7-6）。(c) ステップ2問2-6。この3つがステップ3の「文法」です。どれかが怪しければステップ2の該当章を復習してから進んでください。
$n = 50$ とする。一様重ね合わせ $\frac{1}{\sqrt{2^{50}}}\sum_x |x\rangle|f(x)\rangle$ を作って測定する行為を1万回繰り返した。特定の入力 $x_0$ の値 $f(x_0)$ が一度でも観測される確率はおよそいくらか。「量子並列性で $2^{50}$ 通りを一度に計算した」という表現の実用上の意味を評価せよ。
解答を見る
1回の測定で $x_0$ が出る確率は $2^{-50} \approx 10^{-15}$。1万回でも $\approx 10^{-11}$ で、事実上観測されません。「一度に計算した」は状態ベクトルの記述としては正しくても、読み出せなければ計算したことにならない——素朴な並列性の価値はゼロに近い、というのが正直な評価です。この絶望からスタートして、干渉という唯一の抜け道を工夫するのがアルゴリズム設計です。
「干渉で浮かび上がらせられるのは大域的性質だけ」という制約を踏まえると、次のうち量子アルゴリズムによる高速化が期待しにくいのはどれか、直観で選び理由を述べよ。(a) 巨大な数の素因数分解（答え：周期という構造がある）(b) ソートされていないデータベースから条件に合う1件を探す（答え：構造なし）(c) 任意のプログラムの実行を単純に「速くする」
解答を見る
(c) です。(a) は周期性という強い数学的構造があり、指数的高速化が効きます（Shor）。(b) は構造がないぶん $\sqrt{N}$ どまりですが、それでも高速化はあります（Grover。しかも $\sqrt{N}$ が限界であることが証明済み）。(c) のような「何でも速くなる」は原理的な根拠がなく、実際、一般の計算の無条件な高速化は知られていません。問題の中に干渉で拾える構造があるかどうかが、量子で速くなるかの分かれ目——この感覚が「ニュースを判断できる」ことの中核です。