Amplitude amplification · Kets & Gates

1 / 13 · Learn

Before you start

Lesson 16 found a marked item among $N$ by turning a state step by step toward it. This lesson keeps the turning and drops the search. Take any quantum algorithm whose result is good with probability $p$ : the same kind of step raises that chance close to 1 in about $1/\sqrt p$ rounds, where rerunning the algorithm takes about $1/p$ tries.

Then: what to do when you don’t know $p$ , and what the speed-up does not give you.

By the end of this lesson you can:

write the iterate $Q = -AS_0A^{-1}S_{\text{good}}$ for any algorithm $A$ , and build it in code;
explain why $Q$ turns the state by $2\theta$ , where $\sin\theta = \sqrt p$ , and compute the success chance $\sin^2((2k+1)\theta)$ after $k$ rounds;
choose the number of rounds, and compare the cost with rerunning;
succeed without knowing $p$ , by choosing the number of rounds at random;
say what Grover search does not do: it is no faster database lookup, and its square-root gain cannot be beaten.

Check yourself

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

An algorithm $A$ gives a good answer with probability $p$ , and you can check any answer. Rerunning $A$ until it succeeds takes about $1/p$ runs, so if $p$ becomes 100 times smaller, rerunning costs 100 times more. This lesson’s method replaces rerunning. If $p$ becomes 100 times smaller, how does the cost of that method change?

AIt grows 100 times too: nothing beats rerunning
BIt grows about 10 times
CIt grows by a fixed amount: about 7 more rounds
DIt doesn’t change: one quantum run checks every answer at once

Show the answer

Answer: B. It grows about 10 times

Each round turns the state by $2\theta$ , where $\sin\theta = \sqrt p$ , and it has to turn through about $90^\circ$ . For small $p$ , $\theta \approx \sqrt p$ radians, so it takes about $\tfrac{\pi}{4}/\sqrt p$ rounds: 100 times smaller $p$ means 10 times more rounds.

Why not the others

A. Rerunning grows like $1/p$ , but it is not the only option. Amplitude amplification turns the state by a fixed angle per round, and the number of rounds grows like $1/\sqrt p$ : 100 times smaller $p$ costs only 10 times more.
C. That would be a logarithmic cost, like halving an interval 7 times. Amplitude amplification gains a square root, not more: 100 times smaller $p$ needs about 10 times as many rounds, and no method does better in general.
D. A run on a superposition still ends in one measurement with one random result. The good results have to be made likely first, and that takes rounds: about $\tfrac{\pi}{4}/\sqrt p$ of them.

Check yourself

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

A Grover search over $N = 64$ items is tuned for one marked item: it makes 6 iterations, which find that item with probability 99.7%. Unknown to you, 4 items are marked. With the same 6 iterations, what is the chance of finding a marked item?

AOver 99.7%: more marked items are easier to find
BAbout 99.7%: the number of marked items doesn’t matter
CAbout 6.3%, the chance of a random guess
DAbout 2.0%, worse than a random guess

Show the answer

Answer: D. About 2.0%, worse than a random guess

With one marked item $\sin\theta = \sqrt{1/64}$ , so $\theta \approx 7.18^\circ$ , and 6 iterations reach $13\theta \approx 93.3^\circ$ . With 4 marked items $\sin\theta$ doubles: $\theta \approx 14.48^\circ$ , and the same 6 iterations reach about $188.2^\circ$ , past $\ket{\text{good}}$ at $90^\circ$ and nearly round to the unmarked side. The chance is $\sin^2(188.2^\circ) \approx 0.02$ , while a random guess gets $4/64 \approx 0.063$ .

Why not the others

A. More marked items make each iteration turn the state further: $\sin\theta = \sqrt{4/64}$ is twice $\sqrt{1/64}$ . 6 iterations then carry the state past the marked items, so more turning is not better here.
B. The angle of each iteration depends on how many items are marked. With 4 of them $\theta$ is about twice as large, so 6 iterations turn the state about twice as far as planned.
C. The iterations are not wasted: they move the state, just too far. It ends close to the unmarked states, and the chance, 2.0%, is below even a random guess.

2 / 13 · Learn

From search to any algorithm

Grover search starts from $H^{\otimes n}\ket{0\ldots0}$ , which gives every item the same small amplitude. Many problems allow a better start: some circuit $A$ that is already right with probability $p$ .

So let $A$ be any circuit with no measurements in it, and call some outcomes good. You need a way to recognize them, nothing more. Measuring $A\ket{0\ldots0}$ gives a good outcome with probability $p$ , and rerunning $A$ until one appears takes $1/p$ runs on average. Amplitude amplification does better with one iterate:

Q = -A\,S_0\,A^{-1}\,S_{\text{good}}

$S_{\text{good}}$ flips the sign of every good basis state;
$A^{-1}$ undoes $A$ (possible because $A$ is unitary);
$S_0$ flips the sign of $\ket{0\ldots0}$ alone;
$A$ runs again.

Read the product right to left: $S_{\text{good}}$ acts first. The minus sign in front is a global phase.

First $A$ , then $k$ rounds of $Q$ , then a measurement in the 0/1 basis. Inside each round the four pieces act in time order, which is the reverse of their order in the product $Q = -AS_0A^{-1}S_{\text{good}}$ .

Check yourself

Which piece of $Q$ needs to know what a good outcome looks like?

ANone: $Q$ finds the good outcomes by trying them all
B $A$ and $A^{-1}$ : the algorithm has to aim at the good outcomes
C $S_{\text{good}}$
D $S_0$

Show the answer

Answer: C. $S_{\text{good}}$

Only $S_{\text{good}}$ depends on which outcomes are good. $S_0$ depends only on the number of qubits, and $A$ is the given algorithm. In search, $S_{\text{good}}$ is the oracle; in general, recognizing a good outcome is often far easier than producing one.

Why not the others

A. $Q$ never reads out every outcome. Its only contact with the problem is $S_{\text{good}}$ , which flips the sign of the good states. Without it, $Q$ would have nothing to steer toward.
B. $A$ is the algorithm you already had. It doesn’t need to know which of its outcomes are good, only to produce them with some probability $p$ . Recognizing them is the job of $S_{\text{good}}$ .
D. $S_0$ only singles out the all-zeros state $\ket{0\ldots0}$ , the input of $A$ . It is the same circuit for every problem on the same number of qubits.

Grover search is the special case $A = H^{\otimes n}$ , with “good” meaning marked. Then $p = M/N$ for $M$ marked items among $N = 2^n$ , $S_{\text{good}}$ is the oracle, and $-H^{\otimes n}S_0H^{\otimes n} = 2\ket s\bra s - I$ is the diffusion step, the reflection about the uniform superposition $\ket s$ .

For any $A$ , the same holds with $\ket\psi = A\ket{0\ldots0}$ in place of $\ket s$ : $-AS_0A^{-1} = 2\ket\psi\bra\psi - I$ .

A map that keeps one direction and flips the sign of every direction at right angles to it is a reflection, like a mirror whose line is that direction. The formula says that half of $Q$ is a reflection in the line of $\ket\psi$ . Check the claim on $\ket\psi$ itself, one piece at a time, and watch the signs.

Check yourself

Let $\ket\psi = A\ket{0\ldots0}$ . Follow $\ket\psi$ through $-AS_0A^{-1}$ , one piece at a time. What comes out?

A $\ket{0\ldots0}$
BA state closer to the good outcomes
C $-\ket\psi$
D $\ket\psi$ , unchanged

Hints

Start with $A^{-1}\ket\psi$ : what is it?
Then $S_0$ flips the sign of $\ket{0\ldots0}$ , $A$ runs, and the leading minus sign acts last.

Show the answer

Answer: D. $\ket\psi$ , unchanged

$A^{-1}\ket\psi = \ket{0\ldots0}$ , then $S_0$ flips it to $-\ket{0\ldots0}$ , $A$ gives $-\ket\psi$ , and the minus sign in front restores $+\ket\psi$ . A state orthogonal to $\ket\psi$ instead ends with a minus sign, so $-AS_0A^{-1}$ is a mirror whose line is $\ket\psi$ .

Why not the others

A. $A^{-1}$ alone would do that, but $A$ runs again at the end and brings it back: the net effect on $\ket\psi$ is no change at all.
B. This half of $Q$ only reflects: it keeps the line of $\ket\psi$ and flips the sign of everything orthogonal to it. The turn toward the good states comes from combining both halves, as the next segments show.
C. Through the pieces: $A^{-1}\ket\psi = \ket{0\ldots0}$ , $S_0$ gives $-\ket{0\ldots0}$ , $A$ gives $-\ket\psi$ . You still need the minus sign in front of $-AS_0A^{-1}$ , which makes it $+\ket\psi$ .

3 / 13 · Explore

One round on one qubit

The smallest example has one qubit. $R_y(\phi)$ , Qiskit’s ry, turns $\ket0$ into $\cos\tfrac\phi2\ket0 + \sin\tfrac\phi2\ket1$ , and its inverse is $R_y(-\phi)$ . Take $A = R_y(\pi/3)$ :

A\ket0 = \tfrac{\sqrt3}{2}\ket0 + \tfrac12\ket1.

Call $\ket1$ good, so $p = \tfrac14$ . Then $S_{\text{good}} = Z$ , which flips the sign of $\ket1$ , and $S_0 = XZX$ , which flips the sign of $\ket0$ .

Predict, then see

$A = R_y(\pi/3)$ succeeds with $p = \tfrac14$ . After $A$ and one round of $Q$ , what is the chance of measuring $\ket1$ ?

A $\tfrac34$ : the chance triples
B1: the result is $\ket1$ every time
C $\tfrac14$ : every piece only flips signs or undoes $A$ , so the chance can’t change
D $\tfrac12$ : each round adds another $p$

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
from math import pi

qc = QuantumCircuit(1)
qc.ry(pi / 3, 0)     # A

# one round of Q = -A S0 A^-1 S_good (the minus sign is a global phase)
qc.z(0)              # S_good: flip the sign of |1>
qc.ry(-pi / 3, 0)    # A^-1
qc.x(0)              # S0 = X Z X: flip the sign of |0>
qc.z(0)
qc.x(0)
qc.ry(pi / 3, 0)     # A

The program applies $A$ and one round of $Q$ , and shows the final state. Read off the chance of $\ket1$ . Then put a # in front of each of the six lines of the round and press Run again to see $A\ket0$ alone.

Open it in the app

Where did the extra probability come from? In a sentence or two: how can steps that only flip signs or undo $A$ change a probability?

Show what happens

What happens: B. 1: the result is $\ket1$ every time

Write $A\ket0 = \cos\theta\ket0 + \sin\theta\ket1$ with $\theta = 30^\circ$ , since $\sin\theta = \tfrac12 = \sqrt p$ . Step by step: $Z$ gives $(\tfrac{\sqrt3}{2}, -\tfrac12)$ , at $-30^\circ$ ; $A^{-1}$ turns that back by $30^\circ$ to $(\tfrac12, -\tfrac{\sqrt3}{2})$ ; $XZX$ flips the first entry, $(-\tfrac12, -\tfrac{\sqrt3}{2})$ ; $A$ turns forward by $30^\circ$ to $(0, -1)$ . That is $-\ket1$ , and with the minus sign in front of $Q$ , exactly $\ket1$ . The good amplitude went from $\sin 30^\circ$ to $\sin 90^\circ$ : one round turned the state by $60^\circ = 2\theta$ .

Why not the others

A. The program gives 1. For small $p$ the good amplitude roughly triples in the first round, so the chance grows about ninefold, not threefold. Here $p$ is not small, and the exact rule is a turn from $30^\circ$ to $90^\circ$ .
C. Each sign flip alone leaves the chances alone, but $A^{-1}$ and $A$ sit between the flips and mix the amplitudes. A sign flipped before the mixing changes what comes out after it: the program shows $P(1)$ going from 25% to 100%.
D. Adding about $p$ per try is how rerunning behaves. $Q$ acts on amplitudes instead: it turns the state by a fixed angle, and here one turn lands exactly on $\ket1$ .

4 / 13 · Learn

Two reflections make a rotation

The example is no accident. Split $\ket\psi = A\ket{0\ldots0}$ into its good and bad parts:

\ket\psi = \sin\theta\,\ket{\text{good}} + \cos\theta\,\ket{\text{bad}},

where $\sin\theta = \sqrt p$ , $\ket{\text{good}}$ is the normalized good part and $\ket{\text{bad}}$ the normalized rest. Both halves of $Q$ are mirrors in the plane of these two states:

$S_{\text{good}}$ flips the $\ket{\text{good}}$ part: a mirror along $\ket{\text{bad}}$ ;
$-AS_0A^{-1}$ keeps $\ket\psi$ and flips what is orthogonal to it: a mirror along $\ket\psi$ .

Two mirrors whose lines meet at angle $\theta$ make a rotation by $2\theta$ . So each round turns the state $2\theta$ further toward $\ket{\text{good}}$ , and after $k$ rounds

\begin{aligned}Q^k\ket\psi = {}&\sin((2k+1)\theta)\ket{\text{good}} \\ &+ \cos((2k+1)\theta)\ket{\text{bad}}.\end{aligned}

The chance of a good outcome is ${\sin^2((2k+1)\theta)}$ .

Step 1 · mirror in the bad axis

Step 2 · mirror in the start line

The example from above, $p = \tfrac14$ , so $\theta = 30^\circ$ . Step 1 mirrors $\ket\psi$ in the $\ket{\text{bad}}$ axis, to $-30^\circ$ . Step 2 mirrors that in the line of $\ket\psi$ , to $90^\circ$ , which is $\ket{\text{good}}$ . The net effect is a turn by $2\theta = 60^\circ$ .

Check yourself

An algorithm already succeeds with $p = \tfrac34$ . You apply one round of $Q$ anyway. What is the chance of a good outcome now?

Hints

Find $\theta$ from $\sin\theta = \sqrt p$ .
$\sqrt{3/4} = \sqrt3/2 = \sin 60^\circ$ . After one round the angle is $3\theta$ .

Show the answer

Answer: $0$

$\sin\theta = \sqrt3/2$ , so $\theta = 60^\circ$ . One round turns the state to $3\theta = 180^\circ$ , which is $-\ket{\text{bad}}$ , and $\sin^2 180^\circ = 0$ . Above $p = \tfrac12$ one round already makes things worse; there you would just run $A$ and check.

Common slips

$1$ : One round lands on $\ket{\text{good}}$ only when $3\theta = 90^\circ$ , that is for $p = \tfrac14$ . Here $\sin\theta = \sqrt3/2$ , so $\theta = 60^\circ$ and $3\theta = 180^\circ$ : the state has turned past $\ket{\text{good}}$ all the way to $-\ket{\text{bad}}$ .
$\frac{3}{4}$ : The round does change the state: it turns it by $2\theta = 120^\circ$ , from $60^\circ$ to $180^\circ$ , and $\sin^2 180^\circ = 0$ .
$\frac{1}{4}$ : That is $1 - p$ , the bad part before the round. After the round the angle is $3\theta = 180^\circ$ , and the good chance is $\sin^2 180^\circ = 0$ .

5 / 13 · Worked example

Worked example: how many rounds?

The best number of rounds makes $(2k+1)\theta$ as close to $90^\circ$ as possible: $k$ is the whole number nearest to $\dfrac{90^\circ}{2\theta} - \dfrac12$ . Keep a calculator at hand for $\theta = \arcsin\sqrt p$ .

Worked example

An algorithm that succeeds once in a hundred runs

First $p = \tfrac{1}{100}$ , worked for you; then $p = \tfrac{1}{25}$ , which you finish.

Angle
$\sin\theta = \sqrt{1/100} = \tfrac{1}{10}$ , so $\theta = \arcsin 0.1 \approx 5.74^\circ$ .
Rounds
$\dfrac{90^\circ}{2\theta} - \dfrac12 \approx 7.84 - 0.5 = 7.34$ , so $k = 7$ . The state ends at $15\theta \approx 86.1^\circ$ .
Chance
$\sin^2 86.1^\circ \approx 0.995$ . With $k = 8$ the state would pass $90^\circ$ , to $17\theta \approx 97.6^\circ$ , and the chance would drop to $0.983$ .
Cost
In all, $A$ and $A^{-1}$ run $2k + 1 = 15$ times, and $S_{\text{good}}$ runs 7 times. Rerunning $A$ needs 100 runs on average, and 15 reruns succeed with chance only $1 - 0.99^{15} \approx 0.14$ .
Your turn: rounds
Now $p = \tfrac{1}{25}$ : $\sin\theta = \tfrac15$ , so $\theta \approx 11.54^\circ$ .
Your turn
With $\theta \approx 11.54^\circ$ , how many rounds of $Q$ make a good outcome most likely?
Hints
1. Which $k$ puts $(2k+1)\theta$ closest to $90^\circ$ ?
2. $\dfrac{90^\circ}{2\theta} - \dfrac12 = \dfrac{90}{23.07} - 0.5$ .
Show the answer
Answer: $3$
$\dfrac{90^\circ}{2\theta} - \dfrac12 \approx 3.90 - 0.5 = 3.40$ , so $k = 3$ : the state ends at $7\theta \approx 80.8^\circ$ .
Common slips
- $4$ : Four rounds take the state to $9\theta \approx 103.8^\circ$ , past $90^\circ$ , where the chance is $0.943$ . Remember the $-\tfrac12$ : the state already starts at $\theta$ , so three rounds reach $7\theta \approx 80.8^\circ$ .
- $25$ : 25 is $1/p$ , the average number of reruns of $A$ . Rounds of $Q$ grow like $1/\sqrt p$ : the state needs to turn only about $90^\circ$ , in steps of $2\theta \approx 23^\circ$ .
- $2$ : Two rounds reach $5\theta \approx 57.7^\circ$ , with chance $0.714$ . One more round gets much closer to $90^\circ$ .
Your turn: chance
Your turn
With $k = 3$ rounds and $\theta \approx 11.54^\circ$ , what is the chance of a good outcome? (Two or three decimal places.)
Hints
1. The angle after $k$ rounds is $(2k+1)\theta$ .
2. $7 \times 11.54^\circ \approx 80.76^\circ$ ; square its sine.
Show the answer
Answer: $0.974$
$7\theta \approx 80.76^\circ$ , and $\sin^2 80.76^\circ \approx 0.974$ . Rerunning $A$ the same $2k+1 = 7$ times would succeed with chance $1 - 0.96^7 \approx 0.25$ .
Common slips
- $\frac{1}{25}$ : That is $p$ , the chance before any round. After three rounds the angle is $7\theta \approx 80.8^\circ$ .
- $0.714$ : That is the chance after two rounds, at $5\theta$ . Three rounds reach $7\theta$ .
- $0.943$ : That is the chance after four rounds, at $9\theta \approx 103.8^\circ$ . Three rounds reach $7\theta \approx 80.8^\circ$ .

One more, fully worked, with $p = \tfrac19$ .

Another worked example

Another example: p = 1/9

Angle
$\sin\theta = \sqrt{1/9} = \tfrac13$ , so $\theta \approx 19.47^\circ$ .
Rounds
$\dfrac{90^\circ}{2\theta} - \dfrac12 \approx 2.31 - 0.5 = 1.81$ , so $k = 2$ . The state ends at $5\theta \approx 97.4^\circ$ : a little past $90^\circ$ , but closer than $3\theta \approx 58.4^\circ$ .
Chance
$\sin^2 97.4^\circ \approx 0.984$ , against $\sin^2 58.4^\circ \approx 0.726$ for $k = 1$ . Rerunning $A$ five times would succeed with chance $1 - (\tfrac89)^5 \approx 0.45$ .

6 / 13 · Practice

Build Q in code

In code, $A^{-1}$ of a rotation is the same rotation with the opposite angle, and the minus sign in front of $Q$ needs no gate. So one round of $Q$ is the six gate calls from the prediction program. To apply several rounds, write the round once as a function and call it in a loop.

The same recipe works on any number of qubits. For a circuit a, Qiskit’s a.inverse() builds $A^{-1}$ : the gates in reverse order, each one inverted. $S_0$ is an $X$ on every qubit, a $Z$ controlled by all the others, and the $X$ gates again. The example under the exercise does this on three qubits.

Check yourself

Now take $A = R_y(\pi/9)$ , so $A\ket0 = \cos\theta\ket0 + \sin\theta\ket1$ with $\theta = 10^\circ$ , and $p = \sin^2\theta \approx 0.03$ . Call $\ket1$ good. Then 4 rounds of $Q$ reach $(2\cdot 4 + 1)\theta = 90^\circ$ . Complete the program: write one round of $Q$ in q_round, then apply it 4 times, so that the qubit ends in $\ket1$ (up to a global phase).

from qiskit import QuantumCircuit
from math import pi

qc = QuantumCircuit(1)
qc.ry(pi / 9, 0)     # A

def q_round(qc):
    # one round of Q: S_good, then A^-1, then S0, then A
    pass

# apply q_round 4 times here

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

Hints

Copy the six gate calls of one round from the prediction program, with the angle changed to pi / 9.
Put them inside q_round (indented by four spaces, replacing pass), then call q_round(qc) 4 times, for example in for i in range(4):.

Show the answer

One program that works:

from qiskit import QuantumCircuit
from math import pi

qc = QuantumCircuit(1)
qc.ry(pi / 9, 0)     # A

def q_round(qc):
    qc.z(0)              # S_good: flip the sign of |1>
    qc.ry(-pi / 9, 0)    # A^-1
    qc.x(0)              # S0 = X Z X: flip the sign of |0>
    qc.z(0)
    qc.x(0)
    qc.ry(pi / 9, 0)     # A

for i in range(4):
    q_round(qc)

Each round turns the state by $2\theta$ , so after 4 rounds it sits at $(2\cdot 4+1)\theta = 90^\circ$ from $\ket0$ : the state is $\pm\ket1$ , and the sign is a global phase. (On one qubit, plain $Z$ in place of $XZX$ also passes, since $XZX = -Z$ differs only by a global sign. With more qubits, $S_0$ and $S_{\text{good}}$ are different mirrors.)

One round is $S_{\text{good}} = Z$ , then $A^{-1} = R_y(-\pi/9)$ , then $S_0 = XZX$ , then $A = R_y(\pi/9)$ ; the minus sign in front of $Q$ is a global phase and needs no gate. Apply that round 4 times after the first $A$ . The angle goes $\theta \to 3\theta \to \cdots \to (2\cdot4+1)\theta = 90^\circ$ , so the final state is $\pm\ket1$ .

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

# A: a random two-bit guess on q0, q1, and a flag q2 = q0 AND q1
a = QuantumCircuit(3)
a.h([0, 1])
a.ccx(0, 1, 2)

qc = QuantumCircuit(3)
qc.compose(a, inplace=True)            # A|000>: the flag is 1 with p = 1/4

# one round of Q = -A S0 A^-1 S_good
qc.z(2)                                # S_good: good means flag = 1
qc.compose(a.inverse(), inplace=True)  # A^-1
qc.x([0, 1, 2])                        # S0: flip the sign of |000> ...
qc.ccz(0, 1, 2)
qc.x([0, 1, 2])                        # ... with X, CCZ, X
qc.compose(a, inplace=True)            # A

A three-qubit $A$ : a random two-bit guess on $q_0, q_1$ , and a flag $q_2 = q_0 \text{ AND } q_1$ written by a Toffoli. Good means flag 1, so $S_{\text{good}}$ is a single $Z$ on the flag, and $p = \tfrac14$ . $S_0$ acts on all three qubits, and a.inverse() builds $A^{-1}$ . One round leaves $\ket{111}$ with certainty; put # in front of the round to see $A\ket{000}$ alone.

Open it in the app

7 / 13 · Learn

What it costs

For small $p$ , $\theta \approx \sqrt p$ in radians, and the best number of rounds is close to

k \approx \frac{\pi}{4\theta} \approx \frac{\pi}{4}\cdot\frac{1}{\sqrt p}.

Each round runs $A$ once, $A^{-1}$ once and $S_{\text{good}}$ once. Rerunning $A$ needs $1/p$ runs on average. For $p = 10^{-6}$ that is about 785 rounds against a million runs: a square-root saving, the same one Grover search gets. With $A = H^{\otimes n}$ and $p = M/N$ it reads $k \approx \tfrac{\pi}{4}\sqrt{N/M}$ .

The chance is not monotonic in $k$ . Past the best $k$ the state turns beyond $\ket{\text{good}}$ , and the chance falls again.

For $p = \tfrac{1}{100}$ : the bars show $\sin^2((2k+1)\theta)$ after $k$ rounds, best at $k = 7$ with 99.5%. The dots show rerunning $A$ as often as $k$ rounds use $A$ and $A^{-1}$ , that is $2k+1$ times: 15 runs give only 14%. Past $k = 7$ the bars shrink, because the state has turned past $\ket{\text{good}}$ .

Check yourself

An algorithm succeeds with probability $p = 10^{-4}$ . About how many rounds of $Q$ make a good outcome nearly certain?

Hints

For small $p$ , $\theta \approx \sqrt p$ in radians.
Rounds $\approx \dfrac{\pi}{4\theta} \approx \dfrac{\pi}{4}\cdot\dfrac{1}{\sqrt p}$ .

Show the answer

Answer: $78$

$\sqrt p = 10^{-2}$ , so $\theta \approx 10^{-2}$ radians and about $\tfrac{\pi}{4}\cdot 100 \approx 78.5$ rounds; the exact rule gives $k = 78$ , with success over 99.9%. Rerunning would need about 10,000 runs on average.

Common slips

$10000$ : 10,000 is $1/p$ , the average number of reruns of $A$ . Rounds of $Q$ grow like $1/\sqrt p$ instead.
$100$ : $1/\sqrt p = 100$ is the right scale, but the state only has to turn about $90^\circ$ in steps of $2\theta \approx 2\sqrt p$ : that is about $\tfrac{\pi}{4}\cdot 100 \approx 78.5$ rounds.
$157$ : 157 counts every use of $A$ and $A^{-1}$ , $2k+1$ in all. The question asks for rounds of $Q$ , each of which uses both.

8 / 13 · Learn

When you don’t know p

Everything so far needed $p$ to choose $k$ . Often you don’t know it: you don’t know how many items are marked, or how often your algorithm succeeds. A wrong guess is costly, because the chance oscillates: too many rounds can be worse than none. The search in the second prequestion shows how badly it can go.

The fix, from Boyer, Brassard, Høyer and Tapp (1998), is to choose $k$ at random. Fix a bound $m$ and pick $k$ uniformly from $0, 1, \ldots, m-1$ . Averaged over $k$ , the chance of success is

\frac1m\sum_{k=0}^{m-1}\sin^2((2k+1)\theta) = \frac12 - \frac{\sin(4m\theta)}{4m\sin 2\theta}.

Why about $\tfrac12$ : the angles $(2k+1)\theta$ spread around the circle, and $\sin^2$ averages $\tfrac12$ over a full turn. The second term shrinks as $m$ grows. Since $\abs{\sin(4m\theta)} \le 1$ , as soon as $m \ge 1/\sin 2\theta$ that term is at most $\tfrac14$ , so the average is at least $\tfrac14$ .

For $p = \tfrac{1}{100}$ , the average success when $k$ is picked at random below $m$ . Once $m$ passes $1/\sin 2\theta \approx 5$ , the average is at least $\tfrac14$ , and it settles near $\tfrac12$ . The dashed curve, $\tfrac12 - 1/(4m\sin 2\theta)$ , is the floor the formula guarantees.

Check yourself

Take $p = \tfrac14$ , so $\theta = 30^\circ$ . You pick $k$ at random from $0, 1, 2, 3$ (so $m = 4$ ), run $A$ and $k$ rounds of $Q$ , and measure. What is the chance of a good outcome?

Hints

List the angles $(2k+1)\theta$ for $k = 0, 1, 2, 3$ .
$30^\circ, 90^\circ, 150^\circ, 210^\circ$ : square each sine, then average.

Show the answer

Answer: $\frac{7}{16}$

The angles are $30^\circ, 90^\circ, 150^\circ, 210^\circ$ , with chances $\tfrac14, 1, \tfrac14, \tfrac14$ . Their average is $\tfrac{7/4}{4} = \tfrac{7}{16} \approx 0.44$ . The formula agrees: $\tfrac12 - \tfrac{\sin 480^\circ}{16\sin 60^\circ} = \tfrac12 - \tfrac{1}{16}$ .

Common slips

$1$ : One round, $k = 1$ , gives certainty, but you pick $k$ at random: three of the four choices end at $30^\circ$ , $150^\circ$ or $210^\circ$ , each with chance $\tfrac14$ .
$\frac{1}{4}$ : Three of the four choices give $\tfrac14$ , but $k = 1$ gives 1. The chance is the average, $\tfrac14(\tfrac14 + 1 + \tfrac14 + \tfrac14)$ .
$\frac{1}{2}$ : $\tfrac12$ is where the average settles for large $m$ . For $m = 4$ , average the four chances: $\tfrac14(\tfrac14 + 1 + \tfrac14 + \tfrac14)$ .

The full method grows $m$ as it goes, so it never needs $\theta$ :

Start with $m = 1$ .
Pick $k$ at random from $0, \ldots, m-1$ . Run $A$ , apply $Q$ $k$ times, measure, and check the result.
If it is good, stop. If not, multiply $m$ by a fixed factor (the paper uses $\tfrac65$ ) and go back to step 2.

While $m$ is small the tries are cheap. Once $m$ passes $1/\sin 2\theta$ , each try succeeds with chance at least $\tfrac14$ . Added up, the expected number of rounds is of order $1/\sqrt p$ , which for search is order $\sqrt{N/M}$ : the same scaling as knowing $p$ , with a larger constant. If nothing is marked, nothing can succeed, so you stop once the total passes a fixed multiple of $\sqrt N$ and report “none”. Had there been a marked item, it would very likely have turned up by then.

Check yourself

Why does the method start with $m = 1$ and grow it by $\tfrac65$ after each failure, instead of choosing a huge $m$ from the start?

AA huge $m$ makes the average success drop toward 0
BA huge $m$ makes $k$ huge too, which wastes rounds whenever $p$ turns out to be large
CBecause $k$ has to hit the best number of rounds exactly
D $m$ must stay below $1/\sin 2\theta$

Show the answer

Answer: B. A huge $m$ makes $k$ huge too, which wastes rounds whenever $p$ turns out to be large

Each try costs about $k$ rounds, and $k$ is typically about $m/2$ . Growing $m$ by a constant factor from 1 means $m$ reaches $1/\sin 2\theta$ having spent only a constant multiple of that many rounds, whatever $\theta$ is. A huge starting $m$ would spend order $m$ rounds per try even when $p$ is large and a round or two would do.

Why not the others

A. For large $m$ the average settles near $\tfrac12$ , not 0: the second term of the formula shrinks like $1/m$ . The trouble is cost: a random $k$ below a huge $m$ is usually huge, and each round costs a run of $A$ and $A^{-1}$ .
C. No exact $k$ is needed. Once $m$ is large enough, a random $k$ below it succeeds with chance about $\tfrac12$ on average.
D. It is the other way round: the guarantee of at least $\tfrac14$ starts once $m$ passes $1/\sin 2\theta$ . Growing $m$ step by step reaches that point without overshooting it by more than a constant factor.

9 / 13 · Learn

The fine print

Grover search is often described as searching a database in $\sqrt N$ steps. Three details limit what that means.

The data has to get in. The oracle must answer “is item $x$ marked?” for a superposition of positions $x$ , so the whole list must sit in a memory that a circuit can query in superposition. Writing $N$ items into it takes order $N$ steps, as many as a classical computer needs to scan the list once.
The oracle is a circuit. Every query runs a circuit that computes the check, and it costs gates, often many.
The gain is quadratic. $\sqrt N$ against $N$ is a large saving for large $N$ , but nothing like the exponential gap of Simon’s algorithm in Lesson 15, and the slower, error-corrected gates of a real machine eat into it.

The speed-up pays off when there is no list to load: the items are all $n$ ⁠-bit strings, and being good is a property a circuit can check. Lesson 18 builds such an oracle.

Check yourself

A company keeps a billion ( $10^{9}$ ) customer records, unsorted, on ordinary disks. It wants to find the one record with a given ID, once. Which statement is accurate?

AA quantum computer finds it in about 30 queries, one per bit of the record’s position
BA quantum search would not help: putting the records into a quantum memory takes about $10^{9}$ steps, as long as one classical scan
CGrover search finds it with about $\tfrac{\pi}{4}\sqrt{10^{9}} \approx 25{,}000$ queries, so it is far faster than a scan
DGrover search needs the records sorted by ID first; after that it is fast

Show the answer

Answer: B. A quantum search would not help: putting the records into a quantum memory takes about $10^{9}$ steps, as long as one classical scan

The count $\sqrt N$ assumes an oracle that answers for a superposition of positions. For stored data that means a quantum memory holding all $10^{9}$ records, and filling it costs order $N$ steps. For a one-off lookup a classical scan costs no more than that.

Why not the others

A. That would be an exponential speed-up, and unstructured search has none: every quantum method needs on the order of $\sqrt N$ queries. And the cost of loading the data comes on top.
C. The query count is right, but each query needs the records in a memory that a circuit can address in superposition. Writing $10^{9}$ records into it takes about $10^{9}$ steps, the cost of the scan you hoped to avoid.
D. Grover search needs no order at all; that is its point. And once the records are sorted, a classical binary search takes about $\log_2 N$ steps. The obstacle is getting the data into a quantum memory, which costs order $N$ .

Could a cleverer quantum algorithm beat $\sqrt N$ ? No. Bennett, Bernstein, Brassard and Vazirani proved in 1997 that any quantum algorithm needs on the order of $\sqrt N$ queries to find a marked item among $N$ when nothing else is known about where it is; their paper is listed under Go further. So Grover search, and amplitude amplification with its $1/\sqrt p$ , are optimal up to a constant factor: a square root is all that interference can buy for unstructured search.

Check yourself

Someone claims a quantum algorithm that finds the one marked item among $N = 2^{50}$ items, with nothing known about where it is, using 1,000 queries. What should you think?

APlausible, if it picks the number of rounds at random
BPlausible, if it applies $Q$ about 1,000 times
CIt can’t be right as stated: every quantum method needs on the order of $\sqrt N = 2^{25}$ , about 34 million, queries
DPlausible: quantum algorithms are exponentially faster than classical ones

Show the answer

Answer: C. It can’t be right as stated: every quantum method needs on the order of $\sqrt N = 2^{25}$ , about 34 million, queries

For unstructured search every quantum algorithm needs order $\sqrt N$ queries, and $\sqrt{2^{50}} = 2^{25}$ . Grover’s $\tfrac{\pi}{4}\sqrt N \approx 26{,}000{,}000$ is within a constant factor of that limit. A method using 1,000 queries must be exploiting structure that the problem, as stated, doesn’t have.

Why not the others

A. Picking $k$ at random handles an unknown number of marked items. It costs a constant factor more than knowing that number, never less.
B. Every round of $Q$ is a query: it uses $S_{\text{good}}$ once. With one marked item among $2^{50}$ , about $\tfrac{\pi}{4}\cdot 2^{25} \approx 26{,}000{,}000$ rounds are needed.
D. Some problems have exponential quantum speed-ups, but unstructured search is proven not to: any quantum algorithm needs order $\sqrt N$ queries, here about $2^{25}$ .

10 / 13 · Practice

Practice

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

Check yourself

An algorithm succeeds with probability $p = \tfrac{1}{25}$ . What is the chance of a good outcome after $A$ and 2 rounds of $Q$ ? (Two or three decimal places.)

Hints

Find $\theta$ from $\sin\theta = \sqrt p$ .
After $k$ rounds the angle is $(2k+1)\theta$ ; the chance is the square of its sine.
Here $\theta \approx 11.54^\circ$ and $5\theta \approx 57.68^\circ$ .

Show the answer

Answer: $0.714$

$\theta = \arcsin\sqrt{\tfrac{1}{25}} \approx 11.54^\circ$ , so 2 rounds reach $5\theta \approx 57.68^\circ$ , and $\sin^2(57.68^\circ) \approx 0.714$ .

$\sin\theta = \sqrt{\tfrac{1}{25}}$ gives $\theta \approx 11.54^\circ$ . Each round adds $2\theta$ to the angle, so after 2 rounds it is $(2\cdot2+1)\theta \approx 57.68^\circ$ . The chance of a good outcome is $\sin^2(57.68^\circ) \approx 0.714$ .

Common slips

$\frac{13}{25}$ : That uses the angle $2k\theta$ . The state starts at $\theta$ , so after 2 rounds it is at $(2k+1)\theta = 5\theta$ .
$0.323$ : That turns by $\theta$ per round. Two reflections whose mirrors meet at $\theta$ turn the state by $2\theta$ .
$1$ : That grows the amplitude in a straight line, $(2k+1)\sqrt p$ , which only holds while the angle is small. Use $\sin((2k+1)\theta)$ itself.
$\frac{1}{25}$ : That is the chance before any round.

Check yourself

Grover search over $N = 2^{16}$ items, of which $M = 16$ are marked. About how many iterations make finding a marked item most likely?

Hints

Grover is amplitude amplification with $p = M/N$ . For small $p$ , $\theta \approx \sqrt p$ in radians.
Iterations $\approx \dfrac{\pi}{4\theta} \approx \dfrac{\pi}{4}\sqrt{N/M}$ .

Show the answer

Answer: $50$

$\sqrt{N/M} = 64$ , so about $\tfrac{\pi}{4}\cdot 64 \approx 50.3$ iterations. The exact rule, $k$ nearest to $\tfrac{\pi}{4\theta} - \tfrac12$ , gives $k = 50$ , with success chance over 99.9%.

Here $p = M/N = 16/2^{16}$ , so $\sin\theta = \sqrt p$ and $\theta \approx 0.0156$ radians. The best $k$ makes $(2k+1)\theta$ closest to $\tfrac{\pi}{2}$ : $k \approx \tfrac{\pi}{4\theta} - \tfrac12$ , which rounds to 50. The quick estimate $\tfrac{\pi}{4}\sqrt{N/M} \approx 50.3$ is within one of it.

Common slips

$64$ : $\sqrt{N/M} = 64$ sets the scale, but it is not the count. Each iteration turns the state by $2\theta \approx 2\sqrt{M/N}$ radians, and it only needs to turn about $\tfrac{\pi}{2}$ : that takes about $\tfrac{\pi}{4}\cdot 64 \approx 50$ iterations.
$4096$ : 4,096 is $1/p = N/M$ , the average number of random guesses. Iterations grow like the square root of that.
$201$ : 201 is the count for one marked item. With $M = 16$ marked items $\sin\theta = \sqrt{M/N}$ is $\sqrt{16} = 4$ times larger, so 4 times fewer iterations are needed.

Check yourself

You don’t know $p$ ; in fact $p = \tfrac14$ , so $\theta = 30^\circ$ . You pick $k$ at random from $0$ to $1$ (so $m = 2$ ), run $A$ and $k$ rounds of $Q$ , and measure. What is the chance of a good outcome?

Hints

List the angles $(2k+1)\theta$ for each allowed $k$ .
The angles are $30^\circ, 90^\circ$ . Square each sine, then average the 2 values.

Show the answer

Answer: $\frac{5}{8}$

The angles $30^\circ, 90^\circ$ give chances $\tfrac14, 1$ . Each $k$ is equally likely, so the chance is their average, $\tfrac{5}{8}$ .

With $\theta = 30^\circ$ , the allowed $k = 0, \ldots, 1$ end at the angles $(2k+1)\theta = 30^\circ, 90^\circ$ . Their chances $\sin^2((2k+1)\theta)$ are $\tfrac14, 1$ . Picking $k$ uniformly at random, the chance of a good outcome is the average of these 2 numbers: $\tfrac{5}{8} \approx 0.625$ .

Common slips

$\frac{1}{2}$ : $\tfrac12$ is where the average settles when $m$ is large. For $m = 2$ , average the 2 chances themselves: $\tfrac14, 1$ .
$1$ : That is the best single $k$ . Here $k$ is random, so every choice from 0 to 1 counts equally: average the 2 chances.
$\frac{1}{4}$ : That is $k = 0$ alone: no rounds at all. Average over all the allowed $k$ .

11 / 13 · Explain

Explain it

Each piece of $Q$ only flips signs or undoes $A$ . Explain why applying $Q$ to $A\ket{0\ldots0}$ still raises the chance of a good outcome, and why too many rounds lower it again.

Show a model answer

Write $A\ket{0\ldots0} = \sin\theta\ket{\text{good}} + \cos\theta\ket{\text{bad}}$ with $\sin\theta = \sqrt p$ . In the plane of these two states, $S_{\text{good}}$ flips the good part, which is a reflection in the $\ket{\text{bad}}$ line, and $-AS_0A^{-1}$ is a reflection in the line of $A\ket{0\ldots0}$ . The two lines meet at angle $\theta$ , and two reflections make a rotation by twice that angle: each round turns the state $2\theta$ toward $\ket{\text{good}}$ . After $k$ rounds the angle is $(2k+1)\theta$ and the chance is $\sin^2((2k+1)\theta)$ , which grows until the angle reaches $90^\circ$ . More rounds carry the state past $\ket{\text{good}}$ , and the chance falls again.

A good answer covers

$S_{\text{good}}$ is a reflection that flips the good part, and $-AS_0A^{-1}$ is a reflection in the line of $A\ket{0\ldots0}$
Two reflections make a rotation by $2\theta$ toward $\ket{\text{good}}$ , where $\sin\theta = \sqrt p$
After $k$ rounds the chance is $\sin^2((2k+1)\theta)$
Past $90^\circ$ the state turns away from $\ket{\text{good}}$ , so the chance falls

12 / 13 · Mastery check

Mastery check

Check yourself

An algorithm $A$ gives a good answer with probability $p$ , and you can check any answer. Rerunning $A$ until it succeeds takes about $1/p$ runs, so if $p$ becomes a million times smaller, rerunning costs a million times more. This lesson’s method replaces rerunning. If $p$ becomes a million times smaller, how does the cost of that method change?

AIt grows a million times too: nothing beats rerunning
BIt grows about 1,000 times
CIt grows by a fixed amount: about 20 more rounds
DIt doesn’t change: one quantum run checks every answer at once

Show the answer

Answer: B. It grows about 1,000 times

Each round turns the state by $2\theta$ , where $\sin\theta = \sqrt p$ , and it has to turn through about $90^\circ$ . For small $p$ , $\theta \approx \sqrt p$ radians, so it takes about $\tfrac{\pi}{4}/\sqrt p$ rounds: a million times smaller $p$ means 1,000 times more rounds.

Why not the others

A. Rerunning grows like $1/p$ , but it is not the only option. Amplitude amplification turns the state by a fixed angle per round, and the number of rounds grows like $1/\sqrt p$ : a million times smaller $p$ costs only 1,000 times more.
C. That would be a logarithmic cost, like halving an interval 20 times. Amplitude amplification gains a square root, not more: a million times smaller $p$ needs about 1,000 times as many rounds, and no method does better in general.
D. A run on a superposition still ends in one measurement with one random result. The good results have to be made likely first, and that takes rounds: about $\tfrac{\pi}{4}/\sqrt p$ of them.

Check yourself

Let $\ket\psi = A\ket{0\ldots0}$ , and let $\ket\phi$ be any state orthogonal to $\ket\psi$ . What does $-AS_0A^{-1}$ do to $\ket\phi$ ?

ATurns it toward the good states
BLeaves it unchanged
CMultiplies it by $-1$
DSends it to $\ket{0\ldots0}$

Show the answer

Answer: C. Multiplies it by $-1$

$A^{-1}\ket\phi$ is orthogonal to $\ket{0\ldots0}$ , so $S_0$ leaves it alone, $A$ returns $\ket\phi$ , and the leading minus sign gives $-\ket\phi$ . With $\ket\psi \mapsto \ket\psi$ , that makes $-AS_0A^{-1} = 2\ket\psi\bra\psi - I$ , the mirror in the line of $\ket\psi$ .

Why not the others

A. Half of $Q$ only reflects: it fixes the line of $\ket\psi$ and flips everything orthogonal to it. A turn toward the good states needs both halves of $Q$ .
B. $A^{-1}\ket\phi$ is orthogonal to $A^{-1}\ket\psi = \ket{0\ldots0}$ , so $S_0$ leaves it alone, and $A$ brings back $\ket\phi$ . The minus sign in front then flips it. It is $\ket\psi$ that stays unchanged.
D. $A^{-1}$ alone sends $\ket\psi$ , not $\ket\phi$ , to $\ket{0\ldots0}$ , and $A$ undoes that at the end. The net effect on $\ket\phi$ is a sign: $-\ket\phi$ .

Check yourself

An algorithm succeeds with probability $p = \tfrac18$ . You run $A$ and then one round of $Q$ . What is the chance of a good outcome now? (A fraction, or three decimal places.)

Hints

Find $\theta$ from $\sin\theta = \sqrt p$ .
One round takes the angle from $\theta$ to $3\theta$ ; the chance is $\sin^2 3\theta$ .

Show the answer

Answer: $\frac{25}{32}$

$\theta = \arcsin\sqrt{\tfrac18} \approx 20.70^\circ$ , so $3\theta \approx 62.11^\circ$ and $\sin^2 3\theta = \tfrac{25}{32} \approx 0.781$ . In general one round gives $p(3 - 4p)^2$ , from $\sin 3\theta = 3\sin\theta - 4\sin^3\theta$ .

From $\sin\theta = \sqrt p = \sqrt{\tfrac18}$ , $\theta \approx 20.70^\circ$ . One round of $Q$ turns the state by $2\theta$ , from $\theta$ to $3\theta \approx 62.11^\circ$ . The chance of a good outcome is $\sin^2(62.11^\circ) \approx 0.781$ .

Common slips

$\frac{1}{8}$ : That is $p$ , the chance before the round. One round turns the state from $\theta \approx 20.70^\circ$ to $3\theta \approx 62.11^\circ$ .
$\frac{3}{8}$ : One round does not add $p$ twice more. $Q$ acts on amplitudes: it turns the state by $2\theta$ , and the chance is $\sin^2 3\theta$ .
$0.438$ : That is $\sin^2 2\theta$ . The state starts at angle $\theta$ , so one turn of $2\theta$ takes it to $3\theta$ .

Check yourself

A Grover search over $N = 512$ items is tuned for one marked item: it makes 17 iterations, which find that item with probability 99.9%. Unknown to you, 4 items are marked. With the same 17 iterations, what is the chance of finding a marked item?

AOver 99.9%: more marked items are easier to find
BAbout 99.9%: the number of marked items doesn’t matter
CAbout 0.8%, the chance of a random guess
DAbout 0.2%, worse than a random guess

Show the answer

Answer: D. About 0.2%, worse than a random guess

With one marked item $\sin\theta = \sqrt{1/512}$ , so $\theta \approx 2.53^\circ$ , and 17 iterations reach $35\theta \approx 88.7^\circ$ . With 4 marked items $\sin\theta$ doubles: $\theta \approx 5.07^\circ$ , and the same 17 iterations reach about $177.5^\circ$ , past $\ket{\text{good}}$ at $90^\circ$ and nearly round to the unmarked side. The chance is $\sin^2(177.5^\circ) \approx 0.002$ , while a random guess gets $4/512 \approx 0.008$ .

Why not the others

A. More marked items make each iteration turn the state further: $\sin\theta = \sqrt{4/512}$ is twice $\sqrt{1/512}$ . 17 iterations then carry the state past the marked items, so more turning is not better here.
B. The angle of each iteration depends on how many items are marked. With 4 of them $\theta$ is about twice as large, so 17 iterations turn the state about twice as far as planned.
C. The iterations are not wasted: they move the state, just too far. It ends close to the unmarked states, and the chance, 0.2%, is below even a random guess.

Check yourself

Grover search over $N = 2^{16}$ items, of which $M = 1$ is marked. About how many iterations make finding a marked item most likely?

Hints

Grover is amplitude amplification with $p = M/N$ . For small $p$ , $\theta \approx \sqrt p$ in radians.
Iterations $\approx \dfrac{\pi}{4\theta} \approx \dfrac{\pi}{4}\sqrt{N/M}$ .

Show the answer

Answer: $201$

$\sqrt{N/M} = 256$ , so about $\tfrac{\pi}{4}\cdot 256 \approx 201.1$ iterations. The exact rule, $k$ nearest to $\tfrac{\pi}{4\theta} - \tfrac12$ , gives $k = 201$ , with success chance over 99.9%.

Here $p = M/N = 1/2^{16}$ , so $\sin\theta = \sqrt p$ and $\theta \approx 0.00391$ radians. The best $k$ makes $(2k+1)\theta$ closest to $\tfrac{\pi}{2}$ : $k \approx \tfrac{\pi}{4\theta} - \tfrac12$ , which rounds to 201. The quick estimate $\tfrac{\pi}{4}\sqrt{N/M} \approx 201.1$ is within one of it.

Common slips

$256$ : $\sqrt{N/M} = 256$ sets the scale, but it is not the count. Each iteration turns the state by $2\theta \approx 2\sqrt{M/N}$ radians, and it only needs to turn about $\tfrac{\pi}{2}$ : that takes about $\tfrac{\pi}{4}\cdot 256 \approx 201$ iterations.
$65536$ : 65,536 is $1/p = N/M$ , the average number of random guesses. Iterations grow like the square root of that.
$32768$ : 32,768 is $N/2$ , about how many items a classical search checks on average. Grover needs about $\tfrac{\pi}{4}\sqrt{N}$ iterations.

Check yourself

You don’t know $p$ ; in fact $p = \tfrac14$ , so $\theta = 30^\circ$ . You pick $k$ at random from $0$ to $3$ (so $m = 4$ ), run $A$ and $k$ rounds of $Q$ , and measure. What is the chance of a good outcome?

Hints

List the angles $(2k+1)\theta$ for each allowed $k$ .
The angles are $30^\circ, 90^\circ, 150^\circ, 210^\circ$ . Square each sine, then average the 4 values.

Show the answer

Answer: $\frac{7}{16}$

The angles $30^\circ, 90^\circ, 150^\circ, 210^\circ$ give chances $\tfrac14, 1, \tfrac14, \tfrac14$ . Each $k$ is equally likely, so the chance is their average, $\tfrac{7}{16}$ .

With $\theta = 30^\circ$ , the allowed $k = 0, \ldots, 3$ end at the angles $(2k+1)\theta = 30^\circ, 90^\circ, 150^\circ, 210^\circ$ . Their chances $\sin^2((2k+1)\theta)$ are $\tfrac14, 1, \tfrac14, \tfrac14$ . Picking $k$ uniformly at random, the chance of a good outcome is the average of these 4 numbers: $\tfrac{7}{16} \approx 0.437$ .

Common slips

$\frac{1}{2}$ : $\tfrac12$ is where the average settles when $m$ is large. For $m = 4$ , average the 4 chances themselves: $\tfrac14, 1, \tfrac14, \tfrac14$ .
$1$ : That is the best single $k$ . Here $k$ is random, so every choice from 0 to 3 counts equally: average the 4 chances.
$\frac{1}{4}$ : That is $k = 0$ alone: no rounds at all. Average over all the allowed $k$ .

Check yourself

Someone claims a quantum algorithm that finds the one marked item among $N = 2^{40}$ items, with nothing known about where it is, using 1,000 queries. What should you think?

APlausible, if it applies $Q$ about 1,000 times
BIt can’t be right as stated: every quantum method needs on the order of $\sqrt N = 2^{20}$ , about a million, queries
CPlausible, if it picks the number of rounds at random
DPlausible: quantum algorithms are exponentially faster than classical ones

Show the answer

Answer: B. It can’t be right as stated: every quantum method needs on the order of $\sqrt N = 2^{20}$ , about a million, queries

For unstructured search every quantum algorithm needs order $\sqrt N$ queries, and $\sqrt{2^{40}} = 2^{20}$ . Grover’s $\tfrac{\pi}{4}\sqrt N \approx 820{,}000$ is within a constant factor of that limit. A method using 1,000 queries must be exploiting structure that the problem, as stated, doesn’t have.

Why not the others

A. Every round of $Q$ is a query: it uses $S_{\text{good}}$ once. With one marked item among $2^{40}$ , about $\tfrac{\pi}{4}\cdot 2^{20} \approx 820{,}000$ rounds are needed.
C. Picking $k$ at random handles an unknown number of marked items. It costs a constant factor more than knowing that number, never less.
D. Some problems have exponential quantum speed-ups, but unstructured search is proven not to: any quantum algorithm needs order $\sqrt N$ queries, here about $2^{20}$ .

13 / 13 · Recap

Recap

From memory

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

Write the iterate $Q$ and say what each piece does.
Show the key points
- $Q = -AS_0A^{-1}S_{\text{good}}$ ; read right to left, so $S_{\text{good}}$ acts first
- $S_{\text{good}}$ flips the sign of the good states; $S_0$ flips the sign of $\ket{0\ldots0}$
- $A^{-1}$ undoes $A$ ; the minus sign is a global phase
- Grover search is the case $A = H^{\otimes n}$
How many rounds should you run, what is the success chance, and how does that compare with rerunning $A$ ?
Show the key points
- $\sin\theta = \sqrt p$ ; after $k$ rounds the chance is $\sin^2((2k+1)\theta)$
- $k$ nearest $\tfrac{90^\circ}{2\theta} - \tfrac12$ , about $\tfrac{\pi}{4}/\sqrt p$ ; more rounds overshoot
- Rerunning needs about $1/p$ runs
What do you do when $p$ is unknown, and what does Grover search not give you?
Show the key points
- Pick $k$ at random below $m$ , and grow $m$ by a factor such as $\tfrac65$ after each failure
- Once $m \ge 1/\sin 2\theta$ a try succeeds with chance at least $\tfrac14$ ; the expected cost stays of order $1/\sqrt p$
- Stored data must be loaded (order $N$ ), the oracle is a circuit, and order $\sqrt N$ queries is the proven minimum

Key ideas

Amplitude amplification: for any algorithm $A$ without measurements and any way to recognize good outcomes, $Q = -AS_0A^{-1}S_{\text{good}}$ turns $A\ket{0\ldots0}$ toward the good states.
Two reflections make one rotation: with $\sin\theta = \sqrt p$ , $k$ rounds succeed with chance $\sin^2((2k+1)\theta)$ . For $p = \tfrac14$ , one round gives certainty.
About $\tfrac{\pi}{4}/\sqrt p$ rounds instead of about $1/p$ reruns. Grover search is the case $A = H^{\otimes n}$ , $p = M/N$ .
Unknown $p$ : pick $k$ at random below a bound $m$ that grows by a constant factor. The expected cost stays of order $1/\sqrt p$ , and if order $\sqrt N$ queries find nothing, report “none”.
Grover search is no fast database lookup: loading costs order $N$ , the oracle is a circuit, and order $\sqrt N$ queries is the proven minimum for unstructured search.

Go further

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

Amplitude amplificationWikipedia · Article
A short reference page that derives the general algorithm with good and bad subspaces and shows Grover search as a special case.
Quantum Amplitude Amplification and EstimationBrassard, Høyer, Mosca and Tapp · Article
The research paper behind this lesson’s iterate Q, with its rotation analysis and the case of an unknown success chance.
Tight bounds on quantum searchingBoyer, Brassard, Høyer and Tapp · Article
The 1998 paper with the random-k method for an unknown number of solutions, readable with this lesson in hand.
Strengths and Weaknesses of Quantum ComputingBennett, Bernstein, Brassard and Vazirani · Article
The 1997 paper proving that no quantum algorithm searches without structure in far fewer than √N queries.