Day 8 — Official Sample Gaps

Math Prep

Solve this BEFORE lesson.md. Day 8 is the sample test + gap day; the concept questions that surface there assume "quantum literacy": you can recognize the classic algorithms and say why they work in two sentences of math. This prep gives exactly that layer.

Requires: Days 1–7 math prep. Video back-up: Watrous Lessons 04–08 (entanglement protocols, query algorithms, QFT/QPE, Grover); notes in resource-artifactory/notes/video-notes/.

1. Phase kickback — the engine of everything

Let $U|u\rangle = e^{i\varphi}|u\rangle$ (eigenvector with eigenphase φ). Then controlled- $U$ with control in superposition:

C\text{-}U\;\big(\alpha|0\rangle + \beta|1\rangle\big)\otimes|u\rangle = \big(\alpha|0\rangle + \beta e^{i\varphi}|1\rangle\big)\otimes|u\rangle

The target is untouched; the phase lands on the control. Special case used by oracles: $X|-\rangle = -|-\rangle$ , so a CNOT targeting $|-\rangle$ flips the control's phase:

U_f: |x\rangle|-\rangle \mapsto (-1)^{f(x)}|x\rangle|-\rangle

This turns a function $f$ into a phase oracle — the trick inside Deutsch–Jozsa, Bernstein–Vazirani, and Grover.

2. The Hadamard sandwich

$n$ Hadamards create the uniform superposition; a second layer converts phases back to bits:

H^{\otimes n}|0^n\rangle = \tfrac{1}{\sqrt{2^n}}\sum_x |x\rangle, \qquad H^{\otimes n}|x\rangle = \tfrac{1}{\sqrt{2^n}}\sum_y (-1)^{x\cdot y}|y\rangle

( $x\cdot y$ = parity of shared 1-bits.)

Deutsch–Jozsa (f promised constant or balanced): H-layer → phase oracle → H-layer → measure. Amplitude of $|0^n\rangle$ at the end: $\tfrac{1}{2^n}\sum_x (-1)^{f(x)}$ = ±1 if constant, 0 if balanced. So: all-zeros ⇒ constant, anything else ⇒ balanced. 1 query vs classical $2^{n-1}+1$ (deterministic).

Bernstein–Vazirani ( $f(x) = s\cdot x$ ): same circuit; the interference maps the phase pattern $(-1)^{s\cdot x}$ straight to $|s\rangle$ . One query reads the whole hidden string.

3. Grover — amplitude amplification you can compute

Search space $N = 2^n$ items, $M$ marked. Geometry: the state stays in a 2-D plane spanned by "marked" and "unmarked" superpositions; one Grover iteration (phase oracle + diffusion $2|s\rangle\langle s| - I$ ) rotates by $2\theta$ where $\sin\theta = \sqrt{M/N}$ .

P(\text{success after } t \text{ iterations}) = \sin^2\big((2t{+}1)\theta\big),\qquad t_{\text{opt}} \approx \left\lfloor\frac{\pi}{4}\sqrt{\frac{N}{M}}\right\rfloor

Quadratic speedup: $O(\sqrt{N})$ vs classical $O(N)$ . Overshooting is real: past $t_{\text{opt}}$ the success probability decreases (keeps rotating). For $N=4, M=1$ : $\theta = \pi/6$ , ONE iteration gives $\sin^2(\pi/2) = 1$ — exact.

4. QFT and phase estimation — reading phases as numbers

\text{QFT}: |x\rangle \mapsto \tfrac{1}{\sqrt{2^n}}\sum_y e^{2\pi i x y / 2^n}|y\rangle

It's the unitary DFT matrix ( $\text{QFT}_1 = H$ ); circuit = H's + controlled phases, $O(n^2)$ gates.

Phase estimation (QPE): given $U|u\rangle = e^{2\pi i\varphi}|u\rangle$ , use $m$ control qubits running controlled- $U^{2^j}$ (kickback writes φ's binary digits into phases), then inverse QFT turns those phases into the bitstring of $\varphi \approx 0.\varphi_1\varphi_2\ldots\varphi_m$ (binary fraction). Exact when φ has an $m$ -bit binary expansion; otherwise concentrated near it. QPE + modular arithmetic = order finding = the quantum core of Shor's algorithm (period $r$ of $a^x \bmod N$ ⇒ factors via $\gcd(a^{r/2}\pm1, N)$ ) — exponential speedup over known classical factoring.

5. Teleportation & superdense coding — entanglement as a resource

Teleportation: move an unknown $|\psi\rangle$ using 1 shared Bell pair + 2 classical bits. Sender: CNOT then H then measure both qubits → 2 bits $(b_1 b_0)$ ; receiver applies $Z^{b_1} X^{b_0}$ . Why it works: rewriting $|\psi\rangle\otimes|\Phi^+\rangle$ in the Bell basis of the sender's two qubits shows the receiver's qubit already holds $|\psi\rangle$ up to one of the four Pauli corrections $\{I, X, Z, XZ\}$ . No cloning (original is measured away), no faster-than-light signaling (useless without the classical bits).

Superdense coding: the reverse trade — 1 Bell pair + sending 1 qubit transmits 2 classical bits. Encoder applies one of $\{I, X, Z, ZX\}$ to their half; the four results are the four orthogonal Bell states, distinguished by the decoder's CNOT+H measurement.

6. Speedup scoreboard (recognition table)

Algorithm	Problem	Quantum	Classical	Speedup
Deutsch–Jozsa	constant vs balanced	1 query	$2^{n-1}{+}1$	exponential (vs deterministic)
Bernstein–Vazirani	hidden dot-product string	1 query	$n$	polynomial
Simon	hidden XOR period	$O(n)$	$\Omega(2^{n/2})$	exponential
Grover	unstructured search	$O(\sqrt N)$	$O(N)$	quadratic
Shor	factoring	poly $(n)$	sub-exponential	(believed) exponential

PROBLEMS

P1. Show the kickback identity: apply CNOT with control $|+\rangle$ , target $|-\rangle$ ; write the output as (control state) ⊗ (target state).

P2. Deutsch's problem ( $n=1$ ): run H → phase oracle → H on the input qubit. Compute the final state for $f(x) = x$ and for constant $f(x) = 0$ . What does measuring tell you?

P3. Grover with $N = 8, M = 1$ : give θ, the optimal iteration count, and the success probability after 1 and 2 iterations.

P4. In Grover, what happens to the success probability if you run $2\,t_{\text{opt}}$ iterations instead of $t_{\text{opt}}$ (qualitatively, from the rotation picture)?

P5. QPE with 3 counting qubits on $U$ with eigenphase $\varphi = 5/8$ : which bitstring do you measure (with certainty)? Why is it certain here?

P6. In teleportation, the sender's measurement returns $b_1 b_0 = 10$ . The receiver's qubit currently holds $\alpha|0\rangle - \beta|1\rangle$ where the target was $\alpha|0\rangle + \beta|1\rangle$ . Verify the prescribed correction fixes it.

P8. Which algorithm does the circuit "H's on all qubits → oracle → H's on all qubits → measure; promised constant-or-balanced" implement, and what does outcome '000' mean?

ANSWERS

A1. $|+\rangle|-\rangle = \tfrac{1}{\sqrt2}(|0\rangle + |1\rangle)|-\rangle$ . CNOT: the $|1\rangle$ -branch applies X to $|-\rangle$ giving $-|-\rangle$ . Output $= \tfrac{1}{\sqrt2}(|0\rangle - |1\rangle)\otimes|-\rangle = |-\rangle \otimes |-\rangle$ . The control flipped $|+\rangle \to |-\rangle$ ; the target never changed. ∎

A2. State after the oracle: $\tfrac{1}{\sqrt2}\big((-1)^{f(0)}|0\rangle + (-1)^{f(1)}|1\rangle\big)$ (times the idle $|-\rangle$ ). For $f(x)=x$ : $|-\rangle \xrightarrow{H} |1\rangle$ . For $f=0$ : $|+\rangle \xrightarrow{H} |0\rangle$ . Measurement: 0 ⇒ constant, 1 ⇒ balanced — one query decides what classically needs two.

A3. $\sin\theta = \sqrt{1/8} \Rightarrow \theta \approx 0.3614$ rad. $t_{\text{opt}} = \lfloor \tfrac{\pi}{4}\sqrt8 \rfloor = \lfloor 2.22 \rfloor = 2$ . $P(1) = \sin^2(3\theta) \approx 0.78$ ; $P(2) = \sin^2(5\theta) \approx 0.945$ .

A4. The state rotates past the marked axis — success probability comes back DOWN. Grover is not "more iterations = better"; it's periodic in $t$ .

A5. $\varphi = 5/8 = 0.101_2$ — exactly 3 bits ⇒ QPE is exact ⇒ measure '101' with probability 1. Certainty holds precisely because $2^m\varphi = 8 \cdot \tfrac58 = 5$ is an integer.

A6. Correction for $b_1b_0 = 10$ is $Z^{1}X^{0} = Z$ . $Z(\alpha|0\rangle - \beta|1\rangle) = \alpha|0\rangle + \beta|1\rangle$ . ✓

A7. $V|+\rangle|0\rangle = \tfrac{1}{\sqrt2}(V|00\rangle + V|10\rangle) = \tfrac{1}{\sqrt2}(|00\rangle + |11\rangle)$ — a Bell state. Cloning demands $|+\rangle|+\rangle = \tfrac12(|00\rangle{+}|01\rangle{+}|10\rangle{+}|11\rangle)$ . Different states ⇒ no unitary clones all inputs. (What $V$ actually is — CNOT — is how we entangle instead of clone.)

A8. Deutsch–Jozsa. '000' (all zeros) ⇒ $f$ is constant; any other outcome ⇒ balanced.

Self-check: you can derive kickback in two lines, run DJ on $n=1$ by hand, compute Grover's θ and $t_{\text{opt}}$ for any N, state what QPE outputs, and reproduce the teleportation correction table $\{I, X, Z, ZX\}$ .