Orthogonal complements in the vector space \(\mathbb{Z}_2^n\)

This section will review some mathematical preliminaries that will be useful in understanding Simin's algorithm.

The set \(\{0,1\}^n\) can be regarded as an \(n\)-dimensional vector space \(\mathbb{Z}_2^n\) over the field \(\mathbb{Z}_2\) where the addition of vectors, or bitstrings, \(\mathbf{x}=x_1x_2\dots x_n\) and \(\mathbf{y}=y_1y_2\dots y_n\) in \(\{0,1\}^n\) is given by \(\mathbf{x}\oplus\mathbf{y}=\mathbf{z}\). Let \(\mathbf{z}=z_1z_2\dots z_n\). Then this operation is just bitwise addition modulo \(2\) where \(z_i=(x_i+y_i)mod2\) for each \(i\). That is, \(z_i=1\) if and only if \(x_i\neq y_i\). An inner product on \(\mathbb{Z}_2^n\) is also defined for \(\mathbf{x}=x_1x_2\dots x_n\) and \(\mathbf{y}=y_1y_2\dots y_n\) in \(\mathbb{Z}_2^n\) as
\[\mathbf{x}\cdot\mathbf{y}=(x_1y_1+x_2y_2+\dots +x_ny_n)mod2=\left(\displaystyle\sum\limits_{i=1}^n x_iy_i\right)mod2,\] and so the product of two bitstrings is either \(0\) or \(1\).

 Consider some \(\mathbf{s}\in\mathbb{Z}_2^n\) and define the orthogonal complement of \(\mathbf{s}\) as the set \(\mathbf{s}^{ \bot}=\{\mathbf{x}\in\mathbb{Z}_2^n | \mathbf{x}\cdot\mathbf{s}=0\}\) consisting of all strings orthogonal to \(\mathbf{s}\). The orthogonal complement \(\mathbf{s}^{ \bot}\) of \(\mathbf{s}\) is actually a vector subspace of \(\mathbb{Z}_2^n\) that is orthogonal to the \(1\)-dimensional vector subspace \(\{\mathbf{0},\mathbf{s}\}\) provided that \(\mathbf{s}\neq\mathbf{0}\). Then since \(\mathbf{s}^{ \bot}\cup\{\mathbf{0},\mathbf{s}\}=\mathbb{Z}_2^n\), and \(\mathbb{Z}_2^n\) has dimension \(n\), \(\mathbf{s}^{ \bot}\) must be a subspace of dimension \(n-1\).

For some string \(\mathbf{x}=x_1x_2\dots x_n\in\{0,1\}^n\), denote by \(\mathbf{x}^T\) the column vector that has the coefficient \(x_i\) in row \(i\). Define a \(m\times n\) matrix \(W\) whose rows are given by \(m\) bitstrings \(\mathbf{w}_j\in\mathbf{s}^{ \bot}\) for some \(\mathbf{0}\neq\mathbf{s}\in\{0,1\}^n\). If the \(m\) bitstrings \(\mathbf{w}_i\) are chosen so that they span \(\mathbf{s}^{ \bot}\) entirely, then a nontrivial solution \(\mathbf{x}^T\) to the matrix equation \(W\mathbf{x}^T=\mathbf{0}^T\), where \(\mathbf{0}\in\{0,1\}^m\), will be a the unique solution \(\mathbf{x}^T=\mathbf{s}^T\) that determines exactly the bitstring \(\mathbf{s}\).

 Let \(\mathbf{x}, \mathbf{y}\in\{0,1\}^n\) and \(\mathbf{s}=\mathbf{x}\oplus\mathbf{y}\). Consider the quantum state \[\left|\psi\right>=\displaystyle\frac{1}{\sqrt{2}}(\left|\mathbf{x}\right>+\left|\mathbf{y}\right>)\in\mathcal{H}^{2^n}.\] Note that \(\mathbf{y}=\mathbf{x}\oplus\mathbf{s}\) implies \[\left|\psi\right>=\displaystyle\frac{1}{\sqrt{2}}(\left|\mathbf{x}\right>+\left|\mathbf{x}\oplus\mathbf{s}\right>).\] Applying the Hadamard transform \(H^{\otimes n}\) to \(\left|\psi\right>\) gives
\[\begin{array}{r l}
H^{\otimes n}\left|\psi\right> &=\displaystyle\frac{1}{\sqrt{2}}\left(H^{\otimes n}\left|\mathbf{x}\right>+H^{\otimes n}\left|\mathbf{x}\oplus\mathbf{s}\right>\right) \\
&= \displaystyle\frac{1}{\sqrt{2}}\left(\displaystyle\frac{1}{\sqrt{2^n}}\displaystyle\sum\limits_{\mathbf{z}\in\{0,1\}^n}(-1)^{\mathbf{x}\cdot\mathbf{z}}\left|\mathbf{z}\right>+\displaystyle\frac{1}{\sqrt{2^n}}\displaystyle\sum\limits_{\mathbf{z}\in\{0,1\}^n}(-1)^{(\mathbf{x}\oplus\mathbf{s})\cdot\mathbf{z}}\left|\mathbf{z}\right>\right) \\
&= \displaystyle\frac{1}{\sqrt{2^{n+1}}}\left(\displaystyle\sum\limits_{\mathbf{z}\in\{0,1\}^n}\left((-1)^{\mathbf{x}\cdot\mathbf{z}}+(-1)^{(\mathbf{x}\oplus\mathbf{s})\cdot\mathbf{z}}\right)\left|\mathbf{z}\right>\right)
\end{array}.\]
Now consider the amplitude \(\alpha_z\) of the state \(\left|\mathbf{z}\right>\) in this superposition:
\[\begin{array}{r l}
\alpha_z  & =(-1)^{\mathbf{x}\cdot\mathbf{z}}+(-1)^{(\mathbf{x}\oplus\mathbf{s})\cdot\mathbf{z}} \\
& = (-1)^{\mathbf{x}\cdot\mathbf{z}}+(-1)^{\mathbf{x}\cdot\mathbf{z}\oplus\mathbf{s}\cdot\mathbf{z}} \\
& = (-1)^{\mathbf{x}\cdot\mathbf{z}}\left(1+(-1)^{\mathbf{s}\cdot\mathbf{z}}\right)
\end{array}.\]
If \(\mathbf{z}\in\mathbf{s}^{ \bot}\), then \(\mathbf{s}\cdot\mathbf{z}=0\) and so \((-1)^{\mathbf{s}\cdot\mathbf{z}}=1\) which implies that \(\alpha_z=2(-1)^{\mathbf{x}\cdot\mathbf{z}}\). Thus, the state \(\left|\mathbf{z}\right>\) remains with a nonzero amplitude \(\alpha_z\) in the superposition \(H^{\otimes n}\left|\psi\right>\). Instead, suppose \(\mathbf{z}\notin\mathbf{s}^{ \bot}\) so that \(\mathbf{s}\cdot\mathbf{z}=1\), which implies that the amplitude of the state \(\left|\mathbf{z}\right>\) is \(\alpha_z=(-1)^{\mathbf{x}\cdot\mathbf{z}}\left(1+(-1)^1\right)=0\). Therefore, the state \(H^{\otimes n}\left|\psi\right>\) consists of a superposition of precisely those \(2^{n-1}\) states \(\left|\mathbf{z}\right>\in\{0,1\}^n\) such that \(\mathbf{z}\in\mathbf{s}^ { \bot}\), allowing the sum to be written as
\[H^{\otimes n}\left|\psi\right>=\displaystyle \frac{1}{\sqrt{2^{n-1}}}\displaystyle\sum\limits_{\mathbf{z}\in\mathbf{s}^{ \bot}}(-1)^{\mathbf{x}\cdot\mathbf{z}}\left|\mathbf{z}\right>.\]
If a measurement were to be performed on the state \(H^{\otimes n}\left|\psi\right>\), where \[\left|\psi\right>=\displaystyle \frac{1}{\sqrt{2}}(\left|\mathbf{x}\right>+\left|\mathbf{x}\oplus\mathbf{s}\right>),\]  some computational basis state \(\left|\mathbf{z}\right>\) such that  \(\mathbf{z}\in\mathbf{s}^{ \bot}\) will be observed.

If multiple quantum states of the form \[\left|\psi\right>=\displaystyle\frac{1}{\sqrt{2}}(\left|\mathbf{x}\right>+\left|\mathbf{x}\oplus\mathbf{s}\right>)\] can be constructed and then measured, the set of observed states can be used to construct the matrix \(W\) whose rows consist of elements in \(\mathbf{s}{ \bot}\). Furthermore, if these observed states \(\left|\mathbf{w}_j\right>\) happen to correspond to elements that span \(\mathbf{s}^ { \bot}\), then the string \(\mathbf{s}\) can be uniquely determined by solving the system \(W\mathbf{x}^T=\mathbf{0}^T\). Simon's algorithm provides a way to construct such a state by making queries to the a black-box.