Exercises: Chapter 11 — Quantum Parallelism and Interference — How Quantum Algorithms Get Their Speedup

Exercise 11.1 — Hadamard Transform Proof Prove that $H^{\otimes n}|x\rangle = \frac{1}{\sqrt{2^n}} \sum_{y \in \{0,1\}^n} (-1)^{x \cdot y} |y\rangle$, where $x \cdot y = \sum_i x_i y_i \pmod{2}$. Use this to explain why applying $H^{\otimes n}$ twice returns the original state.

Exercise 11.2 — Phase Kickback with Multiple Qubits Generalize the phase kickback to an $n$-qubit input register and an $m$-qubit output register. Show that if the output register is prepared in the state $\frac{1}{\sqrt{2^m}} \sum_{y} (-1)^{y \cdot z} |y\rangle$ for some fixed $z$, the oracle $U_f$ imparts a phase of $(-1)^{f(x) \cdot z}$ to the input state $|x\rangle$.

Exercise 11.3 — Deutsch's Algorithm Variant Design a variant of Deutsch's algorithm that determines whether $f(0) = f(1)$ using only the phase kickback on a single qubit (no ancilla). Implement it in Qiskit and verify.

Exercise 11.4 — Interference Patterns For $n=2$ qubits, start with $H^{\otimes 2}|00\rangle$, apply a phase flip ($Z$ gate) to qubit 0, then apply $H^{\otimes 2}$ again. Compute the resulting state analytically. What is the probability of measuring $|00\rangle$? Explain the interference that produces this result.

Exercise 11.5 — Classical vs Quantum Query Complexity Prove that any classical deterministic algorithm for Deutsch's problem requires at least 2 queries to the oracle. Then explain why the quantum algorithm achieves the same task with 1 query. What property of quantum mechanics enables this?

Exercise 11.6 — Multi-Qubit Phase Oracle Construct the phase oracle for the function $f(x_1, x_2, x_3) = x_1 \oplus x_2 \cdot x_3$ on 3 qubits. Write the circuit in terms of standard gates. Compute the state after phase kickback when the oracle is applied to the uniform superposition $H^{\otimes 3}|000\rangle$.

Exercise 11.7 — Interference and the Inner Product Show that applying $H^{\otimes n}$ to a state $\sum_x \alpha_x |x\rangle$ produces amplitudes $\beta_y = \frac{1}{\sqrt{2^n}} \sum_x (-1)^{x \cdot y} \alpha_x$. Explain why this is a "Walsh-Hadamard transform" of the coefficient vector. What is the relationship to the Fourier transform?

Exercise 11.8 — Amplitude Amplification Numerics For $N = 256$ and $M = 1$ solution, compute the success probability of Grover's algorithm after $k = 0, 1, 2, \ldots, 20$ iterations. Plot the success probability as a function of $k$. At what value of $k$ does the probability first exceed 0.99? At what value does it first drop below 0.5 after peaking? Explain this behavior.

Exercise 11.9 — Entanglement and Phase Kickback Consider a 2-qubit oracle $U_f$ with $f(x_1, x_2) = x_1 \oplus x_2$ (XOR). After applying $U_f$ to $H^{\otimes 2}|00\rangle \otimes |-\rangle$, is the resulting state entangled? Compute the reduced density matrix of the input register and determine whether it is mixed or pure. What does this tell you about the role of entanglement in phase kickback?

Exercise 11.10 — Constructive and Destructive Interference Consider a 2-qubit system in the state $\frac{1}{2}(|00\rangle + |01\rangle + |10\rangle - |11\rangle)$. Apply $H^{\otimes 2}$ and compute the probability of each outcome. Identify which outcomes exhibit constructive interference (probability > 1/4) and which exhibit destructive interference (probability < 1/4). Explain the pattern in terms of the initial phase assignments.