In this post I want to talk about a thing from the Kryptos universe that are not directly related to the statue. But i think it may be an indirect hint to some Kryptos related methods. The Mayan Symbols in Ed Scheidts driveway I think everyone who knows Kryptos knows Ed Scheidt. The former Chairman of the Cryptographic Center at the CIA and founder of the cryptosystems used around the Kryptos statue. As already shown in Part 4 of my Kryptos series, in the driveway of Ed Scheidts house, there are two symbols: Figure 1 - Garage driveway of Ed Scheidt We denote the left symbol set with $S_1$ and the right one with $S_2$. It took me a while to find his house on Google Maps - Street View. To save you some time, here is the link with a view on the driveway. I you go back in time in Streetview, you can see that the symbols were already there in 2012. But it is impossible to say when they were built. $S_1$ is clearly visible from the street, $S_2$ is hidden in the view. But you can u...
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