| Definition [Simon's problem] Let $f:\{0,1\}^n \rightarrow \{0,1\}^n$ with the property that for $x,y \in \{0,1\}^n$ it is $f(x) = f(y)$ if and only if $x = y \oplus a$, for some fix value $a \in \{0,1\}^n$. Given $f$, the task is to find $a$. |
As usual the $\oplus$ is the bitwise XOR-function. On a classical computer, Simon's problem can only be solved in time that is exponential in $n$, whereof on a QC already $\mathcal{O}(n)$ queries are enough.
Simon's problem can also be seen as some kind of period finding problem. Assume you have a function $f$ and for $f$ it holds that:
\begin{align}
f(1) &= e_1 \\
f(2) &= e_2 \\
... &\\
f(a-1) &= e_{a-1}\\
f(a) &= e_a = 1\\
f(a+1) &= f(1) = e_1\\
f(a+2) &= f(2) = e_2 \\
... &
\end{align}
A non-trivial function that behaves like this is, e.g., the function $f_{p,g}(x) = g^x \pmod{p}$, if $a$ is the order of $g$ in $\mathbb{F}^*_p$ and whenever $x \oplus a = x+a$. This is a very special setup and is almost always not fulfilled for random primes $p$. But, e.g., whenever $a = 2^t$ and $p-1=2^{t+1}$ this holds. For example $p=17$ and $g=2$. Then $f_{17,2}(x)$ has the described property and is a valid function according to Simon's problem definition.
I mention this here, because finding the order of a given integer $a \in \mathbb{Z}^*_n$ is exactly what Shor's quantum algorithm does and thus can be seen as a generalisation of this algorithm.
Where a classical computer is limited to execute the function $f$ for one integer after another, a QC does the following:
Assume that $n = 4$ and we take the function $f_{17,2}$. We prepare two quantum registers of $n=4$ bits, that are all initialized with $0$'s.
\begin{align}
R_1 &= \left(1\cdot |0\rangle + 0\cdot |1\rangle\right) \left(1\cdot |0\rangle + 0\cdot |1\rangle\right) \left(1\cdot |0\rangle + 0\cdot |1\rangle\right) \left(1\cdot |0\rangle + 0\cdot |1\rangle\right) \\
R_2 &= \left(1\cdot |0\rangle + 0\cdot |1\rangle\right) \left(1\cdot |0\rangle + 0\cdot |1\rangle\right) \left(1\cdot |0\rangle + 0\cdot |1\rangle\right) \left(1\cdot |0\rangle + 0\cdot |1\rangle\right) \\
\end{align} First, the Hadamard-Operation $\mathcal{R}_n$
\begin{equation}
\mathcal{R}_n: |x\rangle \mapsto \frac{1}{2^{n/2}}\sum^{2^n-1}_{u=0}(-1)^{x\odot u}|u\rangle
\end{equation}
is applied to the first register, which creates the uniform state, i.e., every integer from $0$ to $15$ is measured with the same probability of $1/16$. The operation $\odot$ is the following:
If the binary representation of $u$ and $x$ are $u_{n-1}u_{n-2}...u_1u_0$ and $x_{n-1}x_{n-2}...x_1x_0$ respectively, then $x\odot u = \sum^{n-1}_{i=0}u_ix_i $. So we can write $R_1$ as
\begin{align}
R_1 &= \\
& \left(\frac{1}{\sqrt{2}}|0\rangle + \frac{1}{\sqrt{2}}|1\rangle\right) \left(\frac{1}{\sqrt{2}}|0\rangle + \frac{1}{\sqrt{2}}|1\rangle\right) \left(\frac{1}{\sqrt{2}}|0\rangle + \frac{1}{\sqrt{2}}|1\rangle\right) \left(\frac{1}{\sqrt{2}}|0\rangle + \frac{1}{\sqrt{2}}|1\rangle\right)\end{align}
and written in another way (after using the distributive law) it is
\begin{align}
R_1 = &\frac{1}{4}|0000\rangle + \frac{1}{4}|0001\rangle + \frac{1}{4}|0010\rangle + \frac{1}{4}|0011\rangle\\
&\frac{1}{4}|0100\rangle + \frac{1}{4}|0101\rangle + \frac{1}{4}|0110\rangle + \frac{1}{4}|0111\rangle\\
&\frac{1}{4}1000\rangle + \frac{1}{4}|1001\rangle + \frac{1}{4}|1010\rangle + \frac{1}{4}1011\rangle\\
&\frac{1}{4}|1100\rangle + \frac{1}{4}|1101\rangle + \frac{1}{4}|1110\rangle + \frac{1}{4}|1111\rangle\\
= &\frac{1}{4}\sum^{15}_{x=0} |x\rangle
\end{align} So each value is measure with the probablity $(1/4)^2 = 1/16$. Then the function $f_{17,2}$ is applied, thereby entagling the first register $R_1$ with the $R_2$.
\begin{align}
R_2 = &\frac{1}{4}|f_{17,2}(0)\rangle + \frac{1}{4}|f_{17,2}(1)\rangle + \frac{1}{4}|f_{17,2}(2)\rangle + \frac{1}{4}|f_{17,2}(3)\rangle\\
&\frac{1}{4}|f_{17,2}(4)\rangle + \frac{1}{4}|f_{17,2}(5)\rangle + \frac{1}{4}|f_{17,2}(6)\rangle + \frac{1}{4}|f_{17,2}(7)\rangle\\
&\frac{1}{4}|f_{17,2}(8)\rangle + \frac{1}{4}|f_{17,2}(9)\rangle + \frac{1}{4}f_{17,2}(10)\rangle + \frac{1}{4}|f_{17,2}(11)\rangle\\
&\frac{1}{4}|f_{17,2}(12)\rangle + \frac{1}{4}|f_{17,2}(13)\rangle + \frac{1}{4}|f_{17,2}(14)\rangle + \frac{1}{4}|f_{17,2}(15)\rangle\\
= &\frac{1}{4}\sum^{15}_{x=0} |f_{17,2}(x)\rangle
\end{align} Writing this together in one equation is
\begin{equation}
R_1R_2 = \frac{1}{4}\sum^{15}_{x=0}|x\rangle|f_{17,2}(x)\rangle
\end{equation}
We next apply the Hadamard operations $\mathcal{R}_{4}$ to the first register $R_1$
\begin{align}
R_1R_2 &= \frac{1}{4}\sum^{15}_{x=0} \frac{1}{4}\sum^{15}_{u=0}(-1)^{x\odot u}|u\rangle|f_{17,2}(x)\rangle\\
&= \frac{1}{16}\sum^{15}_{x=0} \sum^{15}_{u=0}(-1)^{x\odot u}|u\rangle|f_{17,2}(x)\rangle
\end{align} If we define $\mathcal{S}$ to be the subset of $\{0,1,2,...,15\}$, that contains all integers that create distinct $f$ values (in our particular case $\mathcal{S}$ would be $\{0,1,...,7\}$ since $x \oplus a = x + a$) we can write
\begin{align}
R_1R_2 &= \frac{1}{16}\sum_{x\in \mathcal{S}} \sum^{15}_{u=0}\left((-1)^{x\odot u}+(-1)^{(x\oplus a) \odot u}\right)|u\rangle|f_{17,2}(x)\rangle
\end{align} and this is the only step were we used that $f(x) = f(x\oplus a)$. Furthermore, since the base element is $(-1)$ and thus we are actually working modulo $2$, for the $\odot$ operation and the $\oplus$ operation the following holds $$(-1)^{(x\oplus a) \odot u} = (-1)^{x\odot u}(-1)^{a\odot u}$$
Proof. We have to show that $(x\oplus a)\odot u \equiv x\odot u + a\odot u \pmod{2}$. Let $x\oplus a = z = z_{u-1}z_{u-2}...z_1z_0$ in binary form. Then it is to $z_i \equiv x_i + a_i \pmod{2}$ so
\begin{align}
(x\oplus a)\odot u & = z\odot u \\
& \equiv \sum^{n-1}_{i=0} z_iu_i \pmod{2}\\
& \equiv \sum^{n-1}_{i=0} (x_i+a_i)u_i \pmod{2}\\
& \equiv \sum^{n-1}_{i=0} x_iu_i+\sum^{n-1}_{i=0}a_iu_i \pmod{2}\\
& \equiv x\odot u+ a\odot u \pmod{2}
\end{align} Q.e.d.
Using this result, we can rewrite the last equation for $R_1R_2$ to
\begin{align}
R_1R_2 &= \frac{1}{16}\sum_{x\in \mathcal{S}} \sum^{15}_{u=0}(-1)^{x\odot u}\left(1+(-1)^{a\odot u}\right)|u\rangle|f_{17,2}(x)\rangle
\end{align} Lets take a look at the term $(-1)^{x\odot u}(1+(-1)^{a\odot u})$, which defines the probability to measure a certain state $|u\rangle$. So this is
\begin{equation}
(-1)^{x\odot u}(1+(-1)^{a\odot u}) =
\begin{cases}
0, & \text{if }\sum^{n-1}_{i=0}a_iu_i \equiv 1\pmod{2}\\
(-1)^{x\odot u}2, & \text{if }\sum^{n-1}_{i=0}a_iu_i \equiv 0\pmod{2}\\
\end{cases}
\end{equation} But this means, that, if me measure the first register $R_1$, we will only see states (i.e. integers) $|u\rangle$ that have $\sum^{n-1}_{i=0}a_iu_i \equiv 0\pmod{2}$. And each of this states is measured with equal probability. Other states $|u\rangle$ can not be measured, since their probability to occur is zero.
If we repeat this $n$-times, we get $n$ different integers $u$, hence we get (probably) $n$ independent equations (if not, repeat this a few more times) of the form
\begin{align}
a \odot u^1 & = a_{n-1}u^1_{n-1} + a_{n-2}u^1_{n-2} + ... + a_1u^1_{1} + a_0u^1_0 \equiv 0 \pmod{2}\\
... & = ... \\
a \odot u^n & = a_{n-1}u^n_{n-1} + a_{n-2}u^n_{n-2} + ... + a_1u^n_{1} + a_0u^n_0 \equiv 0 \pmod{2}
\end{align} with known $u^i_j$ and only $n$ unkowns $a_i$. This equation system can be uniquely solved for these $a_i$ which are the bits of $a$.
Is it possible to cover more problems than Simon's problem with this approach? E.g., some variation of the definition. For example from $f(x) = f(x\oplus a)$ to e.g. $f(x) = f(x\;\text{AND}\;a)$ or $f(x) = f(x\;\text{OR}\;a)$? For the latter, the resulting probablity term is $$(-1)^{x\odot u}(1+(-1)^{a\odot u - x\odot a\odot u})$$ and the $x$ in the exponent $x\odot a\odot u$ is very annoying.
No comments:
Post a Comment