EASTNORTHEAST - This is not exactly the hint Jim Sanborn (JS) gave for K4 on the 29th of January this year. He only gave NORTHEAST - which refers to the positions 26-34 of K4's plaintext. Beside BERLIN and CLOCK it is the third revealed plaintext word of K4. However, also this hint does not seem to help much. However, it just so happened, that a member in the yahoo kryptos group had a conversation with Jim Sanborn due to a submitted solution. Sandborn's answer to the question contained again the last clue which surprisingly was EASTNORTHEAST at position 22-34. Jim Sanborns compass rose at CIA There is disagreement if Jim revealed this on purpose or he did it accidentially, but the new extended clue seem to be serious and valid.Interestingly, EASTNORTHEAST is exactly the direction which is illustrated on the compass rose on one of the stones around kryptos, also created by Jim Sanborn. Actually, i dont really kn...
To show that quantum computers are indeed able to solve some problems more efficiently than classical computers, one of the first problems that were published was Simon's problem.
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.
| 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.
Comments
Post a Comment