Tuesday, 10 September 2013

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.