Chapter 40 Quiz: Capstone — Quantum Computing: From Qubits to Algorithms

Instructions: This quiz covers the core concepts from Chapter 40. For multiple choice, select the single best answer. For true/false, provide a brief justification (1-2 sentences). For short answer, aim for 3-5 sentences. For applied scenarios, show your work.

Multiple Choice (10 questions)

Q1. A statevector simulator for an $n$-qubit quantum computer stores the quantum state as a complex vector of dimension:

(a) $n$ (b) $2n$ (c) $n^2$ (d) $2^n$

Q2. The gate set $\{H, T, \text{CNOT}\}$ is called "universal" because:

(a) These are the only gates that can be physically implemented (b) Any unitary transformation can be exactly decomposed into a finite sequence of these gates (c) Any unitary transformation can be approximated to arbitrary precision using a finite sequence of these gates (d) They form the minimal set capable of creating any product state

Q3. Grover's algorithm searches an unsorted database of $N$ items using $O(\sqrt{N})$ oracle queries. If you apply more than the optimal number of iterations, the success probability:

(a) Continues to increase toward 1 (b) Stays constant at the maximum value (c) Decreases and then increases again in an oscillatory pattern (d) Drops to zero and stays there permanently

Q4. In the geometric picture of Grover's algorithm, each Grover iterate rotates the state by angle $2\theta$ in a 2D subspace. The angle $\theta$ is defined by:

(a) $\cos\theta = 1/N$ (b) $\sin\theta = 1/\sqrt{N}$ (c) $\tan\theta = 1/N$ (d) $\sin\theta = 1/N$

Q5. Quantum phase estimation with $t$ counting qubits estimates a phase $\varphi$ with a precision of:

(a) $\pm 1/t$ (b) $\pm 1/2^t$ (c) $\pm 1/\sqrt{2^t}$ (d) $\pm t/2^t$

Q6. Shor's factoring algorithm achieves its exponential speedup because:

(a) Grover's algorithm is used as a subroutine to search for factors (b) Quantum parallelism evaluates the modular exponentiation function on all inputs simultaneously (c) QPE efficiently extracts the period of the modular exponentiation function, and factoring reduces to period finding (d) Quantum entanglement allows direct comparison of all candidate factors

Q7. In the 3-qubit bit-flip code, syndrome measurement:

(a) Reveals both the error location and the encoded logical state (b) Reveals the error location without disturbing the encoded logical state (c) Collapses the logical superposition but identifies the error (d) Projects the state onto the code space without identifying the error

Q8. The surface code is the leading candidate for fault-tolerant quantum computing primarily because:

(a) It uses the fewest physical qubits per logical qubit (b) It has the highest threshold error rate and requires only nearest-neighbor interactions (c) It can correct any number of errors, regardless of code distance (d) It does not require ancilla qubits for syndrome measurement

Q9. As of 2025, which hardware platform achieves the highest quantum volume despite having relatively few qubits?

(a) Superconducting transmons (b) Trapped ions (c) Photonic qubits (d) Neutral atoms

Q10. The term "NISQ" (Noisy Intermediate-Scale Quantum) describes devices with:

(a) 1-10 qubits and no errors (b) 50-1000+ qubits without error correction, suitable for short-depth circuits (c) Millions of qubits with full error correction (d) Classical computers that simulate quantum circuits

True/False (4 questions)

Q11. True or False: The Quantum Fourier Transform (QFT) can efficiently compute the Fourier transform of a classical data vector stored in a quantum register, and the result can be read out directly.

Q12. True or False: Grover's algorithm can solve NP-complete problems in polynomial time.

Q13. True or False: Quantum error correction protects quantum information by making copies of the quantum state across multiple physical qubits.

Q14. True or False: A topological qubit, if realized, would achieve fault tolerance through the global topological properties of its encoding, providing inherent hardware-level protection against local noise.

Short Answer (4 questions)

Q15. Explain the distinction between "quantum advantage" (sometimes called "quantum supremacy") and "quantum utility." Give one claimed experimental example of each as of 2025.

Q16. Why can the CNOT gate create entanglement in some cases but not others? Describe precisely the condition on the input state that determines whether the output will be entangled.

Q17. The surface code requires roughly 1,000 physical qubits per logical qubit. Explain why this overhead does not negate the exponential speedup of Shor's algorithm.

Q18. Explain what the "harvest now, decrypt later" threat is and why it makes the transition to post-quantum cryptography urgent even though fault-tolerant quantum computers are years away.

Applied Scenarios (2 questions)

Q19. A quantum chemistry lab wants to simulate a molecule with 40 orbitals using the Jordan-Wigner encoding (1 qubit per orbital).

(a) How many logical qubits are needed?

(b) If the surface code with distance $d = 11$ requires $\sim 241$ physical qubits per logical qubit, how many total physical qubits are needed?

(c) The simulation circuit has depth 10,000. Each logical gate cycle takes $\sim 1\,\mu$s. How long does the computation take?

(d) If the current largest quantum computer has $\sim 1,000$ qubits, how many doublings of qubit count are needed? At one doubling every 2 years, when might this become feasible?

Q20. You are running Grover's algorithm on a 12-qubit quantum computer ($N = 4096$ items) with a device that has a two-qubit gate error rate of $0.3\%$.

(a) How many Grover iterations are optimal?

(b) Each Grover iteration requires approximately 30 two-qubit gates. What is the total number of two-qubit gates for the full algorithm?

(c) Assuming independent errors, what is the probability that no error occurs during the entire computation?

(d) Is the algorithm likely to succeed without error correction? What error rate would be needed for $> 90\%$ probability of no error?

Answer Key

Q1: (d) — The state of $n$ qubits is a vector in $\mathbb{C}^{2^n}$, requiring $2^n$ complex amplitudes.

Q2: (c) — The Solovay-Kitaev theorem guarantees that $\{H, T, \text{CNOT}\}$ can approximate any $n$-qubit unitary to arbitrary precision. Exact decomposition is not generally possible because the Clifford+T group generates a dense (but not equal to) subgroup of $SU(2^n)$.

Q3: (c) — The state rotates past the target state in the geometric picture and continues to oscillate. The success probability is periodic with period $\sim \pi\sqrt{N}/2$ iterations.

Q4: (b) — The initial overlap is $\langle w | s \rangle = 1/\sqrt{N}$, so $\sin\theta = 1/\sqrt{N}$.

Q5: (b) — With $t$ counting qubits, the phase space $[0, 1)$ is divided into $2^t$ bins of width $1/2^t$, giving precision $\pm 1/2^t$.

Q6: (c) — Shor's algorithm reduces factoring to period finding (a classical reduction) and then uses QPE to find the period efficiently. The quantum speedup is in the QPE step, not in parallel evaluation of all inputs (which is a common but misleading description).

Q7: (b) — The syndrome measurement is designed to detect the error pattern without collapsing the encoded superposition, because the syndrome operators commute with the logical operators.

Q8: (b) — The surface code's threshold of $\sim 1\%$ is among the highest known, and its requirement for only nearest-neighbor gates on a 2D lattice matches the connectivity of superconducting and other solid-state qubit platforms.

Q9: (b) — Trapped-ion systems (e.g., Quantinuum H2) achieve quantum volume $2^{20}$ with only $\sim 56$ qubits, far exceeding superconducting devices with many more qubits, due to superior gate fidelities and all-to-all connectivity.

Q10: (b) — NISQ refers to current-generation devices: enough qubits for non-trivial computations, but too noisy for deep circuits or full error correction.

Q11: False. The QFT transforms quantum amplitudes, which cannot be directly observed. You can prepare the QFT of a quantum state, but reading out all $2^t$ Fourier coefficients would require exponentially many measurements (one outcome per shot). The QFT's value lies in enabling algorithms that exploit Fourier structure before measurement.

Q12: False. Grover's algorithm gives a quadratic speedup: $O(2^{n/2})$ instead of $O(2^n)$. This is still exponential in $n$ and does not place NP-complete problems in polynomial time. The complexity class BQP (problems efficiently solvable on a quantum computer) is not believed to contain NP.

Q13: False. The no-cloning theorem forbids copying quantum states. Quantum error correction encodes the logical information into an entangled subspace of multiple physical qubits. The information is spread across the qubits through entanglement, not duplicated.

Q14: True. The encoded information is a property of the global topological state (e.g., braiding history of non-Abelian anyons), which is immune to local perturbations. The error rate is exponentially suppressed in the physical separation of the anyons.

Q15: Quantum advantage refers to solving a well-defined computational task faster than any classical computer can, with evidence of classical intractability. Example: Google's 2019 random circuit sampling on Sycamore (200 seconds vs. "10,000 years" classically, though disputed). Quantum utility refers to using a quantum computer to produce scientifically or commercially useful results, without necessarily proving classical intractability. Example: IBM's 2023 simulation of a transverse-field Ising model on the 127-qubit Eagle processor, producing physics results in a regime where classical methods struggled.

Q16: CNOT creates entanglement when the control qubit is in a superposition of $|0\rangle$ and $|1\rangle$. Specifically, $\text{CNOT}((\alpha|0\rangle + \beta|1\rangle) \otimes |0\rangle) = \alpha|00\rangle + \beta|11\rangle$, which is entangled if both $\alpha \neq 0$ and $\beta \neq 0$. If the control qubit is a definite basis state, CNOT produces a product state (e.g., $\text{CNOT}(|0\rangle \otimes |0\rangle) = |00\rangle$).

Q17: Error correction adds polynomial overhead: $O(d^2)$ physical qubits per logical qubit and constant-factor slowdown per logical gate. Shor's algorithm has polynomial runtime $O(n^3)$ in the number of digits. Polynomial times polynomial is still polynomial — the exponential advantage over the classical $O(\exp(cn^{1/3}(\log n)^{2/3}))$ is preserved.

Q18: An adversary can record encrypted communications today — storing ciphertext that they cannot yet decrypt. Once a fault-tolerant quantum computer is available (perhaps 10-15 years from now), they could decrypt all stored data retroactively. Sensitive information (state secrets, medical records, financial data) that must remain confidential for decades is therefore already at risk if transmitted using RSA or ECC encryption. This motivates deploying post-quantum cryptography now.

Q19: (a) 40 logical qubits. (b) $40 \times 241 = 9{,}640$ physical qubits. (c) $10{,}000 \times 1\,\mu\text{s} = 10$ ms (well within coherence times for error-corrected systems). (d) Need $\lceil\log_2(9{,}640/1{,}000)\rceil \approx \lceil 3.27 \rceil = 4$ doublings, so $\sim 8$ years — roughly 2033. This is among the more optimistic but not unreasonable scenarios.

Q20: (a) $k_{\text{opt}} = \lfloor \pi\sqrt{4096}/4 \rfloor = \lfloor \pi \cdot 64/4 \rfloor = \lfloor 50.3 \rfloor = 50$ iterations. (b) $50 \times 30 = 1{,}500$ two-qubit gates. (c) $(1 - 0.003)^{1500} = 0.997^{1500} \approx e^{-4.5} \approx 0.011$, so about 1.1% chance of no error. (d) The algorithm will almost certainly fail without error correction — there is a 99% chance of at least one error. For $> 90\%$ no-error probability: $(1-p)^{1500} > 0.9 \Rightarrow p < 1 - 0.9^{1/1500} \approx 7 \times 10^{-5}$, or $0.007\%$ — about 40 times better than the assumed 0.3%.