## 11.7 Simon’s algorithm

Here we will see the simplest quantum algorithm that offers an *exponential* speed-up when compared to the best possible classical algorithm.

We are presented with an oracle that computes some unknown function **period** of ^{181}
(We assume that *not* the string of

Our task is to determine, using the fewest queries possible, the value of the

Classically, this problem is exponentially hard.
We will not go through a detailed proof of this fact, but the intuition is reasonably simple: since there is no structure in the function

The quantum case, on the other hand, gives a result (again, with “high” probability) within a *linear* number of steps.
The circuit that solves this problem, shown below, has a familiar Hadamard–function–Hadamard structure, but the second register has now been expanded to

(Simon’s problem).

*First register: n qubits. Second register: n qubits.*

This time, let’s follow the evolution of *both* registers throughout this circuit.
We start off by preparing the equally-weighted superposition of all

But if we measure^{182} the second register *before* applying the second Hadamard transform to the first register, we obtain one of the

Suppose that the outcome of the measurement is ^{183}

In fact, we did not have to measure the second register at all: it was a mathematical shortcut, simply taken for pedagogical purposes.
Instead of collapsing the state to just one term in a superposition, we can express Equation (^{184} formal statement: for all *two* elements or *none*; if it’s the latter, then we don’t include *pick one* and call it

We are not quite done yet: we cannot infer *single* output ^{185} *two* elements, since then we know that we can just take the non-zero one.)

So we run this algorithm repeatedly, each time obtaining another value of

Now, the probability that *outside* the subspace spanned by the

We can bound Equation (^{186}
the probability of obtaining a linearly independent set

We conclude that we can determine

Asking for

f to be periodic is equivalent to asking thatf be**two-to-one**: for anyy\in\{0,1\}^n such that there exists somex\in\{0,1\}^n withf(x)=y , there exists*exactly one other*x'\neq x such thatf(x')=y as well.↩︎As we shall see in a moment, the actual measurement on the second register is not actually necessary.↩︎

We write

s^\perp to mean the set of ally\in\{0,1\}^n such thaty\cdot s=0 .↩︎Another (complicated sounding) way of expressing this sum is by choice of a

**section**off , i.e. picking*one*elementa_z in*each*preimagef^{-1}(z) is equivalent to defining a functiona\colon\{0,1\}^n\to\{0,1\}^n bya\mapsto a_z which satisfies(a\circ f)(z)=z , ora\circ f=\mathbf{1} .↩︎It is important to note that we are talking about the pure “abstract”

*binary strings*, and not the corresponding states in the Hilbert space. Concretely, this means that**linearly independent**here means “no string in the set\{y_1,\ldots,y_n\} can be expressed as the bitwise sum of some other strings in this set”. That is, we are working with the\mathbb{Z}/2\mathbb{Z} -vector space of strings, not the\mathbb{C} -vector space of states!↩︎Use the inequality

\begin{aligned}(1-x)(1-y)&= 1 - x - y - xy\\&\geqslant 1 - (x+y)\end{aligned} which holds for any0<x,y<1 .↩︎