設計された干渉としてのアルゴリズム

アリス、アルゴリズム劇場へ入る

劇場は静かですが、アリスはすべての経路に振幅があり、すべての振幅に符号や位相があることに気づきます。量子アルゴリズムは、魔法の並列試行ではありません。最後に測定したとき、有用な経路が強まり、不要な経路が打ち消されるように作る、設計された干渉です。

前提の復習

相対位相、H、テンソル積、制御操作を使います。新しい道具はオラクルです。オラクルとは、約束された関数や印づけられた項目を符号化するユニタリなブラックボックスです。

オラクルで考える

オラクル問題は、漠然とした現実世界の課題ではありません。次を指定します。

1. どのブラックボックス操作が使えるか。
2. 隠れた関数がどの約束条件を満たすか。
3. どの性質を判定するか。
4. 何回のオラクル問い合わせを数えるか。

位相キックバック

関数オラクルを

とします。第2レジスタを $|-\rangle=(|0\rangle-|1\rangle)/\sqrt{2}$ に準備すると、オラクルは $|x\rangle$ 成分の位相を変えます。

出力値が符号として現れます。その後のアダマールにより、符号パターンを測定確率の違いへ変換できます。これが位相キックバックです。

Deutsch-Jozsa

Deutsch-Jozsa 問題では、約束されたブール関数が定数関数かバランス関数かを判定します。理想的なオラクルモデルでは、量子回路は1回の問い合わせでその性質を判定できます。すべての値を一覧として読んでいるからではありません。位相キックバックが重ね合わせへ入力依存の相対符号パターンを書き込み、最後のアダマールが定数関数では全ゼロ結果を出し、バランス関数では全ゼロを消すからです。定数関数で全成分に共通する符号は大域位相にすぎませんが、バランス関数では入力間の符号が異なります。

$n$ ビット入力では、厳密な決定論的古典ブラックボックス・アルゴリズムは最悪の場合 $2^{n-1}+1$ 回の問い合わせを必要としますが、Deutsch-Jozsa は約束の下で1回の量子問い合わせを使います。これはオラクル問い合わせ計算量の差であり、すべての物理実行時間が指数的に短いという主張ではありません。誤りを許すランダム化古典アルゴリズムは少数の標本で両者を識別できるため、比較では厳密判定か有界誤差かも明示する必要があります。

Grover の直感

Grover 探索は、印づけられた項目の振幅を増幅します。4項目の場合、最初の振幅はすべて $1/2$ です。項目3が印づけられているなら、オラクルはその振幅を $-1/2$ に反転します。拡散ステップは、振幅を平均まわりに反射します。符号反転後の平均は

です。各振幅 $a$ を平均 $\bar a$ のまわりに反射すると $2\bar a-a$ になります。印のない振幅は0、印づけられた振幅は1になり、この小さな理想例では1回の反復で確率1になります。

標的が1つの場合、Grover はオラクル問い合わせ回数をおおよそ $O(N)$ から $O(\sqrt{N})$ へ改善します。より一般に、既知の $M>0$ 個の標的があるとき、振幅増幅は高い確率で1つを見つけるために $O(\sqrt{N/M})$ 回のオラクル呼び出しを使います。特に $M$ が未知なら、定数係数、停止規則、成功確率も重要です。強力ですが指数高速化ではなく、オラクル構成やフォールトトレラント回路のコストが消えるわけでもありません。

計算例：位相から答えへ

1ビット均衡関数 $f(0)=0$, $f(1)=1$ では、位相キックバックが $|+\rangle$ を $|-\rangle$ に変え、最後の H が $|-\rangle$ を $|1\rangle$ に写します。定数関数では両振幅が同じ符号を受けるため、入力は大域位相を除いて $|+\rangle$ のままで、最後の H は $|0\rangle$ を作ります。回路が得るのは約束された性質であり、両方の関数値を読出し可能な一覧にしたものではありません。

よくある誤解

ガイド付き演習

1ビット定数関数と1ビット均衡関数を1つずつ選び、それぞれの位相因子 $(-1)^{f(0)}$ と $(-1)^{f(1)}$ を書いてから、概念的に H を適用します。次に Grover の主張を監査し、$N$、標的数、オラクル費用、問い合わせ回数、必要成功確率を列挙してください。

章末評価

約束条件を述べ、位相符号を追跡し、Deutsch-Jozsa の最終測定を説明し、4項目 Grover の振幅更新を計算できるようにしましょう。

まとめ

次の一歩

理想アルゴリズムを現実と照合できる精度で説明できるようになりました。第8章ではチャネル、デコヒーレンス、シンドローム抽出、フォールトトレラント量子計算の資源前提を扱います。

参考文献と発展学習

• David Deutsch and Richard Jozsa, "Rapid Solution of Problems by Quantum Computation".
• Lov K. Grover, "A Fast Quantum Mechanical Algorithm for Database Search".
• IBM Quantum Learning, The Deutsch-Jozsa algorithm および Unstructured search.