Simon’s algorithm · Kets & Gates

1 / 15 · Learn

Before you start

Lesson 14 counted queries and found a hidden string with a single one, where a classical computer needs $n$ : a gap of $n$ against 1. This lesson hides a string $s$ in a different way, and the gap becomes exponential, even against classical methods that are allowed to guess. Part A: the problem, the classical cost and one run of the circuit. Part B: from runs to $s$ , the size of the gap, and the algorithm in Qiskit.

By the end of this lesson you can:

state Simon’s problem and find $s$ from any collision $f(x) = f(x')$ ;
count pairs of queries to estimate how many random classical queries it takes to find $s$ ;
follow one run of Simon’s circuit and say what its result tells you about $s$ ;
solve the equations $y\cdot s = 0$ for $s$ by elimination over bits, and say how many runs that takes;
build the circuit in Qiskit and read its counts.

Check yourself

A warm-up: make a guess before reading on. The lesson comes back to it.

Simon’s circuit for $n = 3$ hides a string, say $s = 110$ . The circuit is run once and its 3 input qubits are measured. What does that one result give you?

AThe hidden string $s$ itself
BThe value $f(x)$ at one random input $x$
CA random string $y$ with $y\cdot s = 0$ : one equation that $s$ must satisfy
D $s$ with probability $\tfrac12$ , otherwise a random string

Show the answer

Answer: C. A random string $y$ with $y\cdot s = 0$ : one equation that $s$ must satisfy

After the query and the last Hadamards, the inputs hold a string $y$ chosen uniformly from the $2^{n-1} = 4$ strings with $y\cdot s = 0$ . One such $y$ is one equation for the bits of $s$ ; about $n$ runs give enough equations to solve for $s$ .

Why not the others

A. One run gives a random string $y$ with $y\cdot s = 0$ : $000$ , $001$ , $110$ or $111$ , each with probability $\tfrac14$ . The result can be $000$ , which says nothing at all. It takes several runs, and some algebra, to pin $s$ down.
B. That is what you get by measuring right after the query, as in Lesson 9. Simon’s circuit adds Hadamards after the query, and the measured inputs then hold a string $y$ with $y\cdot s = 0$ , not an input of $f$ .
D. No allowed result is more likely than another: each of the $4$ strings with $y\cdot s = 0$ has probability $1/4$ . Even when the result happens to equal $s$ , nothing in the run tells you so.

Check yourself

A warm-up: make a guess before reading on. The lesson comes back to it.

A classical program attacks Simon’s problem for $n = 20$ by querying random inputs until two of them give the same value. Roughly how many queries does that take?

AAbout 20, one per bit
BAbout $2^{10} = 1{,}024$
CAbout $2^{19} \approx 520{,}000$
DAbout $2^{20} \approx 1.0\times10^{6}$

Show the answer

Answer: B. About $2^{10} = 1{,}024$

A good chance of a collision needs about as many pairs as there are candidates: $k^2/2 \approx 2^{20}$ , so $k$ is of order $2^{10}$ . On average random queries take about $1.25\cdot2^{10}$ , roughly $1{,}300$ .

Why not the others

A. A query returns a value $f(x)$ , not a bit of $s$ . 20 random queries make only 190 pairs, and each pair is a matching pair with chance $1/(2^{20} - 1)$ .
C. $2^{19} + 1$ queries make a collision certain, since there are only $2^{19}$ different values. Random queries collide much sooner, because $k$ queries make about $k^2/2$ pairs: about $2^{10}$ queries already make about $2^{19}$ pairs.
D. You never need every input: $2^{19} + 1$ queries already force a collision. Random queries usually find one after about $2^{10}$ , since the number of pairs grows like $k^2/2$ .

2 / 15 · Learn

Part A · Simon’s problem

Part A covers the problem, what it costs a classical computer, and one run of the quantum circuit.

Simon’s problem is a promise problem, like Deutsch–Jozsa. A black box computes $f$ , which takes $n$ bits to $n$ bits. You are promised that there is a string $s$ , not all zeros, such that

f(x) = f(x') \iff x' = x \text{ or } x' = x\oplus s.

So the inputs come in pairs $\{x,\ x\oplus s\}$ . The two members of a pair share a value, and different pairs have different values: $f$ is two-to-one. The values themselves carry no pattern. All the structure is in which inputs collide. Your task is to find $s$ . The figure shows one such $f$ for $n = 3$ and $s = 110$ .

A function with the promise, for $n = 3$ and $s = 110$ . Each input’s partner is the input XOR $110$ : $000\oplus110 = 110$ , $001\oplus110 = 111$ , and so on. The four values are arbitrary; only the pairing matters.

Check yourself

Here $n = 3$ and $s = 101$ . You know $f(011) = 001$ . Which other input has the value $001$ ?

ANone: $f$ gives each value only once
B $001$
C $100$
D $110$
E $101$

Hints

Which input is paired with this one?
Its partner is $x\oplus s$ : XOR the two strings bit by bit.

Show the answer

Answer: D. $110$

$f(x) = f(x\oplus s)$ , so the partner of $011$ is $011\oplus101 = 110$ , and $f(110) = 001$ as well.

Why not the others

A. That would make $f$ one-to-one. The promise makes it two-to-one: $x$ and $x\oplus s$ always share a value, so $f(110) = 001$ too.
B. That is the value $f(011)$ , not an input. The other input with this value is the partner $011\oplus s = 110$ .
C. That flips every bit of $011$ , which is $011\oplus111$ . It would be the partner only if $s = 111$ . XOR with $s = 101$ flips only the bits where $s$ has a 1: $110$ .
E. That is $s$ itself, the difference between partners. The partner of $011$ is $011\oplus101$ : XOR bit by bit, which gives $110$ .

In a circuit, $f$ becomes the oracle of Lesson 9 with a wider output: $n$ input qubits, $n$ output qubits, and

U_f\ket{x}\ket{b} = \ket{x}\ket{b\oplus f(x)},

where $b\oplus f(x)$ is XOR bit by bit. (The output’s contents are called $b$ here, because $y$ will name something else.) With the outputs starting at $0\ldots0$ , one query writes $f(x)$ there. A classical query is the same call on a single input. Either way, the cost we count is the number of calls, as in Lesson 14.

Classically, a collision settles everything: two different inputs with the same value. $f(x) = f(x')$ with $x \ne x'$ forces $x' = x\oplus s$ , so $s = x\oplus x'$ .

Check yourself

You query $f$ for $n = 4$ and find $f(0110) = f(1011)$ . What is $s$ ?

AYou can’t tell yet: more queries are needed
B $0110$
C $1101$
D $0010$

Hints

When can two different inputs share a value?
Only when they differ by $s$ , so XOR them.

Show the answer

Answer: C. $1101$

Two different inputs with the same value must be partners, $x' = x\oplus s$ , so $s = x\oplus x' = 0110\oplus1011 = 1101$ .

Why not the others

A. One collision is enough. Two different inputs with the same value must be partners, $x' = x\oplus s$ , so $s = 0110\oplus1011$ .
B. That is one of the inputs. The promise says two different inputs share a value only when they differ by $s$ , so $s$ is the XOR of the two: $1101$ .
D. That is the bitwise AND of the two inputs. Partners differ by $s$ , so $s$ is their XOR: $0110\oplus1011 = 1101$ .

3 / 15 · Learn

Part A · The classical cost: birthdays

Without a collision, a classical query teaches little. If $f(x) \ne f(x')$ , you learn only that $s \ne x\oplus x'$ : one candidate out of $2^n - 1$ is ruled out. Each pair of queried inputs is one such test, and $k$ queries make

\frac{k(k-1)}{2}

pairs. That count grows like $k^2/2$ , which is why collisions come sooner than you might expect. It is the birthday puzzle: a room of 23 people holds 253 pairs, and the chance that two of them share a birthday is just over 50%, although there are 365 possible days.

Check yourself

You have queried 40 different inputs and seen no collision yet. How many pairs of queried inputs is that? Each pair is one chance that two of them are partners.

Hints

Each new input can be compared with every input before it.
The 40th input adds 39 pairs; add them all up, or use $k(k-1)/2$ .

Show the answer

Answer: $780$

$k(k-1)/2 = 40\cdot39/2 = 780$ pairs: the second input makes 1 pair, the third 2 more, and the 40th 39 more.

Common slips

$1600$ : That is $40^2$ , which counts every pair twice and also pairs each input with itself. The count is $40\cdot39/2 = 780$ .
$1560$ : That counts each pair twice, once in each order. Divide by 2: $780$ .
$40$ : That is the number of queries. The tests are pairs: each new input is compared with every earlier one, $0 + 1 + \cdots + 39 = 780$ .

Now put in numbers for $n = 20$ . There are $2^{20} - 1 = 1{,}048{,}575$ candidates for $s$ , and each pair of queried inputs has a chance of about one in a million of being partners.

100 queries make $4{,}950$ pairs: a collision chance of about 0.5%.
$1{,}024 = 2^{10}$ queries make about $524{,}000$ pairs, as many as half the candidates: a chance of about 39%.
$2{,}048$ queries make about 2.1 million pairs: a chance of about 87%.

So a random search needs about $2^{n/2}$ queries, and on average about $1.25\cdot2^{n/2}$ , which is about $1{,}300$ for $n = 20$ . Simon proved that no classical algorithm does better than order $2^{n/2}$ queries, not even a randomized one that is allowed a small chance of error.

The chance of at least one collision after $k$ random queries for $n = 20$ , computed exactly. It is 39% at $k = 2^{10}$ , one half at about $k = 1{,}206$ , and 87% at $k = 2\cdot2^{10}$ : doubling the queries quadruples the pairs.

Check yourself

A classical program attacks Simon’s problem for $n = 40$ by querying random inputs until two of them give the same value. Roughly how many queries does that take?

AAbout 40, one per bit
BAbout $2^{20} \approx 1.0\times10^{6}$
CAbout $2^{39} \approx 5.5\times10^{11}$
DAbout $2^{40} \approx 1.1\times10^{12}$

Show the answer

Answer: B. About $2^{20} \approx 1.0\times10^{6}$

A good chance of a collision needs about as many pairs as there are candidates: $k^2/2 \approx 2^{40}$ , so $k$ is of order $2^{20}$ . On average random queries take about $1.25\cdot2^{20}$ , roughly $1.3\text{ million}$ .

Why not the others

A. A query returns a value $f(x)$ , not a bit of $s$ . 40 random queries make only 780 pairs, and each pair is a matching pair with chance $1/(2^{40} - 1)$ .
C. $2^{39} + 1$ queries make a collision certain, since there are only $2^{39}$ different values. Random queries collide much sooner, because $k$ queries make about $k^2/2$ pairs: about $2^{20}$ queries already make about $2^{39}$ pairs.
D. You never need every input: $2^{39} + 1$ queries already force a collision. Random queries usually find one after about $2^{20}$ , since the number of pairs grows like $k^2/2$ .

4 / 15 · Learn

Part A · One run of the circuit

Simon’s circuit has $2n$ qubits, all starting in $\ket0$ : $n$ inputs and $n$ outputs.

$H^{\otimes n}$ on the inputs gives every $x$ the same amplitude.
One query: $U_f$ writes $f(x)$ into the outputs, in every branch at once.
$H^{\otimes n}$ on the inputs again.
Measure the inputs. Call the result $y$ .

After step 2 the state is

\ket{\psi_2} = \frac{1}{\sqrt{2^n}}\sum_x \ket{x}\ket{f(x)}.

Group its terms by value. The two inputs of a pair share their value, so each value in the outputs sits beside two branches of the inputs, $\ket{x}$ and $\ket{x\oplus s}$ .

Simon’s circuit drawn with registers: each line stands for $n$ qubits (the slash and $n$ ). The output register may be measured after $U_f$ (dashed meter) or left alone. The inputs are measured at the end.

Check yourself

Take $n = 3$ . In $\ket{\psi_2}$ , how many terms $\ket{x}\ket{f(x)}$ have the value $f(x) = f(000)$ in the output register?

AEight: the query writes the same value in every branch
BTwo: $x = 000$ and $x = s$
COne: the term with $x = 000$
DFour: half of the eight inputs

Hint

Which inputs share a value with $000$ ?

Show the answer

Answer: B. Two: $x = 000$ and $x = s$

The inputs sharing a value with $000$ are $000$ and its partner $000\oplus s = s$ . So $f(000)$ appears in exactly two terms, and the four values split the eight terms into four pairs.

Why not the others

A. Each branch gets its own value $f(x)$ . The eight inputs make four pairs and four different values, two terms per value.
C. Under the promise $f$ is two-to-one. The partner $000\oplus s = s$ has the same value, so its term carries $f(000)$ too.
D. That would make $f$ four-to-one. Only $x$ and $x\oplus s$ share a value, and $000\oplus s = s$ , so two terms carry $f(000)$ .

Suppose you measure the output register now. You get one value, each of the $2^{n-1}$ values with probability $2/2^n$ . Only the two inputs with that value survive, so the inputs are left in

\frac{1}{\sqrt2}\big(\ket{x_0} + \ket{x_0\oplus s}\big),

where $x_0$ is either member of that pair. You can’t read $s$ from this state directly. Measuring it would give $x_0$ or $x_0\oplus s$ , one random input, and to compare the two you would need a second copy of the same pair, which you can’t make. The last Hadamards get information about $s$ out of a single copy.

Check yourself

Take $n = 3$ , $s = 110$ and the function in the figure of pairs above, so $f(001) = 010$ . After the query you measure the output register and get $010$ . Enter the state of the three input qubits, $\ket{000}$ to $\ket{111}$ .

Hints

Which inputs have the same value as $001$ ?
Those two branches keep equal amplitudes; renormalize so that the squares add up to 1.

Show the answer

Answer: $\frac{1}{\sqrt{2}}|001\rangle + \frac{1}{\sqrt{2}}|111\rangle$

The value $f(001)$ belongs to the pair $\{001, 111\}$ , since $001\oplus110 = 111$ . Those two branches survive with equal amplitudes, so the inputs are $(\ket{001} + \ket{111})/\sqrt2$ .

Do you have to measure the outputs? No. Nothing acts on them after $U_f$ , so the input measurement has the same statistics whether or not you look at the outputs first. Left alone, the outputs simply keep a record of which pair the inputs are in.

Compare Lesson 13, where leftover work qubits wrecked interference. Here the leftover register holds $f(x)$ , and that is the same for $x$ and $x\oplus s$ . So the two branches of a pair can still interfere with each other. Branches from different pairs can’t, because their outputs differ, but the algorithm never needs them to.

Check yourself

A student leaves out the measurement of the output register and measures only the inputs at the end. What happens to the results $y$ ?

AThe circuit fails: the inputs must collapse to one pair before the Hadamards
BNothing changes: every $y$ has the same probability as before
CThey become uniform over all $2^n$ strings: the inputs are entangled with the outputs, so nothing interferes
DEvery run now gives $s$ , because all the pairs interfere together

Hint

Does anything act on the output register after the query?

Show the answer

Answer: B. Nothing changes: every $y$ has the same probability as before

Nothing touches the outputs after $U_f$ , so measuring them or not leaves the input statistics unchanged. Unmeasured, the state is a sum over pairs, each pair tagged by its value in the outputs, and within each pair the two branches interfere exactly as in the measured case.

Why not the others

A. No collapse is needed. Each pair sits in its own branch of the output register, and the Hadamards act on every branch. Measuring the outputs only tells you which pair you had, and the statistics of $y$ are the same for every pair.
C. Entanglement with the outputs blocks interference only between branches whose outputs differ. The two branches of a pair share $f(x)$ , so they interfere as before, and the last Hadamards still cancel every $y$ with $y\cdot s = 1$ .
D. Different pairs never interfere: their outputs hold different values. With or without the output measurement, a run gives a random $y$ with $y\cdot s = 0$ , not $s$ .

5 / 15 · Learn

Part A · The last Hadamards

Predict, then see

Take $n = 2$ and $s = 10$ , with $f(x) = x_2$ , the second bit: $f(00) = f(10) = 0$ and $f(01) = f(11) = 1$ . Since $f$ takes only two values, one output qubit is enough. The circuit applies $H$ to both inputs, then $U_f$ (a CNOT from $x_2$ to the output), then $H$ to both inputs again. What will the two input qubits read?

A $10$ every time: the circuit reads out $s$
B $00$ or $10$ : the two inputs of one pair
CAny of the four strings, a quarter of the time each
D $00$ or $01$ , half the time each

Why do $10$ and $11$ never appear on the inputs? A sentence or two is enough.

Show what happens

What happens: D. $00$ or $01$ , half the time each

After $U_f$ the state is $\tfrac12(\ket{00} + \ket{10})\ket0 + \tfrac12(\ket{01} + \ket{11})\ket1$ : each output value sits beside one pair, $\{00, 10\}$ or $\{01, 11\}$ . The last Hadamards act on each pair. In $\ket{00} + \ket{10}$ the first qubit is $\ket0 + \ket1$ , and $H$ turns it into $\ket0$ ; the second qubit is $\ket0$ and becomes $\ket+$ . The other pair gives $\ket0\ket-$ . Either way the first bit of $y$ is 0 and the second is random: $y$ is $00$ or $01$ , exactly the strings with $y\cdot s = y_1 = 0$ . The string $s = 10$ never appears.

Why not the others

A. The widget never shows $10$ on the inputs. It shows $00$ and $01$ , about half the time each. A run gives a string $y$ with $y\cdot s = 0$ , and $10\cdot10 = 1$ .
B. Those are the two members of the pair $\{00, 10\}$ , which is what you would read just before the last Hadamards. The Hadamards change that: the widget shows $00$ and $01$ .
C. The Hadamards don’t just spread amplitude around. Two of the four strings get contributions that cancel exactly: in the widget, $10$ and $11$ never appear on the inputs.

Here is the general calculation. Lesson 9 gave $H^{\otimes n}\ket{x} = \frac{1}{\sqrt{2^n}}\sum_y(-1)^{x\cdot y}\ket{y}$ . Apply it to both branches of a pair:

\begin{aligned}&H^{\otimes n}\,\tfrac{1}{\sqrt2}\big(\ket{x} + \ket{x\oplus s}\big) \\ &\quad= \tfrac{1}{\sqrt{2^{n+1}}}\sum_y\big[(-1)^{x\cdot y} + (-1)^{(x\oplus s)\cdot y}\big]\ket{y}.\end{aligned}

The dot product splits over XOR, $(x\oplus s)\cdot y = x\cdot y\oplus s\cdot y$ , so the bracket is

(-1)^{x\cdot y}\big(1 + (-1)^{s\cdot y}\big).

If $s\cdot y = 1$ , the two terms cancel and $\ket{y}$ gets amplitude 0. If $s\cdot y = 0$ , they add, giving amplitude $\pm2/\sqrt{2^{n+1}} = \pm1/\sqrt{2^{n-1}}$ . So the measurement gives each of the $2^{n-1}$ strings with $s\cdot y = 0$ with probability $1/2^{n-1}$ , whichever pair you had: $x$ only sets the signs.

The last Hadamards on $(\ket{001} + \ket{111})/\sqrt2$ , for $s = 110$ . Each $\ket{y}$ gets one sign from each branch. Where $s\cdot y = 1$ the signs are opposite and cancel (shaded rows); where $s\cdot y = 0$ they agree, and $\ket{y}$ gets amplitude $\pm2/\sqrt{16} = \pm\tfrac12$ .

Check yourself

Simon’s circuit with $n = 3$ and $s = 110$ . After the query the inputs are in $(\ket{010} + \ket{100})/\sqrt2$ . What is the amplitude of $\ket{111}$ after the last Hadamards?

Hints

Each branch $\ket x$ gives $\ket{111}$ the term $(-1)^{x\cdot y}/\sqrt{2^{4}}$ .
Compute $010\cdot111$ and $100\cdot111$ ; equal dot products add, different ones cancel.

Show the answer

Answer: $-\frac{1}{2}$

$010\cdot111 = 1$ and $100\cdot111 = 1$ , so the two terms are $-1/\sqrt{2^{4}}$ and $-1/\sqrt{2^{4}}$ . They add, since $s\cdot y = 0$ : the amplitude is $-\frac{1}{2}$ .

Common slips

$\frac{1}{2}$ : Right size, wrong sign. Both branches give $\ket{111}$ the sign $-1$ , because $010\cdot111 = 1$ and $100\cdot111 = 1$ .
$\frac{1}{4}$ : That is the probability, the squared amplitude. The amplitude itself is $-\frac{1}{2}$ .
$-\frac{1}{4}$ : That counts only the branch $\ket{010}$ . Its partner $\ket{100}$ adds an equal term, since $s\cdot y = 110\cdot111 = 0$ : together $-\frac{1}{2}$ .
$0$ : The two branches cancel only when $s\cdot y = 1$ . Here $110\cdot111 = 0$ , so they add.

Check yourself

Simon’s circuit runs with $n = 3$ and $s = 111$ . Which results $y$ can the input measurement give? Choose all that are possible.

Select all that apply.

A $101$
B $110$
C $011$
D $001$
E $111$
F $000$

Hint

$y$ appears only if $y\cdot s = 0$ . What is $y\cdot111$ in words?

Show the answer

Answers: A. $101$ ; B. $110$ ; C. $011$ ; F. $000$

$y\cdot111 = y_1\oplus y_2\oplus y_3$ , so the possible results are the strings with an even number of 1s: $000$ , $011$ , $101$ and $110$ , each with probability $\tfrac14$ .

Why not the others

D. $001\cdot111 = 1$ , so the two branches of every pair cancel on $\ket{001}$ .
E. That is $s$ itself. Here $s\cdot s = 1\oplus1\oplus1 = 1$ , so the two branches of every pair cancel on $\ket{111}$ : with an odd number of 1s, $s$ is never a result.

6 / 15 · Learn

Part A · Build one run

Now build a whole run yourself, for $n = 2$ and $s = 11$ . A function with this promise is $f(x) = x_1\oplus x_2$ : $f(00) = f(11) = 0$ and $f(01) = f(10) = 1$ . One output qubit can hold it, and the oracle is two CNOTs, one from each input into the output.

Check yourself

Build Simon’s circuit for $n = 2$ and $s = 11$ on three wires (the inputs $x_1$ , $x_2$ and the output), with the oracle for $f(x) = x_1\oplus x_2$ . Leave out the measurement.

Build it in the circuit builder (gates: H, CNOT, control, X).

Hints

Three stages: Hadamards on the inputs, the oracle, Hadamards on the inputs again.
The oracle adds $x_1$ and then $x_2$ to the output: a CNOT from each input to the output.
Column 1: $H$ on $x_1$ and $x_2$ . Columns 2 and 3: a CNOT from $x_1$ to the output, then one from $x_2$ . Column 4: $H$ on both inputs.

Show the answer

One circuit that works: H on q0 and q1, then CNOT q0→q2, then CNOT q1→q2, then H on q0 and q1.

The state is $\tfrac12\big(\ket{00}\ket0 + \ket{11}\ket0 + \ket{00}\ket1 - \ket{11}\ket1\big)$ , so the inputs read $00$ or $11$ : the strings with $y_1\oplus y_2 = 0$ . That $11$ equals $s$ is a coincidence of this $s$ : $11\cdot11 = 1\oplus1 = 0$ . With $s = 10$ , earlier, $s$ never appeared.

7 / 15 · Learn

Part B · From equations to s

Part B turns runs into $s$ , measures the size of the gap, and writes the algorithm in Qiskit.

Each run gives a string $y$ , and with it one equation for the bits of $s$ :

y\cdot s = y_1s_1\oplus y_2s_2\oplus\cdots\oplus y_ns_n = 0.

For $n = 3$ , $y = 111$ says $s_1\oplus s_2\oplus s_3 = 0$ : $s$ has an even number of 1s. That rules out four of the seven candidates and leaves $011$ , $101$ and $110$ . A second run with $y = 001$ says $s_3 = 0$ , which leaves only $110$ .

Some runs add nothing. $y = 0\ldots0$ gives $0 = 0$ , and a $y$ that is the XOR of earlier results gives an equation you could already get by adding theirs. What you need are $n - 1$ independent equations. Each one halves the solutions, from $2^n$ down to exactly two: $0\ldots0$ and $s$ . Since $s \ne 0\ldots0$ , it is the other one.

Before any run

After run 1

After run 2

The candidates for $s$ with $n = 3$ , as two runs come in. $y = 111$ keeps the strings with an even number of 1s; $y = 001$ keeps those that end in 0. Two independent equations, $n - 1 = 2$ , leave one candidate.

Refresher: Bits, XOR and bit strings Equations over bits: XOR as addition, the dot product mod 2, and elimination, with practice.

Check yourself

Simon’s circuit with $n = 3$ gives $y = 011$ and then $y = 110$ . Which string is $s$ ?

A $101$
BNot enough runs yet: three bits need three equations
C $000$
D $011$
E $111$

Hint

Write the two equations $y\cdot s = 0$ in terms of $s_1$ , $s_2$ , $s_3$ .

Show the answer

Answer: E. $111$

$y = 011$ gives $s_2\oplus s_3 = 0$ and $y = 110$ gives $s_1\oplus s_2 = 0$ , so $s_1 = s_2 = s_3$ . The solutions are $000$ and $111$ , and $s \ne 000$ , so $s = 111$ .

Why not the others

A. $101 = 011\oplus110$ gives a third equation you can derive, $s_1\oplus s_3 = 0$ ; it is not a solution. Test it: $011\cdot101 = 1$ , so it breaks the first equation.
B. Two independent equations are enough for $n = 3$ . They leave two solutions, $000$ and $s$ , and $s$ is the nonzero one.
C. $000$ satisfies every equation, which is exactly why it doesn’t count: the promise says $s \ne 000$ . The other solution is $111$ .
D. $011$ is a result, not $s$ . Test it against both equations: $011\cdot011 = 1\oplus1 = 0$ is fine, but $110\cdot011 = 1$ , so it breaks the second.

How many runs does that take? Suppose you already have $k$ independent results, with $k < n - 1$ . The strings you can make by XOR-ing some of them, $2^k$ in all (counting $0\ldots0$ ), are exactly the ones that add nothing new. A fresh run gives one of the $2^{n-1}$ allowed strings at random, so it brings a new independent equation with probability

1 - \frac{2^k}{2^{n-1}} \ \ge\ \frac12.

So each missing equation takes at most two runs on average, and the average total is under $n + 1$ . Solving the equations is ordinary elimination, about $n^3$ bit operations. In all: about $n$ queries.

Check yourself

Simon’s circuit with $n = 4$ . So far you have 2 independent results. What is the probability that the next run gives a new independent equation?

Hints

How many strings can a run give at all, and how many of them add nothing new?
The useless ones are the XORs of your results, including $0000$ : $2^k$ of them.

Show the answer

Answer: $\frac{1}{2}$

A run gives one of the $2^{3} = 8$ strings with $y\cdot s = 0$ , all equally likely. The $2^{2} = 4$ XORs of your results (including $0000$ ) add nothing. So the chance is $1 - 4/8 = \frac{1}{2}$ .

Common slips

$\frac{3}{4}$ : That treats only your 2 results as useless. $0000$ and every XOR of your results add nothing either: $2^{2} = 4$ of the 8 allowed strings.
$\frac{5}{8}$ : That counts your 2 results and $0000$ as useless, but every XOR of your results adds nothing too: $2^{2} = 4$ useless strings in all.

8 / 15 · Worked example

Part B · Worked example: solving for s

Every string here has its first bit, $y_1$ or $s_1$ , on the left.

Worked example

Four bits

Simon’s circuit with $n = 4$ gives the results $1100$ , $0010$ , $1110$ and $0101$ , in that order. Find $s$ .

Equations
One equation per result: $1100$ gives $s_1\oplus s_2 = 0$ ; $0010$ gives $s_3 = 0$ ; $1110$ gives $s_1\oplus s_2\oplus s_3 = 0$ ; $0101$ gives $s_2\oplus s_4 = 0$ .
Drop what is not new
$1110 = 1100\oplus0010$ , and its equation is the sum of the first two: $(s_1\oplus s_2)\oplus s_3 = 0\oplus0$ . It adds nothing. That leaves three independent equations, which is $n - 1$ for $n = 4$ : enough.
Eliminate
$s_3 = 0$ directly. The other two tie the remaining bits together: $s_1 = s_2$ and $s_4 = s_2$ . So everything follows from $s_2$ : $s_2 = 0$ gives $0000$ , and $s_2 = 1$ gives $1101$ .
Answer and check
$s \ne 0000$ , so $s = 1101$ . Check every result: $1100\cdot1101 = 1\oplus1 = 0$ , $0010\cdot1101 = 0$ , $1110\cdot1101 = 1\oplus1 = 0$ , $0101\cdot1101 = 1\oplus1 = 0$ .
Your turn: enough?
New runs, again with $n = 4$ , give $1001$ , $0110$ and $1111$ .
Your turn
Do the results $1001$ , $0110$ and $1111$ pin $s$ down?
1. AYes: three results is $n - 1$ for $n = 4$
2. BNo: one of the three adds nothing new
3. CNo: four bits need four equations
4. DYes: none of them is $0000$ , so each one is new
Hint
1. Is any of the three the XOR of the other two?
Show the answer
Answer: B. No: one of the three adds nothing new
$1001\oplus0110 = 1111$ , so there are two independent equations, $s_1\oplus s_4 = 0$ and $s_2\oplus s_3 = 0$ . They leave four solutions: $0000$ and the candidates $0110$ , $1001$ and $1111$ . One more independent run is needed.
Why not the others
- A. Three results are enough only if they are independent. Here $1001\oplus0110 = 1111$ , so the third equation is the sum of the first two. Two equations leave $2^4/2^2 = 4$ solutions: $0000$ and three candidates.
- C. Three independent equations would be enough for four bits: they leave $0000$ and $s$ . The trouble here is that only two are independent, because $1001\oplus0110 = 1111$ .
- D. Being nonzero isn’t enough: a result can also be the XOR of earlier ones, and $1001\oplus0110 = 1111$ . Only two of these equations are independent.
Your turn: solve
One more run gives $0011$ .
Your turn
With $1001$ , $0110$ , $1111$ and now $0011$ , which string is $s$ ?
1. A $1111$
2. B $1001$
3. C $0011$
4. D $0110$
Hint
1. Write the new equation, then test the three candidates from the last step.
Show the answer
Answer: A. $1111$
The equations now say $s_1 = s_4$ , $s_2 = s_3$ and $s_3 = s_4$ : all four bits are equal. So $s = 1111$ , and indeed $1001$ , $0110$ , $1111$ and $0011$ each share an even number of 1s with it.
Why not the others
- B. $1001$ was a candidate, but $0011\cdot1001 = 1$ : it breaks the new equation $s_3\oplus s_4 = 0$ .
- C. $0011$ is the newest result. Use it as an equation, $s_3\oplus s_4 = 0$ , and test the three candidates left: only $1111$ passes.
- D. $0110$ was a candidate, but $0011\cdot0110 = 1$ : it breaks the new equation $s_3\oplus s_4 = 0$ .

One more, fully worked, with fewer bits and a few wasted runs.

Another worked example

Another example: three bits

Equations
With $n = 3$ the runs give $101$ , $000$ , $101$ and $011$ . The result $000$ gives $0 = 0$ , and the second $101$ repeats the first. The useful equations are $s_1\oplus s_3 = 0$ (from $101$ ) and $s_2\oplus s_3 = 0$ (from $011$ ).
Solve
So $s_1 = s_3$ and $s_2 = s_3$ : all three bits are equal. The solutions are $000$ and $111$ , and $s \ne 000$ , so $s = 111$ .
Check
$101\cdot111 = 1\oplus1 = 0$ and $011\cdot111 = 1\oplus1 = 0$ . Four runs, two of them useful: about what to expect, since each run is new with probability at least $\tfrac12$ .

9 / 15 · Explore

Part B · Play both sides

Here is the whole algorithm, next to the classical search from Part A. In the quantum tab, each run adds an equation and crosses out the candidates it breaks; the round ends when one candidate is left. Play a few rounds of each and compare the averages in the tally.

Check yourself

With $n = 3$ , what is the probability that a run gives $y = 000$ , an equation that says nothing?

Hint

How many results are possible for $n = 3$ , and are they equally likely?

Show the answer

Answer: $\frac{1}{4}$

A run gives one of the $2^{n-1} = 4$ strings with $y\cdot s = 0$ , each with probability $\tfrac14$ , and $000$ is always one of them. So a quarter of the runs are wasted this way.

Common slips

$\frac{1}{8}$ : That treats all eight strings as possible results. Only the four with $y\cdot s = 0$ ever appear, each with probability $\tfrac14$ .
$0$ : $000\cdot s = 0$ for every $s$ , so $000$ is always one of the allowed results. It just teaches you nothing.
$\frac{1}{7}$ : There are seven nonzero strings, but that is the count of candidates for $s$ , not of results. A run gives one of the four strings with $y\cdot s = 0$ , each with probability $\tfrac14$ .

10 / 15 · Learn

Part B · An exponential gap

Put the two costs side by side. The quantum algorithm uses about $n$ queries, plus about $n^3$ steps of classical algebra afterwards. Every classical algorithm, even a randomized one that may err with small probability, needs on the order of $2^{n/2}$ queries. For $n = 20$ that is about 21 runs against about $1{,}300$ queries; for $n = 40$ , about 41 against 1.3 million.

So Simon’s problem gives an exponential separation in the query model, and a stronger one than Deutsch–Jozsa’s. There, a few random classical queries were nearly always right, so the gap was exponential only against methods that must never err (Lesson 9). Here guessing doesn’t help.

Expected uses of the black box: random classical queries until a collision, and runs of Simon’s circuit until $n - 1$ independent equations. The vertical axis is logarithmic, each grid line ten times the one below. On it, the classical count is a straight line (it doubles every two bits), while the quantum count grows by about one per bit.

Check yourself

Which statement about Simon’s algorithm is accurate?

AIt needs only one query, like the circuit of Lesson 14
BLike Deutsch–Jozsa, its gain is exponential only against classical methods that must never err
CIt uses exponentially fewer queries than any classical algorithm, including randomized ones that may err with small probability
DIt proves that quantum computers are exponentially faster at practical problems

Hint

How does the classical cost behave when the classical method may guess?

Show the answer

Answer: C. It uses exponentially fewer queries than any classical algorithm, including randomized ones that may err with small probability

Quantum: about $n$ queries. Classical: order $2^{n/2}$ , even with randomness and a small error allowed. That is an exponential separation, in the query model.

Why not the others

A. One run gives one equation $y\cdot s = 0$ . You need $n - 1$ independent ones, so about $n$ runs: still exponentially fewer than $2^{n/2}$ .
B. That was Deutsch–Jozsa’s weakness: $k$ random queries erred with probability at most $2^{1-k}$ , whatever $n$ was. For Simon’s problem, random queries need about $2^{n/2}$ tries to find a collision, and no classical method of any kind does better than order $2^{n/2}$ .
D. It is a statement about calls to a black box. It shows what interference can do with a hidden XOR pattern, but on its own it says nothing about problems where you can read the circuit that computes $f$ . The step toward practical problems came with Shor’s algorithm.

11 / 15 · Learn

Part B · Simon’s algorithm in Qiskit

In Qiskit the circuit takes a few lines (Lesson 12 has the basics). It needs an oracle for a given $s$ , and there is a simple recipe. First copy $x$ into the outputs with $n$ CNOTs. Then pick a position $j$ where $s_j = 1$ and XOR the bit $x_j$ into every output where $s$ has a 1. The outputs now hold $f(x) = x\oplus x_j\,s$ : that is $x$ , with $s$ XOR-ed in when $x_j = 1$ . The partner $x\oplus s$ has the other value of bit $j$ , so

f(x\oplus s) = x\oplus s\oplus(x_j\oplus1)\,s = x\oplus x_j\,s,

the same value, as the promise requires. Python counts from 0, so s[0] is the first bit, $s_1$ , and it sits on qubit 0.

Interactive

A code editor for Python with Qiskit’s circuit methods, run in the page: edit the program below and run it to see the circuit it builds, the state it leaves and, when it measures, the counts from 1,000 shots.

from qiskit import QuantumCircuit

n = 3
s = '110'      # the hidden string: s[0] is the first bit, s_1, on qubit 0

qc = QuantumCircuit(2 * n, n)
qc.h(range(n))              # Hadamards on the inputs, qubits 0 to n - 1
qc.barrier()
# The oracle: copy x into the outputs, qubits n to 2n - 1 ...
for i in range(n):
    qc.cx(i, n + i)
# ... then XOR bit j of x into every output where s has a 1
j = s.index('1')
for i in range(n):
    if s[i] == '1':
        qc.cx(j, n + i)
qc.barrier()
qc.h(range(n))              # Hadamards on the inputs again
qc.measure(range(n), range(n))

Simon’s circuit for $n = 3$ and $s = 110$ . Run it a few times: only four of the eight strings ever appear. Qiskit prints classical bit 0, here $y_1$ , on the right.

Open it in the app

Reading the counts takes care. Qiskit writes classical bit 0 on the right, so the key '100' means $y_3y_2y_1 = 100$ , which is $y = 001$ in the lessons’ order. For $s = 110$ the four keys 000, 100, 011 and 111 are, reversed, $000$ , $001$ , $110$ and $111$ : exactly the strings with $y_1\oplus y_2 = 0$ . Reverse each key before you write its equation.

Check yourself

A colleague runs Simon’s algorithm in Qiskit for $n = 3$ , measuring qubits 0, 1 and 2 into classical bits 0, 1 and 2, and gets {'000': 251, '010': 244, '100': 262, '110': 243}. What is $s$ , written as $s_1s_2s_3$ ?

AYou can’t tell: the counts never show $s$
B $010$
C $001$
D $100$

Hints

Qiskit writes classical bit 0, here $y_1$ , on the right. Reverse each key first.
Then write $y\cdot s = 0$ for two nonzero results and solve.

Show the answer

Answer: D. $100$

Reversed into the lessons’ order, the results are $000$ , $010$ , $001$ , $011$ . Two nonzero ones, $010$ and $001$ , give $s_2 = 0$ and $s_3 = 0$ . The nonzero solution is $s = 100$ . Check: $010\cdot100 = 0$ , $001\cdot100 = 0$ , $011\cdot100 = 0$ .

Why not the others

A. They don’t have to. Three of the four results are nonzero, and any two of those are independent. Their equations $y\cdot s = 0$ leave exactly one nonzero solution.
B. 010 is one of the keys: a result $y$ , written in Qiskit’s order. A result only tells you that $y\cdot s = 0$ ; it isn’t $s$ . Reverse the keys, write one equation per result, and solve.
C. That comes from reading the keys as if classical bit 0, $y_1$ , were on the left. Qiskit puts bit 0 on the right, so the key 100 means $y = 001$ . Reverse every key first: the results are $000$ , $010$ , $001$ , $011$ , and they give $s = 100$ .

Check yourself

Complete the program so that it runs Simon’s algorithm for $n = 3$ with $s = 011$ : add CNOTs that put into the outputs a value $f(x)$ with $f(x) = f(x\oplus011)$ , two inputs per value. The recipe above works, and so does any other oracle with the promise: the check compares the measured distribution with the one Simon’s circuit must give.

from qiskit import QuantumCircuit

n = 3
s = '011'      # s[0] is the first bit, s_1, on qubit 0

qc = QuantumCircuit(2 * n, n)
qc.h(range(n))
# The oracle goes here: CNOTs from the inputs (qubits 0 to 2)
# into the outputs (qubits 3 to 5).

qc.h(range(n))
qc.measure(range(n), range(n))

Write the program in the app’s code editor (Python with Qiskit’s circuit methods), run it, and check it.

Hints

Start by copying each input into its output: qc.cx(i, n + i) for i in range(n).
Then pick a position j with s[j] == '1' and add qc.cx(j, n + i) for every i where s[i] == '1'.
With $s = 011$ , $j = 1$ works: after the three copies, add qc.cx(1, 4) and qc.cx(1, 5).

Show the answer

One program that works:

from qiskit import QuantumCircuit

n = 3
s = '011'      # s[0] is the first bit, s_1, on qubit 0

qc = QuantumCircuit(2 * n, n)
qc.h(range(n))
# The oracle: copy x into the outputs ...
for i in range(n):
    qc.cx(i, n + i)
# ... then XOR bit j of x into the outputs where s has a 1
j = s.index('1')
for i in range(n):
    if s[i] == '1':
        qc.cx(j, n + i)
qc.h(range(n))
qc.measure(range(n), range(n))

With the recipe the outputs hold $f(x) = x\oplus x_2\,011$ , and $f(x\oplus011) = f(x)$ . The measured inputs are then the strings with $y_2\oplus y_3 = 0$ : $000$ , $011$ , $100$ and $111$ , which Qiskit prints as 000, 110, 001 and 111.

12 / 15 · Practice

Practice

Three items, each with new numbers when it comes back. Hints are there if you need them.

Check yourself

Simon’s circuit with $n = 3$ and $s = 011$ . After the query the inputs are in $(\ket{000} + \ket{011})/\sqrt2$ . What is the amplitude of $\ket{100}$ after the last Hadamards?

Hints

Each branch $\ket x$ gives $\ket{100}$ the term $(-1)^{x\cdot y}/\sqrt{2^{4}}$ .
Compute $000\cdot100$ and $011\cdot100$ ; equal dot products add, different ones cancel.

Show the answer

Answer: $\frac{1}{2}$

$000\cdot100 = 0$ and $011\cdot100 = 0$ , so the two terms are $+1/\sqrt{2^{4}}$ and $+1/\sqrt{2^{4}}$ . They add, since $s\cdot y = 0$ : the amplitude is $\frac{1}{2}$ .

Common slips

$-\frac{1}{2}$ : Right size, wrong sign. Both branches give $\ket{100}$ the sign $+1$ , because $000\cdot100 = 0$ and $011\cdot100 = 0$ .
$\frac{1}{4}$ : That is the probability, the squared amplitude. The amplitude itself is $\frac{1}{2}$ .
$0$ : The two branches cancel only when $s\cdot y = 1$ . Here $011\cdot100 = 0$ , so they add.

Check yourself

Simon’s circuit with $n = 4$ gives the results $1101$ , $1001$ and $0111$ , which are independent. Which string is $s$ ?

A $0010$
B $1101$
C $1011$
D $0100$
E $0000$

Hints

Write one equation $y\cdot s = 0$ per result.
Test each option against every equation: it survives only if it shares an even number of 1s with every result.

Show the answer

Answer: C. $1011$

The equations are $s_1 \oplus s_2 \oplus s_4 = 0$ , $s_1 \oplus s_4 = 0$ , $s_2 \oplus s_3 \oplus s_4 = 0$ . Exactly two strings satisfy all of them, $0000$ and $1011$ , and $s \ne 0000$ , so $s = 1011$ .

One equation per result: $s_1 \oplus s_2 \oplus s_4 = 0$ , $s_1 \oplus s_4 = 0$ , $s_2 \oplus s_3 \oplus s_4 = 0$ . With $n - 1 = 3$ independent equations there are exactly two solutions. Check $1011$ against each result: $1101\cdot1011 = 0$ , $1001\cdot1011 = 0$ , $0111\cdot1011 = 0$ . The only other solution is $0000$ , which the promise rules out.

Why not the others

A. $0010$ passes the first equations but not the last: $0111\cdot0010 = 1$ .
B. $1101$ is a result, not $s$ . Use it as an equation, and test it against the others: $1101\cdot1101 = 1$ .
D. $0100 = 1101\oplus1001$ gives an equation you can derive from the first two, not a solution. Test it: $1101\cdot0100 = 1$ , $0111\cdot0100 = 1$ .
E. $0000$ satisfies every equation, which is exactly why it doesn’t count: the promise says $s \ne 0000$ . The other solution is $1011$ .

Check yourself

You have queried 25 different inputs and seen no collision yet. How many pairs of queried inputs is that? Each pair is one chance that two of them are partners.

Hints

Each new input can be compared with every input before it.
The 25th input adds 24 pairs; add them all up, or use $k(k-1)/2$ .

Show the answer

Answer: $300$

$k(k-1)/2 = 25\cdot24/2 = 300$ pairs: the second input makes 1 pair, the third 2 more, and the 25th 24 more.

Common slips

$625$ : That is $25^2$ , which counts every pair twice and also pairs each input with itself. The count is $25\cdot24/2 = 300$ .
$600$ : That counts each pair twice, once in each order. Divide by 2: $300$ .
$25$ : That is the number of queries. The tests are pairs: each new input is compared with every earlier one, $0 + 1 + \cdots + 24 = 300$ .

13 / 15 · Explain

Explain it

Explain why a run of Simon’s circuit never gives a string $y$ with $y\cdot s = 1$ , and why you still need about $n$ runs to find $s$ .

Show a model answer

After the query, the inputs are (for whichever value the outputs hold) in an equal superposition of a pair, $\ket{x}$ and $\ket{x\oplus s}$ . The last Hadamards give each $\ket{y}$ one contribution from each branch, with signs $(-1)^{x\cdot y}$ and $(-1)^{(x\oplus s)\cdot y} = (-1)^{x\cdot y}(-1)^{s\cdot y}$ . When $s\cdot y = 1$ these are opposite and cancel, so such a $y$ never appears; when $s\cdot y = 0$ they add. So a run gives a uniformly random $y$ with $y\cdot s = 0$ : one linear equation for the bits of $s$ , not $s$ itself. It takes $n - 1$ independent equations to leave only $0\ldots0$ and $s$ , and each run gives a new one with probability at least one half, so about $n$ runs.

A good answer covers

After the query the inputs hold a pair, $\ket{x} + \ket{x\oplus s}$ (for each value in the outputs)
The last Hadamards give $\ket{y}$ two contributions whose signs differ by $(-1)^{s\cdot y}$ , so they cancel when $s\cdot y = 1$
A run gives one random equation $y\cdot s = 0$ , not $s$
About $n$ runs: $n - 1$ independent equations are needed, and each run is new with probability at least one half

14 / 15 · Mastery check

Mastery check

Check yourself

Simon’s circuit for $n = 3$ hides a string, say $s = 101$ . The circuit is run once and its 3 input qubits are measured. What does that one result give you?

A $s$ with probability $\tfrac12$ , otherwise a random string
BA random string $y$ with $y\cdot s = 0$ : one equation that $s$ must satisfy
CThe value $f(x)$ at one random input $x$
DThe hidden string $s$ itself

Show the answer

Answer: B. A random string $y$ with $y\cdot s = 0$ : one equation that $s$ must satisfy

After the query and the last Hadamards, the inputs hold a string $y$ chosen uniformly from the $2^{n-1} = 4$ strings with $y\cdot s = 0$ . One such $y$ is one equation for the bits of $s$ ; about $n$ runs give enough equations to solve for $s$ .

Why not the others

A. No allowed result is more likely than another: each of the $4$ strings with $y\cdot s = 0$ has probability $1/4$ . Even when the result happens to equal $s$ , nothing in the run tells you so.
C. That is what you get by measuring right after the query, as in Lesson 9. Simon’s circuit adds Hadamards after the query, and the measured inputs then hold a string $y$ with $y\cdot s = 0$ , not an input of $f$ .
D. One run gives a random string $y$ with $y\cdot s = 0$ : $000$ , $010$ , $101$ or $111$ , each with probability $\tfrac14$ . The result can be $000$ , which says nothing at all. It takes several runs, and some algebra, to pin $s$ down.

Check yourself

You query $f$ for $n = 5$ and find $f(10011) = f(01101)$ . What is $s$ ?

A $11110$
BYou can’t tell yet: more queries are needed
C $00001$
D $10011$

Hints

When can two different inputs share a value?
Only when they differ by $s$ , so XOR them.

Show the answer

Answer: A. $11110$

Two different inputs with the same value must be partners, $x' = x\oplus s$ , so $s = x\oplus x' = 10011\oplus01101 = 11110$ .

Why not the others

B. One collision is enough. Two different inputs with the same value must be partners, $x' = x\oplus s$ , so $s = 10011\oplus01101$ .
C. That is the bitwise AND of the two inputs. Partners differ by $s$ , so $s$ is their XOR: $10011\oplus01101 = 11110$ .
D. That is one of the inputs. The promise says two different inputs share a value only when they differ by $s$ , so $s$ is the XOR of the two: $11110$ .

Check yourself

Simon’s circuit with $n = 2$ and $s = 01$ . After the query the inputs are in $(\ket{11} + \ket{10})/\sqrt2$ . What is the amplitude of $\ket{10}$ after the last Hadamards?

Hints

Each branch $\ket x$ gives $\ket{10}$ the term $(-1)^{x\cdot y}/\sqrt{2^{3}}$ .
Compute $11\cdot10$ and $10\cdot10$ ; equal dot products add, different ones cancel.

Show the answer

Answer: $-\frac{1}{\sqrt{2}}$

$11\cdot10 = 1$ and $10\cdot10 = 1$ , so the two terms are $-1/\sqrt{2^{3}}$ and $-1/\sqrt{2^{3}}$ . They add, since $s\cdot y = 0$ : the amplitude is $-\frac{1}{\sqrt{2}}$ .

Common slips

$\frac{1}{\sqrt{2}}$ : Right size, wrong sign. Both branches give $\ket{10}$ the sign $-1$ , because $11\cdot10 = 1$ and $10\cdot10 = 1$ .
$\frac{1}{2}$ : That is the probability, the squared amplitude. The amplitude itself is $-\frac{1}{\sqrt{2}}$ .
$-\frac{\sqrt{2}}{4}$ : That counts only the branch $\ket{11}$ . Its partner $\ket{10}$ adds an equal term, since $s\cdot y = 01\cdot10 = 0$ : together $-\frac{1}{\sqrt{2}}$ .
$0$ : The two branches cancel only when $s\cdot y = 1$ . Here $01\cdot10 = 0$ , so they add.

Check yourself

A classical program attacks Simon’s problem for $n = 24$ by querying random inputs until two of them give the same value. Roughly how many queries does that take?

AAbout 24, one per bit
BAbout $2^{12} = 4{,}096$
CAbout $2^{23} \approx 8.4\times10^{6}$
DAbout $2^{24} \approx 1.7\times10^{7}$

Show the answer

Answer: B. About $2^{12} = 4{,}096$

A good chance of a collision needs about as many pairs as there are candidates: $k^2/2 \approx 2^{24}$ , so $k$ is of order $2^{12}$ . On average random queries take about $1.25\cdot2^{12}$ , roughly $5{,}100$ .

Why not the others

A. A query returns a value $f(x)$ , not a bit of $s$ . 24 random queries make only 276 pairs, and each pair is a matching pair with chance $1/(2^{24} - 1)$ .
C. $2^{23} + 1$ queries make a collision certain, since there are only $2^{23}$ different values. Random queries collide much sooner, because $k$ queries make about $k^2/2$ pairs: about $2^{12}$ queries already make about $2^{23}$ pairs.
D. You never need every input: $2^{23} + 1$ queries already force a collision. Random queries usually find one after about $2^{12}$ , since the number of pairs grows like $k^2/2$ .

Check yourself

Simon’s circuit with $n = 4$ gives the results $1101$ , $0111$ and $0010$ , which are independent. Which string is $s$ ?

A $0101$
B $1010$
C $1011$
D $1101$
E $0000$

Hints

Write one equation $y\cdot s = 0$ per result.
Test each option against every equation: it survives only if it shares an even number of 1s with every result.

Show the answer

Answer: A. $0101$

The equations are $s_1 \oplus s_2 \oplus s_4 = 0$ , $s_2 \oplus s_3 \oplus s_4 = 0$ , $s_3 = 0$ . Exactly two strings satisfy all of them, $0000$ and $0101$ , and $s \ne 0000$ , so $s = 0101$ .

One equation per result: $s_1 \oplus s_2 \oplus s_4 = 0$ , $s_2 \oplus s_3 \oplus s_4 = 0$ , $s_3 = 0$ . With $n - 1 = 3$ independent equations there are exactly two solutions. Check $0101$ against each result: $1101\cdot0101 = 0$ , $0111\cdot0101 = 0$ , $0010\cdot0101 = 0$ . The only other solution is $0000$ , which the promise rules out.

Why not the others

B. $1010 = 1101\oplus0111$ gives an equation you can derive from the first two, not a solution. Test it: $1101\cdot1010 = 1$ , $0111\cdot1010 = 1$ , $0010\cdot1010 = 1$ .
C. $1011$ passes the first equations but not the last: $0010\cdot1011 = 1$ .
D. $1101$ is a result, not $s$ . Use it as an equation, and test it against the others: $1101\cdot1101 = 1$ .
E. $0000$ satisfies every equation, which is exactly why it doesn’t count: the promise says $s \ne 0000$ . The other solution is $0101$ .

Check yourself

A colleague runs Simon’s algorithm in Qiskit for $n = 3$ , measuring qubits 0, 1 and 2 into classical bits 0, 1 and 2, and gets {'000': 244, '001': 244, '110': 248, '111': 264}. What is $s$ , written as $s_1s_2s_3$ ?

AYou can’t tell: the counts never show $s$
B $011$
C $001$
D $110$

Hints

Qiskit writes classical bit 0, here $y_1$ , on the right. Reverse each key first.
Then write $y\cdot s = 0$ for two nonzero results and solve.

Show the answer

Answer: B. $011$

Reversed into the lessons’ order, the results are $000$ , $100$ , $011$ , $111$ . Two nonzero ones, $100$ and $011$ , give $s_1 = 0$ and $s_2 \oplus s_3 = 0$ . The nonzero solution is $s = 011$ . Check: $100\cdot011 = 0$ , $011\cdot011 = 0$ , $111\cdot011 = 0$ .

Why not the others

A. They don’t have to. Three of the four results are nonzero, and any two of those are independent. Their equations $y\cdot s = 0$ leave exactly one nonzero solution.
C. 001 is one of the keys: a result $y$ , written in Qiskit’s order. A result only tells you that $y\cdot s = 0$ ; it isn’t $s$ . Reverse the keys, write one equation per result, and solve.
D. That comes from reading the keys as if classical bit 0, $y_1$ , were on the left. Qiskit puts bit 0 on the right, so the key 001 means $y = 100$ . Reverse every key first: the results are $000$ , $100$ , $011$ , $111$ , and they give $s = 011$ .

Check yourself

Simon’s problem with $n = 24$ . On average, about how many uses of the black box does each approach need: runs of Simon’s circuit, and random classical queries until a collision?

AAbout $25$ runs, and about $5{,}100$ queries
B $1$ run, and about $24$ queries
CAbout $25$ runs, and $2^{23} + 1$ queries
DAbout $24$ of each

Hint

A run is new with probability at least one half; random queries need about as many pairs as candidates.

Show the answer

Answer: A. About $25$ runs, and about $5{,}100$ queries

Quantum: $n - 1 = 23$ independent equations, each run new with probability at least $\tfrac12$ , about $25$ runs on average. Classical: a collision takes about $1.25\cdot2^{12} \approx 5{,}100$ random queries.

Why not the others

B. That is the Bernstein–Vazirani pattern. Here one run gives one equation $y\cdot s = 0$ ; you need $n - 1 = 23$ independent ones, so about $25$ runs. A classical search needs a collision, which takes about $1.25\cdot2^{12}$ queries.
C. $2^{23} + 1$ queries make a collision certain, but random ones find one much sooner: $k$ queries make about $k^2/2$ pairs, so about $1.25\cdot2^{12} \approx 5{,}100$ on average.
D. A classical query gives one value $f(x)$ . Without a collision, each pair of queries rules out a single candidate, and there are $2^{24} - 1$ candidates. That takes about $2^{12}$ queries, not $24$ .

15 / 15 · Recap

Recap

From memory

Before reading the summary, write down what you remember. Pulling it back from memory is what makes it last.

State Simon’s problem, and say what a classical algorithm needs to solve it.
Show the key points
- $f$ maps $n$ bits to $n$ bits, and $f(x) = f(x')$ exactly when $x' = x$ or $x' = x\oplus s$ , with $s \ne 0\ldots0$
- A collision $f(x) = f(x')$ with $x \ne x'$ gives $s = x\oplus x'$
- Random queries need about $2^{n/2}$ tries, since $k$ queries make $k(k-1)/2$ pairs; no classical algorithm beats order $2^{n/2}$
Describe one run of Simon’s circuit and what it returns.
Show the key points
- $H^{\otimes n}$ on the inputs, $U_f$ , $H^{\otimes n}$ on the inputs, then measure the inputs
- After the query the inputs are in a pair, $(\ket{x} + \ket{x\oplus s})/\sqrt2$ ; measuring the outputs is optional
- $\ket{y}$ gets amplitude proportional to $(-1)^{x\cdot y}(1 + (-1)^{s\cdot y})$ : a uniformly random $y$ with $y\cdot s = 0$
How do you get from the results to $s$ , and how many queries does that take?
Show the key points
- Each $y$ gives an equation $y\cdot s = 0$ ; collect $n - 1$ independent ones and solve by elimination
- The solutions are $0\ldots0$ and $s$ ; take the nonzero one
- Each run is new with probability at least $\tfrac12$ , so about $n$ queries, against order $2^{n/2}$ classically

Key ideas

Simon’s promise: $f(x) = f(x')$ exactly when $x' \in \{x, x\oplus s\}$ . Any collision gives $s = x\oplus x'$ .
Classically, $k$ queries test $k(k-1)/2$ pairs, so a collision takes about $2^{n/2}$ queries, and no classical algorithm, even a randomized one, does better than order $2^{n/2}$ .
One run: $H^{\otimes n}$ , $U_f$ , $H^{\otimes n}$ . The pair $(\ket{x} + \ket{x\oplus s})/\sqrt2$ turns into a sum where $\ket{y}$ has amplitude proportional to $(-1)^{x\cdot y}(1 + (-1)^{s\cdot y})$ , so $y$ is uniform over the strings with $y\cdot s = 0$ .
One run gives one equation, never $s$ itself. $n - 1$ independent equations, solved by elimination over bits, leave $0\ldots0$ and $s$ ; about $n$ runs are enough.
About $n$ quantum queries against order $2^{n/2}$ classical ones: an exponential separation in the query model, and the idea behind Shor’s period finding.
In Qiskit, reverse each counts key (bit 0 is on the right) before you write its equation.

Go further

Free resources for when you want more than this lesson covers.

Fundamentals of quantum algorithms: Simon’s algorithmJohn Watrous, IBM Quantum · Course
A careful treatment with the classical lower bound proved, and the circuit built in Qiskit.
Quantum Computing: Lecture NotesRonald de Wolf · Lecture notes
Free lecture notes whose early chapters cover query algorithms, Simon’s algorithm among them, and then Shor’s period finding.
Simon’s problemWikipedia · Article
The problem, the circuit and the history, including the link to Shor’s algorithm.
Birthday problemWikipedia · Article
The counting behind the classical cost, with the square-root rule worked out in several ways.

Math refreshers

The toolkit topics this lesson leans on.

Bits, XOR and bit stringsx ⊕ y, x · z mod 2, sums over {0,1}ⁿ, signs that depend on f(x), and equations over bits