Chapter 25 Exercises: Quantum Information and Computation

Contributors to Quantum Mechanics: From Wavefunctions to Qubits

Chapter 25 Exercises: Quantum Information and Computation

Part A: Conceptual Questions (⭐)

These questions test your understanding of the core ideas. No calculations required unless stated.

A.1 Explain in your own words why a quantum computer with $n$ qubits does not simply "try all $2^n$ answers simultaneously." What role does interference play, and why is it essential?

A.2 A classical bit can be either 0 or 1. A qubit can be in a superposition $\alpha|0\rangle + \beta|1\rangle$. Does this mean a qubit stores more information than a classical bit? Carefully distinguish between the information encoded in the state and the information extracted by measurement.

A.3 The no-cloning theorem states that no quantum operation can copy an arbitrary unknown quantum state. Explain why this is a consequence of the linearity of quantum mechanics, and discuss one important implication for quantum computing or quantum communication.

A.4 Why must all quantum gates be unitary? What physical principle does unitarity enforce? Give an example of a classical logic gate that is not reversible and explain why it cannot be directly implemented as a quantum gate.

A.5 The Hadamard gate satisfies $H^2 = I$. On the Bloch sphere, $H$ is a rotation by $\pi$ about the axis $(\hat{x} + \hat{z})/\sqrt{2}$. Verify geometrically that two such rotations return to the original state.

A.6 Explain the concept of phase kickback and why it is essential to both the Deutsch-Jozsa and Grover algorithms. What happens to the ancilla qubit, and why is it typically prepared in the state $|-\rangle$?

A.7 In Grover's algorithm, what goes wrong if you apply too many iterations? How is this qualitatively different from classical search, where more computation never hurts?

A.8 A quantum computer uses entanglement as a computational resource. But Bell's theorem tells us that entanglement cannot be used to send information faster than light. Reconcile these two statements.

Part B: Applied Problems (⭐⭐)

B.1: Qubit State Calculations

A qubit is in the state $|\psi\rangle = \frac{1}{\sqrt{3}}|0\rangle + \sqrt{\frac{2}{3}}e^{i\pi/4}|1\rangle$.

(a) What is the probability of measuring $|0\rangle$? Of measuring $|1\rangle$?

(b) Find the Bloch sphere coordinates $(\theta, \varphi)$.

(c) Find the Bloch vector $\vec{r} = (\sin\theta\cos\varphi, \sin\theta\sin\varphi, \cos\theta)$.

(d) Write the density matrix $\rho = |\psi\rangle\langle\psi|$ explicitly.

(e) Verify that $\rho = \frac{1}{2}(I + \vec{r}\cdot\vec{\sigma})$ using your answers from (c) and (d).

B.2: Gate Algebra

(a) Verify that $HXH = Z$ and $HZH = X$ by explicit matrix multiplication.

(b) Show that $H = \frac{1}{\sqrt{2}}(X + Z)$ and verify this identity.

(c) Express the SWAP gate as a product of three CNOTs and verify by computing the $4 \times 4$ matrix.

(d) Show that the controlled-Z gate is symmetric: $CZ_{12} = CZ_{21}$. Why is this not true for CNOT?

B.3: Bell State Circuits

(a) Starting from $|00\rangle$, trace through the circuit $H_1 \to \text{CNOT}_{12}$ step by step to derive $|\Phi^+\rangle$.

(b) What initial two-qubit state produces $|\Psi^-\rangle = \frac{1}{\sqrt{2}}(|01\rangle - |10\rangle)$ through the same circuit?

(c) Design a circuit (using only $H$, CNOT, $X$, and $Z$ gates) that transforms $|\Phi^+\rangle$ into $|\Psi^-\rangle$.

(d) The Bell measurement circuit runs the Bell preparation circuit in reverse: $\text{CNOT}_{12} \to H_1 \to$ measure both qubits. Show that the four Bell states $|\Phi^\pm\rangle$, $|\Psi^\pm\rangle$ produce the four outcomes $|00\rangle$, $|10\rangle$, $|01\rangle$, $|11\rangle$ respectively.

B.4: Toffoli and Classical Computation

(a) Write the $8 \times 8$ matrix of the Toffoli gate in the computational basis.

(b) Show that the Toffoli gate implements the AND function: if the target qubit starts in $|0\rangle$, the output is $|a, b, a \text{ AND } b\rangle$.

(c) Show that by fixing one input to $|1\rangle$, the Toffoli gate reduces to a CNOT gate. Which input do you fix?

(d) Argue that the set $\{\text{Toffoli}\}$ is universal for classical reversible computation.

B.5: Deutsch-Jozsa for $n = 2$

(a) List all possible balanced functions $f: \{0,1\}^2 \to \{0,1\}$.

(b) Choose the balanced function $f(00) = 0$, $f(01) = 1$, $f(10) = 1$, $f(11) = 0$. Write the phase oracle matrix $O_f = \text{diag}((-1)^{f(x)})$.

(c) Trace through the Deutsch-Jozsa circuit step by step and verify that the measurement outcome is not $|00\rangle$.

(d) Now choose the constant function $f(x) = 1$ for all $x$. Repeat the calculation and verify that the measurement outcome is $|00\rangle$.

B.6: Grover for $N = 8$

Consider $N = 8$ (3 qubits) with the marked item $w = |101\rangle$ (decimal 5).

(a) What is the initial amplitude of $|w\rangle$ in the uniform superposition? What is the initial success probability?

(b) Calculate the optimal number of Grover iterations using $k \approx \frac{\pi}{4}\sqrt{N}$.

(c) After one Grover iteration, compute the amplitude of $|w\rangle$ and the amplitude of each unmarked state. What is the success probability?

(d) After two iterations, what is the success probability? Compare with the optimal prediction.

(e) What happens after three iterations? Does the success probability increase or decrease?

B.7: QFT Matrix

(a) Write the $4 \times 4$ QFT matrix for $n = 2$ qubits. Express entries in terms of $\omega = e^{2\pi i/4} = i$.

(b) Verify that the QFT matrix is unitary: $\text{QFT}^\dagger \cdot \text{QFT} = I$.

(c) Apply the QFT to the state $|2\rangle = |10\rangle$ and express the result in the computational basis.

(d) The inverse QFT has matrix elements $(\text{QFT}^{-1})_{jk} = \frac{1}{\sqrt{N}}\omega^{-jk}$. Show that $\text{QFT}^{-1} = \text{QFT}^\dagger$.

Part C: Advanced Problems (⭐⭐⭐)

C.1: Universality of $\{H, T, \text{CNOT}\}$

(a) Show that $T^2 = S$ and $S^2 = Z$.

(b) Show that $HTH = R_x(\pi/4)$ (up to a global phase). Hint: Use $H\sigma_z H = \sigma_x$.

(c) Argue that $\{H, T\}$ can generate any single-qubit rotation to arbitrary precision. (You may invoke the Solovay-Kitaev theorem without proof.)

(d) Explain why adding CNOT to the set makes it universal for multi-qubit operations.

C.2: Quantum Teleportation — Full Derivation

Alice has an unknown qubit state $|\psi\rangle = \alpha|0\rangle + \beta|1\rangle$. She shares a Bell state $|\Phi^+\rangle = \frac{1}{\sqrt{2}}(|00\rangle + |11\rangle)$ with Bob.

(a) Write the full three-qubit state $|\psi\rangle_A \otimes |\Phi^+\rangle_{A'B}$.

(b) Rewrite this state in the Bell basis for the first two qubits (Alice's qubit and her half of the Bell pair). Show that:

$$|\psi\rangle_A |\Phi^+\rangle_{A'B} = \frac{1}{2}\left[|\Phi^+\rangle_{AA'}\otimes|\psi\rangle_B + |\Phi^-\rangle_{AA'}\otimes(Z|\psi\rangle)_B + |\Psi^+\rangle_{AA'}\otimes(X|\psi\rangle)_B + |\Psi^-\rangle_{AA'}\otimes(XZ|\psi\rangle)_B\right]$$

(c) After Alice measures her two qubits in the Bell basis, what correction does Bob apply for each of the four possible outcomes?

(d) Why can't teleportation be used for faster-than-light communication?

C.3: Grover with Multiple Marked Items

Suppose there are $M$ marked items out of $N$ total.

(a) Generalize the geometric analysis: define $\sin\theta_0 = \sqrt{M/N}$ and show that $k$ Grover iterations rotate the state by angle $(2k+1)\theta_0$.

(b) Derive the optimal number of iterations $k_{\text{opt}} = \lfloor \frac{\pi}{4\theta_0} \rfloor$.

(c) For $N = 64$ and $M = 4$, calculate $k_{\text{opt}}$ and the success probability.

(d) What happens as $M$ approaches $N/2$? When does Grover's algorithm offer no advantage?

C.4: Period Finding and Shor's Algorithm

Consider the function $f(x) = 7^x \bmod 15$.

(a) Compute $f(0), f(1), \ldots, f(7)$ and determine the period $r$.

(b) If $r$ is the period, compute $\gcd(7^{r/2} + 1, 15)$ and $\gcd(7^{r/2} - 1, 15)$. Do you obtain nontrivial factors of 15?

(c) Explain how the QFT would detect the period $r$ from the quantum state $\frac{1}{\sqrt{N}}\sum_x |x\rangle|f(x)\rangle$ after measuring the second register.

(d) Why does the classical step (computing GCDs) need to be done classically? What part of the algorithm requires a quantum computer?

C.5: Bit-Flip Error Correction Code

The 3-qubit bit-flip code encodes $|0\rangle_L = |000\rangle$ and $|1\rangle_L = |111\rangle$.

(a) Write the encoded state for $|\psi\rangle_L = \alpha|0\rangle_L + \beta|1\rangle_L$.

(b) If qubit 3 undergoes a bit flip ($X_3$), what is the resulting state?

(c) Compute the syndrome measurements: $\langle Z_1 Z_2 \rangle$ and $\langle Z_2 Z_3 \rangle$. Show that the syndrome uniquely identifies which qubit was flipped.

(d) Write the syndrome table for all four cases: no error, error on qubit 1, error on qubit 2, error on qubit 3.

(e) Explain why this code cannot correct phase errors. What additional encoding is needed?

C.6: Superdense Coding

Alice and Bob share the Bell state $|\Phi^+\rangle = \frac{1}{\sqrt{2}}(|00\rangle + |11\rangle)$.

(a) Alice applies one of $\{I, X, Z, XZ\}$ to her qubit. Show that the four resulting states are the four Bell states.

(b) Alice sends her qubit to Bob. Bob now has both qubits. Show that by measuring in the Bell basis, Bob can determine which of the four operations Alice applied.

(c) How many classical bits of information has Alice communicated by sending one qubit?

(d) Explain why this does not violate the Holevo bound (one qubit can carry at most 1 bit of accessible information). Hint: Consider the pre-shared entanglement as a resource.

C.7: Quantum Circuit Simulation

Using the code from code/example-01-circuits.py:

(a) Build a circuit that prepares the 4-qubit GHZ state $\frac{1}{\sqrt{2}}(|0000\rangle + |1111\rangle)$. Verify by examining the statevector and measurement statistics.

(b) Implement the Deutsch-Jozsa algorithm for $n = 4$ with the oracle $f(x) = x_1 \oplus x_3$ (XOR of bits 1 and 3). Verify that the algorithm correctly identifies $f$ as balanced.

(c) Run Grover's algorithm for $N = 32$ (5 qubits) with a marked item of your choice. Plot the success probability as a function of the number of iterations and identify the optimal iteration count.

(d) Implement the QFT on 4 qubits and verify that $\text{QFT}^{-1} \cdot \text{QFT} = I$ by applying QFT followed by inverse QFT and checking that the state returns to the input.

C.8: Hardware Comparison Analysis

Using the data from Section 25.9:

(a) Calculate the ratio of coherence time to two-qubit gate time for each of the three major platforms (superconducting, trapped ion, photonic). What does this ratio represent physically?

(b) If a quantum algorithm requires a circuit depth of 1000 two-qubit gates, which platform(s) can execute it within the coherence time?

(c) Estimate the number of physical qubits needed to create one logical qubit with an error rate of $10^{-10}$ using surface codes, assuming physical error rates of $10^{-3}$ (superconducting) and $10^{-4}$ (trapped ion). Use the rough scaling $n_{\text{phys}} \sim d^2$ where the code distance $d \sim \log(1/\epsilon_L)/\log(p_{\text{th}}/p_{\text{phys}})$.

(d) A practical quantum chemistry simulation might require 200 logical qubits and a circuit depth of $10^6$. Estimate the total physical qubit count and wall-clock time for superconducting and trapped ion platforms. Which is more practical, and why?

Part D: Challenge Problems (⭐⭐⭐⭐)

D.1: Proving Grover's Optimality

(a) Consider any quantum algorithm that makes $k$ queries to the oracle $O_f$. Show that after $k$ queries, the state can be written as $|\psi_k\rangle = \alpha_k|w\rangle + \beta_k|w^\perp\rangle$ where $|\alpha_k| \leq (2k+1)/\sqrt{N}$. Hint: Use the polynomial method or the geometric argument that each query rotates by at most $2\theta_0$.

(b) Conclude that any quantum search algorithm requires $\Omega(\sqrt{N})$ queries.

D.2: Simon's Algorithm

Simon's algorithm (1994) solves the following promise problem: given $f: \{0,1\}^n \to \{0,1\}^n$ with the promise that there exists $s \in \{0,1\}^n$ such that $f(x) = f(y)$ if and only if $x = y$ or $x = y \oplus s$, find $s$.

(a) Show that a classical algorithm requires $\Omega(2^{n/2})$ queries.

(b) Design a quantum circuit using $H^{\otimes n}$, $U_f$, and measurement that, with each run, produces a uniformly random $z$ satisfying $z \cdot s = 0$.

(c) How many runs are needed to determine $s$ with high probability?

(d) What is the query complexity of the quantum algorithm?

D.3: The Solovay-Kitaev Theorem (Sketch)

The theorem states: given a universal gate set $\mathcal{G}$ that generates a dense subgroup of $SU(2)$, any single-qubit gate $U \in SU(2)$ can be approximated to precision $\epsilon$ using $O(\log^c(1/\epsilon))$ gates from $\mathcal{G}$, where $c \approx 3.97$.

(a) Explain why the naive approach (random sequences of gates) would require $O(1/\epsilon^3)$ gates for precision $\epsilon$.

(b) The key idea is group-theoretic: approximate $U V^{-1}$ (where $V$ is a good existing approximation) using the identity $U V^{-1} = [A, B]$ for some $A, B$ that are themselves approximable. Explain why this recursive decomposition leads to a logarithmic dependence on $1/\epsilon$.

(c) Why is the Solovay-Kitaev theorem important for fault-tolerant quantum computation?

D.4: The No-Cloning Theorem and Quantum Money

(b) Stephen Wiesner proposed (1970s, published 1983) "quantum money" that cannot be counterfeited. The idea: a bank prepares qubits in states chosen randomly from $\{|0\rangle, |1\rangle, |+\rangle, |-\rangle\}$ and records the choices in a database. Explain why the no-cloning theorem prevents counterfeiting.

(c) What is the limitation of Wiesner's scheme that requires verification by the bank?