Simon のアルゴリズムの確認の最後として 1-to-1 の場合を見る。書籍のコードでは 1-to-1 の条件なら何でも良いということでランダム気味な回路が作られる。ある時に作られた回路を見る:
この時に 1 つ目のレジスタを測定すると
というようにすべての量子状態が観測された。2-to-1 と仮定して、$\mathcal{O}(n)$ 回の試行の末に異なる $y_1, \cdots, y_n$ が観測されたとしよう。ここから $s^*$ は求まるとしても、$y_1, \cdots, y_n$ がどの組み合わせで観測されるかによって $s^*$ の内容は変わってしまい、従って実質ランダムである。仮に $\ket{0001}, \ket{0010}, \ket{0011}, \ket{0100}$ が観測されたとすると、$s^* = \ket{1000}$ が求まる。2-to-1 と仮定しているので、この $s^*$ は正しい $s$ ということになり、$f_s(s^*) = f_s(0)$ を満たすはずであるが。しかし問い合わせ関数だけからなる回路に実際に $s^*$ を入力すると 2 つ目のレジスタからは $f_s(s^*)$ として
{'0011': 128}が観測され、$\ket{0}$ を入力すると $f_s(0)$ として
{'1011': 128}が観測され一致しない。よって、2-to-1 と仮定したことが誤りであり、1-to-1 ということになる。
これで書籍 p.129 まで完了となる。
