Lesson 16: Grover search

Answer: D. $1$: it finds $10$ every time

Why not the others

• A. The oracle alone would change no probability: it only flips the sign of $\ket{10}$. The diffusion step turns that sign into probability. After the oracle the amplitudes are three $\tfrac12$⁠s and one $-\tfrac12$, with mean $\tfrac14$; reflecting each about the mean gives $2\cdot\tfrac14 + \tfrac12 = 1$ for $\ket{10}$ and $2\cdot\tfrac14 - \tfrac12 = 0$ for the rest.
• B. One iteration doesn’t add a fixed share of probability. Work out the amplitudes: after the oracle they are $\tfrac12$, $\tfrac12$, $\tfrac12$ and $-\tfrac12$ on $\ket{10}$, with mean $\tfrac14$. The diffusion step sends each $a$ to $2\cdot\tfrac14 - a$: 1 for $\ket{10}$, 0 for the others.
• C. It is natural to expect a gradual climb that reaches certainty only after many steps. For four items one step is already exact: the diffusion step sends every amplitude $a$ to $2\cdot\tfrac14 - a$, which gives $\ket{10}$ amplitude 1 and the other three amplitude 0.

Answer: C. It falls, to about 33%

Why not the others

• A. It seems that more of a good thing must help. But every iteration turns the state by the same angle, $2\theta$, in a plane. After 2 iterations it is close to the marked direction, and one more turn carries it past: the chance falls to 33%.
• B. Nothing settles. Every iteration is the same rotation by $2\theta$, applied again, so the state keeps turning, past the marked direction, and the chance falls to 33%.
• D. One more iteration turns the state only $2\theta$ further, not all the way back. The chance falls to 33%, still well above $1/8$.

Answer: $63$

Common slips

• $64$: You never need to check the last item. Exactly one is marked, so if the first 63 checks all say no, the last item must be it.
• $32$: About $N/2$ is the average: often the marked item turns up early. The worst case is that the first 63 checks all fail.
• $6$: That would be a binary search, which needs a sorted list and questions like “is it in the first half?”. Here a check only answers “is this the one?”, so each check rules out a single item.

Answer: $\frac{1}{2}|00\rangle + \frac{1}{2}|01\rangle - \frac{1}{2}|10\rangle + \frac{1}{2}|11\rangle$

Answer: $P(10) = \frac{1}{4}$

Common slips

• $1$: The oracle marks $\ket{10}$ with a sign, but a sign changes no probability: $\abs{-\tfrac12}^2 = \tfrac14$, the same as every other item.
• $0$: A negative amplitude still has a positive probability: $(-\tfrac12)^2 = \tfrac14$.

Answer: $1$

Common slips

• $-\frac{1}{2}$: That leaves the amplitude where it was. $D$ moves every amplitude to $2\bar a - a$, and $-\tfrac12$ is far below the mean.
• $\frac{1}{2}$: That only undoes the oracle’s sign flip, a reflection about zero. $D$ reflects about the mean, $\tfrac14$: $2\cdot\tfrac14 - (-\tfrac12) = 1$.
• $\frac{1}{4}$: That is the mean of the four amplitudes. $D$ reflects each amplitude about it: $2\cdot\tfrac14 - (-\tfrac12) = 1$.
• $0$: That is the new amplitude of each unmarked item, $2\cdot\tfrac14 - \tfrac12 = 0$. The marked one starts below the mean, so it ends above: $2\cdot\tfrac14 + \tfrac12 = 1$.

Answer: A. $H$ on every qubit, $X$ on every qubit, a $CCZ$, $X$ on every qubit, $H$ on every qubit

Why not the others

• B. A layer of Hadamards is not a reflection about $\ket s$: it sends $\ket s$ to $\ket{000}$, while $D$ leaves $\ket s$ alone. The Hadamards only change basis. The reflection itself is a sign flip on $\ket{000}$, made between two Hadamard layers.
• C. A $CCZ$ flips the sign of $\ket{111}$, so this reflects about $H^{\otimes 3}\ket{111}$, a state full of minus signs, not $\ket s$. The $X$ layers move the flip onto $\ket{000}$, which the Hadamards then turn into $\ket s$.
• D. That flips the sign of $\ket{000}$ alone, so its mirror passes through $\ket{000}$, not $\ket s$. Hadamards on both sides move the mirror to $H^{\otimes 3}\ket{000} = \ket s$.

Answer: $2$

Common slips

• $3$: Look again at the third iteration: the chance falls from 94.5% to 33%. More iterations don’t always help.
• $1$: One iteration gives 78.1%, but a second raises it to 94.5%.
• $4$: Four is $N/2$, the classical average. In the lab the chance peaks at 94.5% after two iterations and has fallen to about 1% by the fourth.

Answer: A. Nothing: the mean stays where it is

Why not the others

• B. The marked bar rises a lot, but the seven others each fall a little, and the mean line doesn’t move. Each bar ends as far from the mean as it started, on the other side, so the gains and losses cancel.
• C. The seven unmarked bars do get shorter, but the marked bar rises by just as much in total. Reflecting every bar in the mean line leaves the line where it was.
• D. Reflecting about the mean doesn’t move the mean anywhere: each amplitude $a$ goes to $2\bar a - a$, and the average of those is $2\bar a - \bar a = \bar a$.

Answer: $\theta = 14.477$

Common slips

• $3.583$: That uses $\sin\theta = M/N$. The $\ket{\text{good}}$ part of $\ket s$ is an amplitude, $\sqrt{M/N}$, so $\sin\theta = \sqrt{1/16}$.
• $0.253$: That is $\theta$ in radians (or $\sin\theta$, which is close to it when $\theta$ is small). The question asks for degrees: $\theta \approx 14.48^\circ$.
• $28.955$: That is $2\theta$, the turn made by one iteration. $\theta$ is the angle between $\ket s$ and $\ket{\text{bad}}$.
• $75.522$: That is the angle between $\ket s$ and $\ket{\text{good}}$. $\theta$ is measured from $\ket{\text{bad}}$, and $\sin\theta$ is the $\ket{\text{good}}$ part of $\ket s$.

Answer: $P = 0.473$

Common slips

• $\frac{11}{16}$: That is $\sin(3\theta)$, the marked item’s amplitude. The chance is its square, $\sin^2(3\theta)$.
• $\frac{15}{64}$: That puts the state at $2\theta$. It starts at $\theta$, not at 0, so after one iteration it is at $(2\cdot1 + 1)\theta = 3\theta$.
• $\frac{9}{16}$: That is the small-angle estimate $\sin^2 x \approx x^2$ with $x \approx 3/\sqrt{16}$. At $43.4^\circ$ the angle is too large for it: take $\sin^2$ itself.

Answer: C. $M/N = \tfrac14$, as for one marked item among four, so $\theta = 30^\circ$ and one iteration reaches $3\theta = 90^\circ$

Why not the others

• A. Press One iteration (O, then D) again: the chance falls to 25%. The state turns past $90^\circ$ to $5\theta = 150^\circ$, and $\sin^2 150^\circ = \tfrac14$.
• B. The count shrinks like $1/\sqrt M$, not $1/M$: twice as many marked items need about $1/\sqrt2$ as many iterations. What decides it here is the angle: $\sin\theta = \sqrt{2/8} = \tfrac12$, so $\theta = 30^\circ$ and one iteration lands on exactly $90^\circ$.
• D. Twice the work per step would double the gain, and with one marked item one iteration gave 78.1%: double that is more than 100%. The real reason is the angle: $\sin\theta = \sqrt{2/8} = \tfrac12$, so $\theta = 30^\circ$ and one turn of $2\theta$ reaches $90^\circ$.

Answer: $3$

Common slips

• $8$: That is $N/2$, the average for a classical search. Grover search needs only about $\tfrac{\pi}{4}\sqrt N$ iterations.
• $4$: One more than the best overshoots. After 4 iterations the state is at $130.3^\circ$, further from $90^\circ$ than $101.3^\circ$, and the chance drops from 96.1% to 58.2%.
• $2$: One fewer stops short: after 2 iterations the state is at $72.4^\circ$, and the chance is 90.8%, against 96.1% after 3.

Answer: $25$

Common slips

• $512$: That is $N/2$, the average for a classical search. Grover search needs only about $\tfrac{\pi}{4}\sqrt N$ iterations.
• $26$: One more than the best overshoots. After 26 iterations the state is at $94.9^\circ$, further from $90^\circ$ than $91.3^\circ$, and the chance drops from 99.9% to 99.3%.
• $32$: $\sqrt{N/M}$ is how the count grows, but the constant matters. The state must turn through about $90^\circ$, in steps of $2\theta$, which takes about $\tfrac{\pi}{4}\sqrt{N/M}$ iterations. 32 iterations give only 80.2%.
• $24$: One fewer stops short: after 24 iterations the state is at $87.7^\circ$, and the chance is 99.8%, against 99.9% after 25.

Answer: B. About $2^{64}$ (more exactly $\tfrac{\pi}{4}\cdot 2^{64} \approx 1.4\times10^{19}$)

Why not the others

• A. One query does act on every key in superposition, but all it does is flip the sign of the right one, which no measurement can see. Turning that sign into a high chance takes about $\tfrac{\pi}{4}\sqrt N$ rounds of oracle and diffusion.
• C. That is the classical average: test keys one at a time and you expect to go through half of them. Grover search needs about the square root of $N$, which is $2^{64}$.
• D. That would be an exponential speedup, and Grover search doesn’t give one. Each iteration turns the state by about $2/\sqrt N$ radians, so it takes about $\tfrac{\pi}{4}\sqrt N = \tfrac{\pi}{4}\cdot 2^{64}$ queries: the square root of $N$, not its logarithm.

One circuit that works: H on q0 and q1, then CZ q0→q1, then H on q0 and q1, then X on q0 and q1, then CZ q0→q1, then X on q0 and q1, then H on q0 and q1.

Answer: D. 1110

Why not the others

• A. The oracle and diffusion steps don’t just spread amplitude around. After 3 iterations the marked item has probability 96.1%, so about 961 of the 1,000 shots give it.
• B. That flips every bit, as if the $X$ gates in the oracle changed the answer. They are undone right after the multi-controlled $Z$; they only move the sign flip onto $\ket{0111}$. The result is $\ket{0111}$, which Qiskit prints as 1110.
• C. That reads Qiskit’s string as a ket. Qiskit prints qubit 0 last, so $\ket{0111}$ shows up as 1110: the same bits in reverse order.

One program that works:

from qiskit import QuantumCircuit

def oracle(qc):
    # flip the sign of |110> (lesson order: qubit 0 first)
    qc.x(2)
    qc.ccz(0, 1, 2)
    qc.x(2)

def diffusion(qc):
    qc.h(range(3))
    qc.x(range(3))
    qc.ccz(0, 1, 2)
    qc.x(range(3))
    qc.h(range(3))

qc = QuantumCircuit(3)
qc.h(range(3))
for step in range(2):
    oracle(qc)
    diffusion(qc)
qc.measure_all()

Answer: $0.177$

Common slips

• $\frac{\sqrt{2}}{4}$: That leaves the unmarked amplitudes where they were. $D$ moves every amplitude: each $0.354$ sits a little above the mean $0.265$, so it ends a little below it.
• $\frac{3}{8\sqrt{2}}$: That is the mean after the oracle. $D$ reflects each amplitude about it, $a \to 2\bar a - a$: $2(0.265) - 0.354$.
• $\frac{5}{4\sqrt{2}}$: That is the marked item’s new amplitude. An unmarked item starts above the mean, at $0.354$, so it is reflected to just below it: $2(0.265) - 0.354$.

Answer: $P = 0.781$

Common slips

• $\frac{5}{4\sqrt{2}}$: That is $\sin(3\theta)$, the marked item’s amplitude. The chance is its square, $\sin^2(3\theta)$.
• $\frac{7}{16}$: That puts the state at $2\theta$. It starts at $\theta$, not at 0, so after one iteration it is at $(2\cdot1 + 1)\theta = 3\theta$.