## Tuesday, 10 September 2013

### Simon's Problem and Algorithm

Let $X\subseteq \{0,1\}^n$ be some subset and consider a function $f: \{0,1\}^n\rightarrow X$ that satisfies the property that for all $\mathbf{x}, \mathbf{y}\in \{0,1\}^n$, $f(\mathbf{x})=f(\mathbf{y})$ if and only if $\mathbf{x}=\mathbf{y}$ or $\mathbf{x}=\mathbf{y}\oplus\mathbf{s}$, for some fixed $\mathbf{s}\in\{0,1\}^n$. Suppose such a function is provided, but the string $\mathbf{s}$ is unknown. Simon's problem, presented first in \cite{simon}, is concerned with determining the string $\mathbf{s}$ by making queries to a black-box that evaluates the function $f$.

Simon's Problem

Input:  A black-box that computes an unknown function $f:\{0,1\}^n\rightarrow X$, where $X\subseteq\{0,1\}$, such that there exists  some fixed $\mathbf{s}\in\{0,1\}^n$ that satisfies  $f(\mathbf{x})=f(\mathbf{y})$ if and only if $\mathbf{x}=\mathbf{y}$ or $\mathbf{x}=\mathbf{y}\oplus\mathbf{s}$.

Problem:  Determine the unknown string $\mathbf{s}\in\{0,1\}^n$ by making queries to the black-box that evaluates $f$.

A quantum algorithm for solving Simon's problem will be constructed in what follows, and it will be shown that this can be done by making exponentially fewer queries to $f$ than what is needed in the classical case. Before presenting this algorithm, it is worthwhile to invest some detail pertaining to some properties of bitstrings in $\{0,1\}^n$ and certain operations defined on them. The relevant details can be found in the previous post on orthogonal complements in the vector space $\mathbb{Z}_2^n$. These consequences will be essential in the analysis of Simon's algorithm.

Simon's Algorithm

For Simons problem we are provided with a black-box that computes an unknown function $f: \{0,1\}^n\rightarrow X$ such that there exists  some fixed $\mathbf{s}\in\{0,1\}^n$ that satisfies  $f(\mathbf{x})=f(\mathbf{y})$ if and only if $\mathbf{x}=\mathbf{y}$ or $\mathbf{x}=\mathbf{y}\oplus\mathbf{s}$. This black-box can be implemented as the controlled$-U_f$ gate $\begin{array}{r l} c-U_f: &\mathcal{H}^{2^n}\otimes\mathcal{H}^{2^n}\rightarrow \mathcal{H}^{2^n}\otimes \mathcal{H}^{2^n}, \\ & \left|\mathbf{x}\right>\left|\mathbf{y}\right>\mapsto \left|\mathbf{x}\right>\left|\mathbf{y}\oplus f(\mathbf{x})\right>, \end{array}$
where the first register serves as a $n$ qubit control register and the second register acts as a $n$ qubit target.

(A circuit used to solve Simon's problem consisting of two $n$ qubit registers. Simon's algorithm runs the circuit multiple times making a single query to the black-box $c-U_f$ each time the circuit is applied. First, Hadamard gates are applied to the first $n$ qubits in the control register of the state $\left|\psi_0\right>$ creating an equally weighted superposition of basis states in the control register. Then by applying the $c-U_f$ gate to $\left|\psi_1\right>$ an entangled state $\left|\psi_2\right>$ is produced that contains the value of each $f(\mathbf{x})$ in the target register. Measuring the target register of $\left|\psi_2\right>$, leaves the control register in a state which produces a superposition $\left|\psi_4\right>$ of states in the orthogonal complement $\mathbf{s}^ {\bot}$ after the last set of Hadamard gates is applied to the control register. A final measurement of the control register then produces a state $\left|\psi_5\right>$ in $\mathbf{s}^ {\bot}$. After this procedure is iterated a sufficient amount of times the states obtained after the measurement can be used to determine $\mathbf{s}$.)

Simon's algorithm makes use of the circuit displayed in the figure above, and begins with the input state $\left|\psi_0\right>=\left|\mathbf{0}\right>\left|\mathbf{0}\right>$. First, a Hadamard gate is applied to every qubit in the control yielding
$\left|\psi_1\right>=H^{\otimes n}\left|\mathbf{0}\right>\left|\mathbf{0}\right>=\displaystyle \frac{1}{\sqrt{2^{n}}}\displaystyle\sum\limits_{\mathbf{x}\in\{0,1\}^n}\left|\mathbf{x}\right>\left|\mathbf{0}\right>,$
which has an equally weighted superposition of all $2^n$ basis states in the control register. Next, by making a single query with $c-U_f$ to the state $\left|\psi_1\right>$, a superposition of states is formed that contains the value of $f(\mathbf{x})$ for every $\mathbf{x}\in\{0,1\}^n$ in the target register
$\begin{array}{r l} \left|\psi_2\right>=c-U_f\left|\psi_1\right> &=\displaystyle\frac{1}{\sqrt{2^{n}}}\displaystyle\sum\limits_{\mathbf{x}\in\{0,1\}^n}c-U_f(\left|\mathbf{x}\right>\left|\mathbf{0}\right>) \\ &=\displaystyle \frac{1}{\sqrt{2^{n}}}\displaystyle\sum\limits_{\mathbf{x}\in\{0,1\}^n}\left|\mathbf{x}\right>\left|f(\mathbf{x})\right>. \end{array}$
Notice that this state $\left|\psi_2\right>$ is actually an entangled state. If all the qubits in the target register were to be measured at this point, a particular computational basis state $\left|f(\mathbf{x})\right>\in\mathcal{H}^{2^n}$ will be observed.

To see what state the control register will be left in after a measurement is made to the target, recall the definition of the function $f$: f(\mathbf{x})=f(\mathbf{y})\) if and only if $\mathbf{x}=\mathbf{y}$ or $\mathbf{y}=\mathbf{x}\oplus\mathbf{s}$. Observe that if $\mathbf{s}\neq\mathbf{0}$ then the function $f$ is two-to-one. This means that for every value $f(\mathbf{x})$ there are precisely two bitstrings in $\{0,1\}^n$ that both share the same value $f(\mathbf{x})$---namely, the strings $\mathbf{x}$ and $\mathbf{y}=\mathbf{x}\oplus\mathbf{s}$. Therefore, consider a partition of the $2^n$ bitstrings of $\{0,1\}^n$ into $2^{n-1}$ disjoint sets  where each set is of the form $\{\mathbf{x},\mathbf{x}\oplus\mathbf{s}\}$. Moreover, let $I$ be the index set that contains $2^{N-1}$ bitstrings $\mathbf{x}$ that represent each of the sets $\{\mathbf{x},\mathbf{x}\oplus\mathbf{s}\}$. In this way, the  entangled state $\left|\psi_2\right>$ can be expressed as
$\left|\psi_2\right>=\displaystyle \frac{1}{\sqrt{2^{n}}}\displaystyle\sum\limits_{\mathbf{x}\in\{0,1\}^n}\left|\mathbf{x}\right>\left|f(\mathbf{x})\right>=\displaystyle \frac{1}{\sqrt{2^{n-1}}}\displaystyle\sum\limits_{\mathbf{x}\in I}\left(\left|\mathbf{x}\right>+\left|\mathbf{x}\oplus\mathbf{s}\right>\right)\left|f(\mathbf{x})\right>,$ where now the sum only runs over the indexed states of $I$.

When the target register of $\left|\psi_2\right>$ is measured, a state of the form
$\left|\psi_3\right>=\left(\left|\mathbf{x}\right>+\left|\mathbf{x}\oplus\mathbf{s}\right>\right)\left|f(\mathbf{x})\right>$for a particular value of $f(\mathbf{x})$ is observed with equal probability. Thus, the target register becomes the state $\left|f(\mathbf{x})\right>$, and the control register is left in the state $\displaystyle\frac{1}{\sqrt{2}}\left(\left|\mathbf{x}\right>+\left|\mathbf{x}\oplus\mathbf{s}\right>\right)$ after measurement. Then as it was shown in the previous section, where $\left|\psi\right>=\displaystyle\frac{1}{\sqrt{2}}\left(\left|\mathbf{x}\right>+\left|\mathbf{x}\oplus\mathbf{s}\right>\right),$ applying Hadamard gates to the control register after a measurement on the target register has been made results in the state
$\left|\psi_4\right>=H^{\otimes n}\left|\psi_3\right>=H^{\otimes n}\left|\psi\right>\left|f(\mathbf{x})\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>\left|f(\mathbf{x})\right>,$
which has the control register in an equally weighted superposition of all basis states belonging to the orthogonal complement $\mathbf{s}^ {\bot}$. Measuring the control register therefore yields some state $\left|\psi_5\right>=\left|\mathbf{z}\right>$, such that $\mathbf{z}\in\mathbf{s}^ {\bot}$, where each state is observed with equal probability.

Simon's algorithm solves the problem of determining $\mathbf{s}$ by repeating the operation just described by the circuit in the figure shown above. By observing the control register after the final measurement is made in each iteration of this circuit, elements of $\mathbf{s}^ {\bot}$ are effectively sampled uniformly at random. After a sufficient amount of samples are made from each iteration, the information obtained from the observed states $\left|z_i\right>$ can be used to construct the matrix $W$ whose rows consists of coefficients given by the strings $\mathbf{z_i}$. This allows the string $\mathbf{s}$ to be determined by finding the solutions to the matrix equation $W\mathbf{x}^T=\mathbf{0}^T$.

In regards to the query complexity of Simon's algorithm, it can be shown that the number of expected queries $Q(n)$ made to the black-box $c-U_f$, which is directly proportional to the number of iterations that need to be made to Simon's circuit, is less than $n$. In addition, the amount of other steps $S(n)$ needed to solve the matrix equation $W\mathbf{x}^T=\mathbf{0}^T$ is in $O(n^3)$.\cite{mosca}

It is presumed that this latter part of this algorithm of solving the matrix equation is performed through classical means. Therefore, the total time complexity of Simon's algorithm is $T(n)=Q(n)R(n)+S(n)=O(n)R(n)+O(n^3)$ for some function $R(n)$ representing the time complexity of implementing the black box $c-U_f$. Regardless, the total time complexity of Simon's algorithm is $\Omega(n^3)$. In the probabilistic  classical case, at least $\Omega(2^{n/3})$ queries must be made to some classical black box implementing the function $f$ in order to solve Simon's problem with a probability of success at least $2/3$. This requires resources exponentially larger than the quantum algorithm provided by Simon's. Thus, Simon's algorithm is our first example of an algorithm that can perform exponentially faster than any known classical algorithm.