Exercises: Chapter 32 — Quantum Hype vs. Quantum Reality

Exercise 32.1: Myth Detection

Find three recent news articles or press releases about quantum computing. For each, identify: (a) any factual errors or misleading statements, (b) any claims that conflate theoretical possibility with near-term practicality, and (c) what a more accurate version of the article would say. Write a 300-word analysis for each.

Exercise 32.2: Complexity Class Boundaries

Prove that if there existed a quantum algorithm that could solve 3-SAT in polynomial time, then $\mathsf{NP} \subseteq \mathsf{BQP}$. Explain why most complexity theorists believe this is unlikely. What would be the implications for cryptography if it were true?

Exercise 32.3: NISQ vs. Fault-Tolerant Analysis

Choose a quantum algorithm (Shor's, Grover's, VQE, or QAOA). Estimate the number of physical qubits and circuit depth required to solve a practically interesting instance of the problem (e.g., factoring RSA-2048, searching a database of $2^{64}$ entries, simulating FeMoco). Determine whether the algorithm is feasible on NISQ devices, early fault-tolerant devices (100-1,000 logical qubits), or only mature fault-tolerant devices (10,000+ logical qubits). Justify your answer with quantitative estimates.

Exercise 32.4: The Quantum Winter Scenario

Write a 500-word scenario describing a "quantum winter" — a period of reduced funding and interest in quantum computing. What events could trigger it? How would it affect different stakeholders (researchers, startups, investors, governments)? What would be the long-term consequences for the field? Then write a 500-word counter-scenario describing how the field could avoid this outcome.

Exercise 32.5: Quantum Literacy for Executives

You have been asked to give a 10-minute briefing to the C-suite of a Fortune 500 company about quantum computing. Prepare a one-page executive summary that addresses: (a) what quantum computing is (in one paragraph, without jargon), (b) what it means for their industry (pick one: finance, pharmaceuticals, energy, or logistics), (c) what they should do now (specific, actionable recommendations), and (d) what they should not worry about (myths to ignore). The summary must be accurate, honest about limitations, and useful for decision-making.

Exercise 32.6: Grover's Algorithm Performance Calculation

A database has $N = 2^{30} \approx 10^9$ entries. (a) How many queries does classical search require on average? (b) How many queries does Grover's algorithm require? (c) If each query takes 1 microsecond, what are the total search times? (d) Now suppose the database is sorted and you can use binary search. How does this compare to Grover's algorithm? What does this tell you about when quantum search is actually useful?

Exercise 32.7: Resource Estimation for Quantum Chemistry

Using the formula for qubit count after Jordan-Wigner transformation ($n_{\text{qubits}} = n_{\text{spin-orbitals}}$) and the T-gate count estimates from Lee et al. (2021), estimate the resources needed to compute the ground state energy of: (a) H$_2$ (4 qubits), (b) LiH (12 qubits), (c) H$_2$O (14 qubits), (d) FeMoco active space (108 qubits). For each, state whether it's feasible on current NISQ hardware, near-term fault-tolerant hardware, or requires mature fault-tolerant hardware.

Exercise 32.8: Error Mitigation vs. Error Correction

Implement a VQE calculation for H$_2$ in Qiskit. Compare: (a) ideal simulation, (b) simulation with a depolarizing noise model (1% two-qubit gate error), (c) simulation with error mitigation (zero-noise extrapolation at noise levels 1×, 2×, 3×), (d) simulation with error mitigation and readout error mitigation. Report the energy error for each case. At what noise level does error mitigation stop being effective?

Exercise 32.9: Quantum Advantage Threshold Analysis

For each of the following applications, estimate the "quantum advantage threshold" — the minimum number of qubits and circuit depth needed to outperform the best classical algorithm: (a) factoring RSA-2048, (b) simulating a 50-electron molecule to chemical accuracy (1.6 mHartree), (c) solving MaxCut on a 1000-node graph, (d) training a machine learning model on the MNIST dataset. For each, state whether current quantum hardware can achieve this threshold and, if not, when you expect it to be achievable.

Exercise 32.10: Hype Analysis Portfolio

Create a "quantum hype tracker" — a document where you record five quantum computing claims from the past year, with your analysis of each using the seven-point checklist from Section 32.7. Update this document quarterly. Over time, you will develop a calibrated sense of which claims are credible and which are hype.