レッスン6：量子アルゴリズム

Deutsch-Jozsa（関数の判定）と Grover（検索）を、実際に回路を組んで体感する

量子アルゴリズム

重ね合わせ・もつれ・干渉を組み合わせると、古典コンピュータより速く解ける問題が出てきます。 最後のレッスンでは、代表的な 2 つのアルゴリズムを、実際に回路を組んで体感しましょう。

アルゴリズム できること 古典との差
Deutsch-Jozsa 関数が「定数」か「バランス」かを判定 古典 \(2^{n-1}+1\) 回 → 量子 1 回
Grover データベースから目的の項目を探す 古典 \(O(N)\) → 量子 \(O(\sqrt{N})\)

Deutsch-Jozsa：たった1回の質問で見抜く

問題：\(f\) は 0 → 0/1、1 → 0/1 の関数。\(f\) が「定数」（\(f(0)=f(1)\)）か「バランス」（\(f(0)\neq f(1)\)）かを判定したい。

古典では最悪 2 回 関数を呼ぶ必要があります。量子では、関数をブラックボックス（oracle）として 1 回だけ 呼ぶだけで判定できます。

仕組みを試しましょう。関数を選ぶと、上の回路を組んで測定します。q0 の測定結果が 0 なら定数、1 ならバランスです。

判定結果：バランス関数 （q0 が 1 ならバランス、0 なら定数）
Tip

見てみよう - f(x)=0 や f(x)=1（定数）を選ぶと、q0 は 必ず 0。 - f(x)=x や f(x)=1⊕x（バランス）を選ぶと、q0 は 必ず 1。 - 関数を 1 回だけ呼ぶだけで、古典の 2 回と同等以上の判定ができています。

Grover：データベースから一発で見つける

4 個の箱（00〜11）の中から、目的の箱を探す問題を考えます。古典なら平均 2〜3 回 開けないといけませんが、 Grover アルゴリズムは1 ステップで確率をほぼ 100% に引き上げます。

仕組みは「目的の振幅を増幅」すること： 1. 全部の箱を重ね合わせにする 2. オラクルで目的の箱の符号を反転 3. 拡散（平均まわりの反転）で、目的の箱の振幅を増幅 4. 測定 → 目的の箱が出やすい！

Tip

見てみよう - どのターゲットを選んでも、測定するとほぼ必ずその箱が出ます。 - 「振幅の増幅」によって、4 箱の中から 1 ステップ で特定できるのが Grover の力です。 - 箱の数が 100 万個になっても、Grover は古典の \(\sqrt{N}\) 倍速（約 1,000 回）で探せます。

まとめ

  • Deutsch-Jozsa：定数/バランス判定を 1 回のクエリで行う。
  • Grover：検索を \(O(\sqrt{N})\) で行う「振幅増幅」アルゴリズム。
  • 両者に共通するのは「重ね合わせで可能性を広げ、干渉で目的の振幅を増幅する」という量子の力。

これで 6 レッスンは完了です。あとは ワークシート で復習し、「自分のPCで試す」ページの Qiskit ノートブックで、実際の量子 SDK にも触れてみましょう。