1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
|
---
title: "Simon's algorithm"
sort_title: "Simon's algorithm"
date: 2021-05-01
categories:
- Quantum information
- Algorithms
layout: "concept"
---
**Simon's algorithm** was the first proof that quantum computers
are able to solve some problems *exponentially* faster
than classical computers.
In the same spirit as
the [Deutsch-Jozsa algorithm](/know/concept/deutsch-jozsa-algorithm/)
and the [Bernstein-Vazirani algorithm](/know/concept/bernstein-vazirani-algorithm/),
the problem it solves, known as **Simon's problem**,
is of no practical use,
but nevertheless Simon's algorithm is an important milestone.
Simon's problem is this:
we are given a "black box" function $$f(x)$$
that takes an $$n$$-bit input $$x$$
and returns an $$n$$-bit output.
We are promised that there exists an $$s$$ such that for all $$x_1$$ and $$x_2$$:
$$\begin{aligned}
f(x_1)
= f(x_2)
\qquad \Leftrightarrow \qquad
x_2
= s \oplus x_1
\end{aligned}$$
In other words, regardless of what $$f(x)$$ does behind the scenes,
its output is the same for inputs $$x_1$$ and $$x_2$$
if and only if $$x_2 = s \oplus x_1$$,
or, equivalently, $$x_1 = s \oplus x_2$$.
The goal is to find the $$n$$-bit number $$s$$, using as few calls to $$f$$ as possible.
There are two cases:
if $$s = 0$$, then $$f$$ is one-to-one, since $$x_2 = 0 \oplus x_1 = x_1$$.
Otherwise, if $$s \neq 0$$, then $$f$$ is two-to-one by definition:
for every $$x_1$$ there exists exactly one $$x_2$$ such that $$x_2 = s \oplus x_1$$.
A classical computer solves this by randomly guessing inputs,
until it finds two that give the same output,
and then $$s = x_1 \oplus x_2$$.
For $$n$$-bit numbers, this takes $$\mathcal{O}(\sqrt{2^n})$$ guesses
(the square root is due to the birthday paradox).
A quantum computer needs to query $$f$$ only $$\mathcal{O}(n)$$ times,
although the exact number varies due to the algorithm's probabilistic nature.
It uses the following circuit:
{% include image.html file="simons-circuit.png" width="52%"
alt="Simon's circuit" %}
The XOR oracle $$U_f$$ implements $$f$$,
and has the following action for $$n$$-bit $$a$$ and $$b$$:
$$\begin{aligned}
\Ket{a} \Ket{b}
\quad \to \boxed{U_f} \to \quad
\Ket{a} \Ket{b \oplus f(a)}
\end{aligned}$$
Starting from the state $$\Ket{0}^{\otimes 2 n}$$,
we apply the [Hadamard gate](/know/concept/quantum-gate/) $$H$$
to each of the first $$n$$ qubits:
$$\begin{aligned}
\Ket{0}^{\otimes n} \Ket{0}^{\otimes n}
\quad \to \boxed{H^{\otimes n}} \to \quad
\Ket{+}^{\otimes n} \Ket{0}^{\otimes n}
= \frac{1}{\sqrt{2^n}} \sum_{x = 0}^{2^n - 1} \Ket{x} \Ket{0}^{\otimes n}
\end{aligned}$$
Where $$\Ket{x}$$ is shorthand for $$\Ket{x}_1 \cdots \Ket{x}_n$$.
In other words, we now have an equal superposition of all possible inputs $$x$$,
with a constant $$\Ket{0}^{\otimes n}$$ beside it.
We give this to the oracle $$U_f$$:
$$\begin{aligned}
\frac{1}{\sqrt{2^n}} \sum_{x = 0}^{2^n - 1} \Ket{x} \Ket{0}^{\otimes n}
\quad \to \boxed{U_f} \to \quad
\frac{1}{\sqrt{2^n}} \sum_{x = 0}^{2^n - 1} \Ket{x} \Ket{f(x)}
\end{aligned}$$
Then we apply $$H^{\otimes n}$$ to the first $$n$$ qubits again,
which, thanks to the definition of the Hadamard transform,
yields the following,
where $$x \cdot y$$ is the bitwise dot product:
$$\begin{aligned}
\frac{1}{\sqrt{2^n}} \sum_{x = 0}^{2^n - 1} \Ket{x} \Ket{f(x)}
\quad \to \boxed{H^{\otimes n}} \to \quad
&\frac{1}{\sqrt{2^n}} \sum_{x = 0}^{2^n - 1}
\bigg( \frac{1}{\sqrt{2^n}} \sum_{y = 0}^{2^n - 1} (-1)^{x \cdot y} \Ket{y} \bigg) \Ket{f(x)}
\end{aligned}$$
Next, we measure all qubits.
The order in which we do this does not matter,
but, for clarity, let us measure the last $$n$$ qubits first,
yielding $$\Ket{f(x_1)}$$ for some $$x_1$$.
Doing this leaves the $$2n$$ qubits in the following state,
where $$f(x_1) = f(x_2)$$ and $$x_2 = s \oplus x_1$$:
$$\begin{alignedat}{2}
&\mathrm{if} \: s = 0: \qquad
&&\bigg( \frac{1}{\sqrt{2^{n}}} \sum_{y = 0}^{2^n - 1} (-1)^{x_1 \cdot y} \Ket{y} \bigg) \Ket{f(x_1)}
\\
&\mathrm{if} \: s \neq 0: \qquad
&&\bigg( \frac{1}{\sqrt{2^n}} \sum_{y = 0}^{2^n - 1} \frac{1}{\sqrt{2}} \Big( (-1)^{x_1 \cdot y} + (-1)^{x_2 \cdot y} \Big) \Ket{y} \bigg) \Ket{f(x_1)}
\end{alignedat}$$
If $$s = 0$$, we get an equal superposition of all $$y$$,
so when we measure the first $$n$$ qubits,
the result is a uniformly random number,
regardless of the phase $$(-1)^{x_1 \cdot y}$$.
If $$s \neq 0$$, we get an "extra superposition",
since $$x_1 \neq x_2$$ but both are candidate inputs.
This is a more interesting situation,
because we can only measure $$y$$-values where:
$$\begin{aligned}
0
\neq (-1)^{x_1 \cdot y} + (-1)^{x_2 \cdot y}
\end{aligned}$$
Since $$x_2 = s \oplus x_1$$ by definition,
we can rewrite this as follows:
$$\begin{aligned}
0
\neq (-1)^{x_1 \cdot y} + (-1)^{x_1 \cdot y \oplus s \cdot y}
= (-1)^{x_1 \cdot y} + (-1)^{x_1 \cdot y} (-1)^{s \cdot y}
\end{aligned}$$
Clearly, this expression can only be nonzero if $$s \cdot y$$ is even.
In other words, when we measure the first $$n$$ qubits,
we get a random $$y$$-value,
for which $$s \cdot y$$ is guaranteed to be even.
In both cases $$s = 0$$ and $$s \neq 0$$,
measuring the first $$n$$ qubits gives a $$y$$-value satisfying:
$$\begin{aligned}
s \cdot y
= 0 \:\bmod 2
\end{aligned}$$
This tells us something about $$s$$, albeit not much.
But if we run Simon's algorithm $$N$$ times,
we get various $$y$$-values $$y_1, ..., y_N$$,
from which we can build a system of linear equations:
$$\begin{aligned}
s \cdot y_1
&= 0 \:\bmod 2
\\
s \cdot y_2
&= 0 \:\bmod 2
\\
&\:\:\vdots
\\
s \cdot y_N
&= 0 \:\bmod 2
\end{aligned}$$
This can be solved efficiently by a classical computer.
In the best-case scenario, all those $$y$$-values would be linearly independent
(when regarded as vectors of bits),
in which case only $$N = n - 1$$ equations would be necessary.
Simon's algorithm is therefore $$\mathcal{O}(n)$$.
It may feel like "cheating" to use a classical computer at the end.
Remember that the point of this algorithm is to limit the number of oracle queries,
which we did successfully.
Querying an oracle might be a very expensive operation,
so that is a big improvement!
That said, Simon's algorithm currently has no known practical uses.
## References
1. J.S. Neergaard-Nielsen,
*Quantum information: lectures notes*,
2021, unpublished.
2. S. Aaronson,
*Introduction to quantum information science: lecture notes*,
2018, unpublished.
|
