SIP第3期量子技術課題「教育プログラムの開発と実践」教育コースプログラム「量子技術入門コース」の第八講に参加してきました。

https://skillup-next.co.jp/sip_3period_01

今回は第七講に続いて量子アルゴリズムを扱う内容で、ショアのアルゴリズムのほかに、グローバーのアルゴリズムや HHL アルゴリズムが登場しました。こういったアルゴリズムはどうやって動作するのでしょうか？以下では、そうしたアルゴリズムを動かしている「量子回路」を、実際にどう組むのかをご紹介します。

---

量子回路は「行列の掛け算」である

第七講の記事は、ショアのアルゴリズムを Mathematica 上で動かし、\(N = 15\) を \(3 \times 5\) に分解しました。記事の中では、10量子ビットの回路図と、間隔16できれいに並んだ4本の測定ピークをお見せしています（図3とその下の表）。

ただ、第七講でお見せしたのは結果だけでした。あの回路はどう書かれていて、中で何が計算されているのか。今回はそこを検証していきます。

先に結論を書いておきます。

量子回路とは、ベクトルに行列を順番に掛けていく計算のことです。

量子ビットの状態はベクトル、ゲートは行列、回路はその行列の積です。量子コンピュータが「何か神秘的な計算をしている」わけではありません。やっていることは線形代数そのものです。

では、なぜ普通のコンピュータではできないのか。第七講の最後に見たとおり、ベクトルの次元が量子ビット数に対して指数関数的に増えるからです（図4　古典（GNFS）とショアで必要な演算・ゲートの数）。\(n\) 量子ビットなら \(2^n\) 次元になります。第七講の 247 の分解では16量子ビット、つまり65,536次元のベクトルを扱っていました。50量子ビットにもなれば、古典計算機ではベクトルを並べることすら困難です。

裏返せば、数量子ビットの小さな回路なら、手元のパソコンでも再現できるということです。原理を確かめるにはこれで十分です。

本記事では、回路図と行列だけを使って、量子回路の中で何が起きているかを追っていきます。

---

1量子ビット：状態はベクトル、ゲートは行列

状態

1量子ビットの状態は、2成分のベクトルです。

\[|0\rangle = \begin{pmatrix}1\\0\end{pmatrix}, \qquad |1\rangle = \begin{pmatrix}0\\1\end{pmatrix}\]

\(|0\rangle\) や \(|1\rangle\) はブラケット記法（ケット）と呼ばれる書き方で、これまでの回ではこの記法のまま計算してきました。今回は記事のテーマに合わせて、ケットは「このベクトルの名前」としてだけ使い、計算はすべてベクトルと行列で行います。

2つの成分を同じ重みで持つ状態もあります。

\[|+\rangle = \frac{1}{\sqrt{2}}\begin{pmatrix}1\\1\end{pmatrix}\]

\(|0\rangle\) の成分と \(|1\rangle\) の成分を同じ重みで持っているので、「\(|0\rangle\) と \(|1\rangle\) の重ね合わせ」と呼ばれます。

係数の \(\frac{1}{\sqrt2}\) は、成分の2乗の和が 1 になるように付けたものです（\(\left(\frac{1}{\sqrt2}\right)^2 + \left(\frac{1}{\sqrt2}\right)^2 = 1\)）。これを規格化と呼びます。後の測定の節で見るとおり、量子ビットを測ったときに各結果が出る確率は成分（振幅）の2乗なので、規格化しておくと確率の合計がちょうど 1 になります。

ゲート

1量子ビットに対する量子ゲートは 2×2 の行列です。代表格のアダマールゲート \(H\) は次の行列です。

\[H = \frac{1}{\sqrt{2}}\begin{pmatrix}1 & 1\\ 1 & -1\end{pmatrix}\]

これを \(|0\rangle\) に作用させると、

\[H|0\rangle = \frac{1}{\sqrt{2}}\begin{pmatrix}1 & 1\\ 1 & -1\end{pmatrix}\begin{pmatrix}1\\0\end{pmatrix} = \frac{1}{\sqrt{2}}\begin{pmatrix}1\\1\end{pmatrix} = |+\rangle\]

「ゲートを作用させる」とは、行列をベクトルに掛けることです。

結果の \(\frac{1}{\sqrt2}(1, 1)^T\) も、ちゃんと規格化されています。量子ゲートの行列は、規格化されたベクトルを必ず規格化されたベクトルに移すように作られていて、このような行列をユニタリ行列と呼びます。

式で書くと、ユニタリ行列 \(U\) は \(UU^\dagger = I\) を満たす行列です（\(U^\dagger\) は \(U\) を転置して複素共役をとったもの、\(I\) は単位行列）。\(H\) の前の \(\frac{1}{\sqrt2}\) もこのための係数で、これがないと

\[\begin{pmatrix}1&1\\1&-1\end{pmatrix}\begin{pmatrix}1&1\\1&-1\end{pmatrix}^{\dagger} = \begin{pmatrix}2&0\\0&2\end{pmatrix} = 2I\]

となり、ベクトルの長さが変わってしまいます。実際、係数なしの行列を \(|0\rangle\) に掛けると \((1, 1)^T\) になり、2乗の和が 2 になります。状態の \(\frac{1}{\sqrt2}\) とゲートの \(\frac{1}{\sqrt2}\) は、同じ理由で付いているのです。

よく使う1量子ビットゲートを並べておきます。

名前	行列	何をするか
X	\(\begin{pmatrix}0&1\\1&0\end{pmatrix}\)	\(\lvert 0\rangle\) と \(\lvert 1\rangle\) を入れ替える（古典の NOT）
Y	\(\begin{pmatrix}0&-i\\i&0\end{pmatrix}\)	入れ替えと位相反転を同時に行う
Z	\(\begin{pmatrix}1&0\\0&-1\end{pmatrix}\)	\(\lvert 1\rangle\) の符号だけを反転する
H	\(\frac{1}{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix}\)	重ね合わせを作る・ほどく
S	\(\begin{pmatrix}1&0\\0&i\end{pmatrix}\)	\(\lvert 1\rangle\) に位相 \(i\) を付ける
T	\(\begin{pmatrix}1&0\\0&e^{i\pi/4}\end{pmatrix}\)	\(\lvert 1\rangle\) に位相 \(e^{i\pi/4}\) を付ける

回路：H を2回かけると元に戻る

ゲートを並べたものが回路です。\(H\) を2回続けてかける回路を考えます。

回路全体は、ゲートの行列を掛け合わせた1つの行列になります。

\[HH = \frac{1}{2}\begin{pmatrix}1&1\\1&-1\end{pmatrix}\begin{pmatrix}1&1\\1&-1\end{pmatrix} = \begin{pmatrix}1&0\\0&1\end{pmatrix} = I\]

単位行列 \(I\) になりました。入力が何であっても、この回路は何もしなかったのと同じです。なお \(H\) は実数の対称行列なので \(H^\dagger = H\) で、この \(HH = I\) は、先ほどの \(H\) がユニタリであるという条件 \(HH^\dagger = I\) そのものでもあります。

これは当たり前に見えて、実は量子計算の急所を含んでいます。1回目の \(H\) で \(|0\rangle\) は \(|0\rangle\) と \(|1\rangle\) の重ね合わせになるのに、2回目の \(H\) で \(|1\rangle\) の成分がきれいに消えて元に戻るからです。

なぜ消えるのかは、行列の掛け算の中身を見るとわかります。行列の \(i\) 行 \(j\) 列の成分 \(H_{ij}\) は、「\(|j\rangle\) から出発して \(|i\rangle\) に着く」振幅です（\(i, j\) は 0 か 1）。\(H\) を2回かけて \(|0\rangle\) から \(|1\rangle\) に着く振幅 \((HH)_{10}\) は、行列の積の定義どおりに書くと、

\[(HH)_{10} = \underbrace{H_{10}\,H_{00}}_{0\ \to\ 0\ \to\ 1} \;+\; \underbrace{H_{11}\,H_{01}}_{0\ \to\ 1\ \to\ 1} = \frac{1}{\sqrt2}\cdot\frac{1}{\sqrt2} \;+\; \left(-\frac{1}{\sqrt2}\right)\cdot\frac{1}{\sqrt2} = \frac12 – \frac12 = 0\]

です。\(|0\rangle\) から \(|1\rangle\) へ行くには、途中で \(|0\rangle\) を通る経路と、途中で \(|1\rangle\) を通る経路の2本があります。行列の積は、この2本の経路の振幅を足し合わせる計算になっていて、2本目の経路には行列の右下の \(-1\) が入るので、ちょうど打ち消し合って 0 になります。これが干渉です。確率は負になれませんが、振幅は負になれる。だから打ち消し合える。量子アルゴリズムとは、要らない答えの振幅を打ち消し、欲しい答えの振幅を強め合わせる回路を設計することだと言ってしまってもいいくらいです。第七講のショアで逆量子フーリエ変換がくしの歯の位置だけにピークを立てたのも、この干渉の仕業でした。

---

2量子ビットと「もつれ」

回路

量子ビットが2本になると、いよいよ量子らしい現象が出てきます。ベル状態と呼ばれる、2量子ビットがもつれ合った状態を作る回路です。

CNOT（制御 NOT）は、制御ビットが \(|1\rangle\) のときだけ標的ビットを反転するゲートです。

\[|00\rangle \to |00\rangle,\quad |01\rangle \to |01\rangle,\quad |10\rangle \to |11\rangle,\quad |11\rangle \to |10\rangle\]

ケットの中は左が量子ビット1、右が量子ビット2です。

2量子ビットの状態ベクトル

2量子ビットの状態をベクトルで書いておきます。1量子ビットでは2成分でしたが、2量子ビットでは4成分になり、4つの基底がそれぞれ1つの成分に対応します。

\[|00\rangle = \begin{pmatrix}1\\0\\0\\0\end{pmatrix},\quad |01\rangle = \begin{pmatrix}0\\1\\0\\0\end{pmatrix},\quad |10\rangle = \begin{pmatrix}0\\0\\1\\0\end{pmatrix},\quad |11\rangle = \begin{pmatrix}0\\0\\0\\1\end{pmatrix}\]

並び順は、ケットの中身を2進数として読んだ順（00 → 01 → 10 → 11、つまり 0, 1, 2, 3）です。\(|01\rangle\) は「量子ビット1が \(|0\rangle\)、量子ビット2が \(|1\rangle\)」という状態で、1量子ビットのベクトル同士のテンソル積として作れます。

\[|01\rangle = |0\rangle \otimes |1\rangle = \begin{pmatrix}1\\0\end{pmatrix} \otimes \begin{pmatrix}0\\1\end{pmatrix} = \begin{pmatrix}1\cdot\begin{pmatrix}0\\1\end{pmatrix}\\[4pt] 0\cdot\begin{pmatrix}0\\1\end{pmatrix}\end{pmatrix} = \begin{pmatrix}0\\1\\0\\0\end{pmatrix}\]

左のベクトルの各成分に、右のベクトル全体を掛けて縦に積む、という計算です。量子ビットが1本増えるたびにこの積が1回増え、ベクトルの長さが2倍になります。

CNOT の行列

CNOT を行列で書くと 4×4 になります。

\[\text{CNOT} = \left(\begin{array}{cc|cc} 1&0&0&0\\ 0&1&0&0\\ \hline 0&0&0&1\\ 0&0&1&0 \end{array}\right) = \begin{pmatrix} I & 0 \\ 0 & X \end{pmatrix}\]

行と列は上から（左から）\(|00\rangle, |01\rangle, |10\rangle, |11\rangle\) の順です。2×2 ずつの区画に分けて見ると、構造がよくわかります。左上の区画は制御ビットが 0 の部分で、単位行列 \(I\)、つまり何もしません。右下の区画は制御ビットが 1 の部分で、X ゲートそのものです。「制御ビットが1のときだけ X をかける」という言葉が、そのまま行列の形になっています。

行列で追う

では、図2の回路を行列で計算します。ここからは入力を決めて、状態がどう変わるかを追います。入力は \(|00\rangle\) です。

「量子ビット1に \(H\)、量子ビット2には何もしない」という操作は、\(H\) と単位行列 \(I\) のテンソル積（クロネッカー積）\(H \otimes I\) です。これと CNOT を順に \(|00\rangle\) に掛けると、

\[\underbrace{\begin{pmatrix}1&0&0&0\\0&1&0&0\\0&0&0&1\\0&0&1&0\end{pmatrix}}_{\text{CNOT}}\ \underbrace{\frac{1}{\sqrt2}\begin{pmatrix}1&0&1&0\\0&1&0&1\\1&0&-1&0\\0&1&0&-1\end{pmatrix}}_{H\otimes I}\ \underbrace{\begin{pmatrix}1\\0\\0\\0\end{pmatrix}}_{|00\rangle} = \frac{1}{\sqrt2}\begin{pmatrix}1\\0\\0\\1\end{pmatrix}\]

\[= \frac{1}{\sqrt2}\left[\ \underbrace{\begin{pmatrix}1\\0\end{pmatrix}\otimes\begin{pmatrix}1\\0\end{pmatrix}}_{\text{両方 0}} \;+\; \underbrace{\begin{pmatrix}0\\1\end{pmatrix}\otimes\begin{pmatrix}0\\1\end{pmatrix}}_{\text{両方 1}}\ \right]\]

4成分のベクトルは上から \(|00\rangle, |01\rangle, |10\rangle, |11\rangle\) に対応するので、\(|00\rangle\) と \(|11\rangle\) の成分だけが \(\frac{1}{\sqrt2}\) で、\(|01\rangle\) と \(|10\rangle\) の成分は 0 です。1量子ビットずつのテンソル積に書き直すと、2行目のように「両方 0」と「両方 1」の和になります。これがベル状態です。

この和は、量子ビット1のベクトルと量子ビット2のベクトルの1つの積にまとめ直すことができません。テンソル積でも普通の掛け算と同じように分配法則が成り立つので、1つの積を展開すると、

\[\left[\begin{pmatrix}1\\0\end{pmatrix} + \begin{pmatrix}0\\1\end{pmatrix}\right]\otimes v = \begin{pmatrix}1\\0\end{pmatrix}\otimes v + \begin{pmatrix}0\\1\end{pmatrix}\otimes v\]

と、どちらの項にも同じ相手 \(v\) が付きます。逆に言えば、1つの積にまとめられるのは、共通の相手でくくり出せるときだけです。ベル状態は相手が \((1, 0)^T\) と \((0, 1)^T\) で異なるので、くくり出せません。多項式でいえば、\(x_0 y_0 + x_1 y_1\) が因数分解できないのと同じです。

2本の量子ビットは、それぞれが自分の状態を持っているのではなく、2本ひと組でしか状態を書けない。これが「もつれ（エンタングルメント）」です。第五講・第六講で量子鍵配送や量子中継に登場した「もつれた光子対」は、まさにこの状態でした。それが \(H\) 1個と CNOT 1個で作れてしまいます。

---

測定：確率として読み出す

ここまでは状態ベクトルを直接のぞいてきましたが、これはシミュレータだからできる反則です。実際の量子コンピュータでは、状態ベクトルそのものは見えません。見えるのは測定の結果だけで、しかも測った瞬間に状態は壊れます（第五講・第六講で繰り返し見てきた性質です）。

最初に触れたとおり、測定で各結果が出る確率は、その成分の振幅の2乗です。ベル状態 \(\frac{1}{\sqrt2}(1, 0, 0, 1)^T\) なら、

結果	\(\lvert 00\rangle\)	\(\lvert 01\rangle\)	\(\lvert 10\rangle\)	\(\lvert 11\rangle\)
振幅	\(\frac{1}{\sqrt2}\)	0	0	\(\frac{1}{\sqrt2}\)
確率	\(\frac12\)	0	0	\(\frac12\)

\(|00\rangle\) と \(|11\rangle\) が半々で、\(|01\rangle\) と \(|10\rangle\) は絶対に出ません。 ここに、もつれの観測上の意味がそのまま現れています。量子ビット1だけを見ると、0 と 1 が半々のでたらめな結果です。ところが量子ビット2を見ると、必ず量子ビット1と同じ値が出ています。

量子ビット1だけを測った場合を考えると、さらにはっきりします。測定後の状態は、量子ビット1が 0 と出たら \(|00\rangle\)、1 と出たら \(|11\rangle\) になっています。片方を測った瞬間に、もう片方の値も決まるのです。

---

応用：グローバーのアルゴリズム

部品がそろったので、講義にも出てきたグローバーのアルゴリズムを組んでみます。

何をするアルゴリズムか

グローバーのアルゴリズムは探索のアルゴリズムです。\(N\) 個の候補の中に、条件を満たす「当たり」が1つだけある。それを見つけたい、という問題です。

ここで前提になるのがオラクルと呼ばれる箱です。オラクルは当たりがどれかを教えてはくれません。候補を1つ渡すと、それが当たりかどうかを判定するだけです。

古典計算機なら、候補を1つずつオラクルに渡していくしかありません。平均で \(N/2\) 回、運が悪ければ \(N\) 回近くかかります。グローバーのアルゴリズムは、これを約 \(\frac{\pi}{4}\sqrt{N}\) 回に減らします[1]。

量子版のオラクルは「当たりかどうか」を答えとして返すのではなく、当たりの振幅の符号だけを反転するゲートとして働きます。

ただし、符号を反転しただけでは何も起きません。確率は振幅の2乗なので、符号が変わっても確率は変わらず、測っても当たりはわからないからです。そこでもう1つの部品として、拡散と呼ばれる操作を組み合わせます。拡散は、すべての振幅について、平均を基準にして、平均との差を逆向きにする操作です。振幅を \(a\)、すべての振幅の平均を \(\bar a\) と書くと、平均との差は \((a – \bar a)\) なので、これを逆向きにして平均に足し戻すと、

\[a \;\to\; \bar a – (a – \bar a)\]

となります。平均より上にあった振幅は同じだけ下へ、下にあった振幅は同じだけ上へ移ります。オラクルで符号を反転された当たりだけが平均から大きく下に離れているので、差を逆向きにすると当たりの振幅だけが大きく上がります。拡散は当たりが何であっても同じ操作で、問題ごとに変わるのはオラクルだけです。

グローバーのアルゴリズムは、

1. すべての候補を同じ振幅で重ね合わせる
2. オラクルで当たりの符号を反転する
3. 拡散で平均を基準にして平均との差を逆向きにし、当たりの振幅を大きくする
4. 2と3を必要な回数だけ繰り返してから、測定する

という手順です。これがどう働くのかを、いちばん小さい例で見ていきます。

2量子ビット版：4つの中から \(|11\rangle\) を探す

候補は \(|00\rangle, |01\rangle, |10\rangle, |11\rangle\) の4つで、当たりを \(|11\rangle\) とします。回路はこうなります。

使っているゲートは H、X、CZ の3種類だけです。CZ（制御 Z）は、2本とも \(|1\rangle\) のとき、つまり \(|11\rangle\) のときだけ符号を反転するゲートです。行列で書くと、

\[\text{CZ} = \begin{pmatrix}1&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&0&-1\end{pmatrix}\]

という対角行列で、当たりの位置（4番目、\(|11\rangle\)）の対角成分だけが \(-1\) になっています。振幅ベクトルに掛けると、4番目の成分の符号だけが反転します。ちょうど「\(|11\rangle\) が当たり」のオラクルです。

この回路の測定結果は、確率1で \(|11\rangle\) です。オラクルに問い合わせたのは1回だけです。古典なら、4つを順に調べて平均2.25回かかるところです。

1ステップずつ振幅を追う

何が起きたのかを、途中の状態ベクトルで確かめます。

\[\underbrace{\frac{1}{2}\begin{pmatrix}1\\1\\1\\1\end{pmatrix}}_{\text{①}} \xrightarrow{\ \text{オラクル}\ } \underbrace{\frac{1}{2}\begin{pmatrix}1\\1\\1\\-1\end{pmatrix}}_{\text{②}} \xrightarrow{\ \text{拡散}\ } \underbrace{\begin{pmatrix}0\\0\\0\\1\end{pmatrix}}_{\text{③}}\]

1. ① 一様な重ね合わせ：H を2本にかけると、4つの候補が振幅 \(\frac12\) ずつで並びます。この時点で測ると、どれも確率 \(\frac14\) です。
2. ② オラクル：当たりの \(|11\rangle\) だけ振幅が \(-\frac12\) になります。確率は \(\left(-\frac12\right)^2 = \frac14\) のままなので、この時点で測っても何もわかりません。符号の違いは、測定では見えないのです。
3. ③ 拡散：ここが手品の種です。先に紹介した「平均を基準にして、平均との差を逆向きにする」操作を、数字で追ってみます。

②の振幅の平均は \(\frac14\left(\frac12 + \frac12 + \frac12 – \frac12\right) = \frac14\) です。図5の②の破線がこの平均で、これを基準にします。先ほどの式

\[a \;\to\; \bar a – (a – \bar a)\]

に \(\bar a = \frac14\) を入れると、次のようになります。

• はずれ（\(\frac12\)）：平均より \(\frac14\) だけ上にある → 平均より \(\frac14\) だけ下へ移る → \(\frac14 – \left(\frac12 – \frac14\right) = 0\)
• 当たり（\(-\frac12\)）：平均より \(\frac34\) だけ下にある → 平均より \(\frac34\) だけ上へ移る → \(\frac14 – \left(-\frac12 – \frac14\right) = 1\)

平均の近くにいたはずれは少ししか動かず、平均から遠く離れていた当たりは大きく跳ね上がります。

行列で書くと、この「平均との差を逆向きにする」操作は次のようになります。

\[\frac{1}{2}\begin{pmatrix}-1&1&1&1\\1&-1&1&1\\1&1&-1&1\\1&1&1&-1\end{pmatrix}\cdot\frac{1}{2}\begin{pmatrix}1\\1\\1\\-1\end{pmatrix} = \frac{1}{4}\begin{pmatrix}-1+1+1-1\\1-1+1-1\\1+1-1-1\\1+1+1+1\end{pmatrix} = \begin{pmatrix}0\\0\\0\\1\end{pmatrix}\]

はずれの振幅はちょうど 0 になり、当たりに全部集まりました。オラクルが符号を反転して当たりだけを平均から遠ざけ、拡散が平均との差を逆向きにして持ち上げる。これがグローバーのアルゴリズムの仕組みです。先ほどの「H を2回かけると元に戻る」で見た干渉を、狙った答えが残るように設計したもの、と言えます。

なお、図4のように H・X・CZ で拡散を組むと、正確には上の行列にさらに \(-1\) を掛けたもの（対角が \(+\frac12\)、それ以外が \(-\frac12\)）になり、最後の状態は \((0, 0, 0, -1)^T\) になります。全体に一様にかかる符号（グローバル位相）は測定の確率に一切影響しないので、無視してかまいません。

当たりを変えるには

当たりを \(|11\rangle\) 以外にしたいときは、オラクルだけを変えます。CZ は \(|11\rangle\) にしか反応しないので、当たりのビットが 0 の位置を、CZ の前後で X を使って一時的に 1 に反転しておけばよいのです。たとえば当たりが \(|01\rangle\) なら、量子ビット1を X で挟みます。行列で計算すると、

\[(X\otimes I)\ \text{CZ}\ (X\otimes I) = \begin{pmatrix}1&0&0&0\\0&-1&0&0\\0&0&1&0\\0&0&0&1\end{pmatrix}\]

となり、\(-1\) が当たりの位置（2番目、\(|01\rangle\)）に移ります。一般に、2量子ビット版のオラクルは「当たりの位置だけ \(-1\) で、残りは \(1\) の対角行列」です。こうして4通りの当たりすべてを試すと、どれも確率1で正解が出ます。

3量子ビット版：回しすぎると戻ってくる

2量子ビットでは1回でぴったり当たりましたが、これは \(N = 4\) の特殊な事情です。候補を8つ（3量子ビット）に増やすと、様子が変わります。

3量子ビットでは、CZ の代わりに、3本すべてが1のときだけ符号を反転する CCZ ゲート（制御ビットを2本持つ制御 Z）を使います。当たりを \(|101\rangle\) として、「オラクル＋拡散」の組を \(k\) 回繰り返したときの正解の確率を計算しました。

繰り返し回数 \(k\)	0	1	2	3	4
正解の確率	\(\frac{1}{8} = 0.125\)	\(\frac{25}{32} \fallingdotseq 0.781\)	\(\frac{121}{128} \fallingdotseq \mathbf{0.945}\)	\(\frac{169}{512} \fallingdotseq 0.330\)	\(\frac{25}{2048} \fallingdotseq 0.012\)

2回で 94.5% まで上がりますが、3回目で 33% に落ちます。回しすぎると、当たりの振幅が逆に減っていくのです。

これは、グローバーのアルゴリズムが「当たりの状態」と「はずれ全体の重ね合わせ」が張る平面の中で、状態ベクトルを一定の角度 \(2\theta\) ずつ回転させているからです。当たりの方向を向いたところで止めれば確率はほぼ1になりますが、そのまま回し続けると通り過ぎてしまいます。ちょうどよい回数は約 \(\frac{\pi}{4}\sqrt{N}\) 回で、\(N = 8\) なら 2.2、つまり2回です。Mathematica で計算した厳密値は、理論式に \(k\) を代入した値と誤差なしで一致します。

---

まとめ：部品はたったこれだけ

今回使ったゲートを並べてみます。

ゲート	使った場面
H	重ね合わせを作る、干渉させる
X	ビット反転、オラクルで当たりの位置をずらす
CNOT	もつれを作る
CZ・CCZ	オラクル、拡散
測定	確率として読み出す

これだけで、もつれからグローバーのアルゴリズムまで組めました。 そしてどの回路も、中でやっていることはベクトルに行列を順に掛けていく計算です。

第七講のショアの回路も、同じ目で見直せます。左端の H で計数レジスタを重ね合わせにし、中央の制御ゲートで \(a^y \bmod N\) を並べ、右端の逆量子フーリエ変換で干渉させて周期を読む。重ね合わせ → 問題を解く制御ゲート → 干渉 → 測定という骨組みは、グローバーとまったく同じです。講義で紹介された HHL アルゴリズム（連立一次方程式を解く量子アルゴリズム）も、同じ骨組みの上に作られています。

数量子ビットの回路なら手元のパソコンで中身を全部見られます。講義で出てきた量子アルゴリズムを「読む」だけでなく「組んで、途中を覗く」と、式だけでは見えなかったものが見えてきます。

---

参考文献

[1] グローバーの原論文
L. K. Grover, “A fast quantum mechanical algorithm for database search,” Proceedings of the 28th Annual ACM Symposium on Theory of Computing (STOC ’96), 212–219 (1996).
https://arxiv.org/abs/quant-ph/9605043