書籍 p.125 からがよく分からない。また、Simon's Algorithm を見ると書籍と条件が違うように見える。書籍では $x^\prime = x \oplus s \Rightarrow f_s(x) = f_s(x^\prime)$ だが、Qiskit-textbook ではちょっと形が違う。書籍の条件だと、$x^\prime = x \oplus s$ 以外にも $f_s(x)$ をとる入力値を許してそうに感じられる。Simon's problem - Wikipedia もあまりスッキリしないので、Simon’s Algorithm — Grove 1.7.0 documentation の記述を一旦念頭に置く・・・。というより、D.R. Simon の論文 On the power of quantum computation から条件を書き出す:
$f: \{0,1\}^n \to \{0,1\}^m\ (m \geq n)$ が与えられ、$f$ が 1-to-1 であるか、或いは非自明な n bit の列 $s$ が存在して異なる $x$ と $x^\prime$ に対し $f(x) = f(x^\prime) \iff x^\prime = x \oplus s$ となることのいずれかが成立するものとする。$f$ に対していずれが成立するか、そして後者の場合は $s$ が何であるかを見つけたい。
と書かれている。定理の主張としては $f$ がこのいずれかの形になると定義されていれば (xor-マスク不変性)、これを (効率良く) 解くアルゴリズムが存在するという内容である。
後者の場合、つまり 2-to-1 でも $2^{n-1}$ 回目までは異なる入力に対してたまたま異なる出力を得る可能性があるので、最悪値で $2^{n-1} + 1$ 回の試行をしないと関数の性質がどちらか切り分けできないので、古典アルゴリズムの最悪の確認回数は $2^{n-1} + 1$ 回となる。
問い合わせのゲートは正確には、Deutsch-Jozsa と同様に、$U_f: \ket{x}\ket{a} \to \ket{x}\ket{a \oplus f(x)}$ という性質のようだ。
textbook の日本語訳も曖昧だが: $\ket{\psi_3} = \frac{1}{\sqrt{2}^n} \sum_{x \in \{0,1\}^n} \ket{x}\ket{f(x)}$ を得た時点で 2nd レジスタにおいて $f(x)$ を測定したとする。この時、まだ 1-to-1 か 2-to-1 か分かっていないので、$x$ からくる $f(x)$ として測定されたかもしれないし、$x^\prime = x \oplus s$ からくる $f(x^\prime) = f(x)$ として観測されたかもしれない。possible のニュアンスが消えている。
と、textbook ではここから急に 2-to-1 のことだけを話しているように見える。2-to-1 だと仮定して測定を進めて正しいか矛盾するかで判断するのだろうか？
2-to-1 のケースでは、1st レジスタは $\ket{x}$ と $\ket{x \oplus s}$ が半々で混在しており、1st レジスタは
\begin{align*}
\ket{\psi_4} = \frac{1}{\sqrt{2}}(\ket{x} + \ket{x^\prime})
\end{align*}
の状態にある。ここで、既に何回か用いている公式
\begin{align*}
H^{\otimes n} \ket{x} = \frac{1}{\sqrt{2}^n} \sum_{y=0}^{2^n-1} (-1)^{x\cdot y} \ket{y}
\end{align*}
を思い出す。$\ket{\psi_4}$ に $H^{\otimes n}$ を作用させると、
\begin{align*}
\ket{\psi_5} &= H^{\otimes n} \ket{\psi_4} \\
&= \frac{1}{\sqrt{2}^{n+1}} \sum_{z \in \{0, 1\}} [(-1)^{x\cdot z} \ket{z} + (-1)^{x^\prime\cdot z} \ket{z}]
\end{align*}
既に Qiskit (23) - らんだむな記憶 で見たように、$z\cdot s \equiv 0 \mod 2$ の時のみ $(-1)^{x\cdot z} + (-1)^{x^\prime\cdot z}$ が非 0 となり生き残るのであった。
これで、書籍 p.124 のところまで textbook でも並走できた。
