さて、書籍 p.125 によると異なる 1st レジスタの値を $n$ 個 ($y_1,\cdots,y_n$) 測定できたとすると、以下の $\mod2$ の方程式が Gauss の消去法 (吐き出し法) などで解けるとのことである。
\begin{align*}
\begin{cases}
y_1 \cdot s &= 0 \\
&\vdots \\
y_n \cdot s &= 0
\end{cases}
\tag{1}
\end{align*}
Simon’s Algorithm — Grove 1.7.0 documentation によると、Intro_to_QC_Vol_1_Loceff.pdf p.523- 辺りが参考になるらしい。まずはおさらいとして
\begin{align*}
\begin{cases}
5x + y + 2z + w &= 7 \\
x - y + z + 2w &= 10 \\
x + 2y - 3z + 7w &= -3
\end{cases}
\end{align*}
が登場する。第 1 式と第 2 式および第 2 式と第 3 式から以下を得る。
\begin{align*}
\begin{cases}
6y - 3z - 9w &= -43 \\
3y - 4z + 5w &= -13
\end{cases}
\end{align*}
さらに
\begin{align*}
5z - 19w = -17
\end{align*}
が得られる。ここまでを行列の形でプロセスを実行したものが “Gaussian elimination” になる。ところが、変数の数と方程式の数が合わないので、唯一の解が求まらない。ここから例えば $z = \alpha$ として、残りの $x,y,z$ も $\alpha$ の式とし、簡単に一般解を得られるのであった。この辺が “back substitution” にあたると思う。
(1) 式を成分ごとに書き下すと、$y_i = (y_i^1, \cdots, y_i^n)$, $s = (s^1,\cdots,s^n)$ と書くことにして、
\begin{align*}
\begin{pmatrix}
y_1^1 &\cdots & y_1^n \\
\vdots & \ddots & \vdots \\
y_n^1 &\cdots & y_n^n
\end{pmatrix} \begin{pmatrix}
s^1 \\
\vdots \\
s^n
\end{pmatrix} \equiv \begin{pmatrix}
0 \\
\vdots \\
0
\end{pmatrix} \mod 2
\end{align*}
を得る。これらは全て $\{0,1\}$ に値をとっている。よってガウスの消去法を適用すると、例えば
\begin{align*}
\begin{pmatrix}
1 & 1 & 1 & 1 \\
0 & 1 & 1 & 0 \\
0 & 0 & 1 & 0 \\
0 & 0 & 0 & 0
\end{pmatrix} \begin{pmatrix}
s^1 \\
s^2 \\
s^3 \\
s^4
\end{pmatrix} \equiv \begin{pmatrix}
0 \\
0 \\
0 \\
0
\end{pmatrix} \mod 2
\tag{2}
\end{align*}
となる。このケースでは $s^* = (1, 0, 0, 1)$ が “有意な” $s^*$ ということになる。$(0, 0, 0, 0)$ も解であるので、一意性はない。
常に “有意な” 解が求まることは議論が必要と思われるが、解 $s^*$ が求まる流れはなんとなく分かったように思う。
あまりシックリとはこないが、D. R. Simon の論文 On the power of quantum computation によると、(2) の方程式は自明な解と非自明な解からなり、この非自明な解 $s^*$ が求める $s$ であるとの主張である。部分的に $s$ の性質を満たしたら一致することが保証されているのかちょっと読み取れなかったのでが、一旦ここはそういうものと理解することにして先へ進む。また、この時 $f_s(s^*) = f_s(0 \oplus s^*) = f_s(0)$ なので、$f_s(s^*)$ を $f_s(0)$ と比較すれば 1-to-1 か 2-to-1 か判断できるよ、とのことである。1-to-1 の場合、$s^*$ はランダムな列になるとなっており、たぶん・・・実態に反して 2-to-1 と仮定して無理に解いたので意味のないものになるという意味なのだと思う・・・。
