Exercises: Chapter 1 — Why Quantum Computing? What Quantum Computers Can Do That Classical Computers Can't (and What They Can't Do Better)

Exercise 1.1: Complexity Classes

Classify each problem into P, NP (but not known to be in P), or BQP (with exponential quantum speedup): (a) Multiplying two $n$-digit integers. (b) Factoring an $n$-bit integer. (c) Determining if a Boolean formula is satisfiable. (d) Simulating the time evolution of a 50-spin quantum system. (e) Finding the shortest path in a weighted graph. (f) Computing the discrete logarithm $g^x \equiv h \pmod{p}$. (g) Sorting a list of $n$ numbers. (h) Finding a collision in a 2-to-1 function on $n$ bits.

Exercise 1.2: Exponential State Space

A classical register of $n$ bits can store one of $2^n$ values. A quantum register of $n$ qubits can be in a superposition of all $2^n$ basis states. Explain why this does not mean a quantum computer can solve arbitrary search problems in one step. What is the role of measurement? What is the maximum classical information that can be extracted from an $n$-qubit state with a single measurement?

Exercise 1.3: Grover's Speedup

Grover's algorithm searches an unstructured database of $N$ items in $O(\sqrt{N})$ quantum operations. If $N = 1,000,000$, approximately how many operations does Grover's algorithm require? How does this compare to classical search? Is this an exponential speedup? Why or why not?

Exercise 1.4: The No-Cloning Theorem

The no-cloning theorem states that an arbitrary unknown quantum state cannot be perfectly copied. Why is this a fundamental limitation for quantum computing? How does it affect error correction strategies? Contrast this with classical error correction, where making backup copies is the standard approach.

Exercise 1.5: NISQ Applications

Research one proposed NISQ-era application (variational quantum eigensolver, quantum approximate optimization algorithm, quantum machine learning). Write a one-paragraph summary of what problem it addresses and why it might work on near-term noisy devices.

Exercise 1.6: Interference Calculation

Starting from state $|0\rangle$, apply a Hadamard gate to get $|+\rangle$, then apply a Z gate (which flips the sign of $|1\rangle$), then apply another Hadamard gate. Calculate the final state step by step, showing how interference leads to the result. What state do you end up in? What would happen if you replaced the Z gate with an X gate instead?

Exercise 1.7: Classical Simulation Cost

Estimate the amount of memory required to store the state vector of a quantum computer with $n$ qubits, assuming each amplitude requires 16 bytes (128 bits for a complex number). Create a table for $n = 10, 20, 30, 40, 50, 60$. At what point does this exceed the total memory of the world's largest supercomputer (approximately 10 petabytes)?

Exercise 1.8: BQP vs BPP

Explain in your own words why oracle separations (like Simon's problem) provide evidence that BQP is strictly larger than BPP, but do not constitute a proof. What would a proof require? Why is this difficult?

Exercise 1.9: Quantum Supremacy Debate

Google claimed quantum supremacy in 2019 with their Sycamore processor. IBM disputed the claim, arguing that with better classical algorithms, the task could be done in 2.5 days rather than 10,000 years. Research this debate and explain: (a) why the specific task chosen (random circuit sampling) was important for proving supremacy, and (b) why the debate about classical simulation time doesn't invalidate the achievement.

Exercise 1.10: Error Correction Overhead

If a quantum computer has physical qubits with error rate $p = 10^{-3}$, and the surface code requires a code distance of $d = 2\lceil \log(1/\epsilon)/\log(1/p) \rceil + 1$ to achieve logical error rate $\epsilon$, calculate the code distance needed for $\epsilon = 10^{-12}$. How many physical qubits per logical qubit does this require? If Shor's algorithm needs 2,000 logical qubits, how many physical qubits are needed?