Chapter 25 Quiz: Quantum Information and Computation

Contributors to Quantum Mechanics: From Wavefunctions to Qubits

Chapter 25 Quiz: Quantum Information and Computation

Instructions: This quiz covers the core concepts from Chapter 25. 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 qubit in the state $|\psi\rangle = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$ is measured in the computational basis. What are the possible outcomes and their probabilities?

Q2. The Hadamard gate applied to $|0\rangle$ produces $|+\rangle = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$. What does the Hadamard gate applied to $|1\rangle$ produce?

(a) $|+\rangle = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$ (b) $|-\rangle = \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)$ (c) $|1\rangle$ (d) $i|+\rangle$

Q3. What is the primary entangling gate in quantum computation?

(a) Hadamard gate (b) CNOT gate (c) Toffoli gate (d) Phase gate $S$

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

(a) These are the only quantum gates that exist (b) Any classical computation can be performed with these gates (c) Any unitary operation on $n$ qubits can be approximated to arbitrary precision using only these gates (d) These gates are the easiest to implement on hardware

Q5. In the Deutsch-Jozsa algorithm, the key quantum advantage comes from:

(a) Quantum parallelism — evaluating $f(x)$ for all $x$ simultaneously (b) Quantum interference — constructive/destructive interference of amplitudes reveals a global property of $f$ (c) Quantum entanglement between the input and output registers (d) The ability to clone quantum states

Q6. Grover's search algorithm achieves a speedup of:

(a) Exponential: $O(\log N)$ queries instead of $O(N)$ (b) Quadratic: $O(\sqrt{N})$ queries instead of $O(N)$ (c) Polynomial: $O(N^{1/3})$ queries instead of $O(N)$ (d) Constant: $O(1)$ queries instead of $O(N)$

Q7. In Grover's algorithm, the diffusion operator $D = 2|s\rangle\langle s| - I$ performs which geometric operation?

(a) Rotation by $\pi$ about $|0\rangle$ (b) Rotation by $\pi/2$ about $|s\rangle$ (c) Reflection about the uniform superposition $|s\rangle$ (d) Projection onto the marked state $|w\rangle$

Q8. Shor's algorithm factors large integers efficiently using:

(a) Grover's search to find factors by brute force (b) The quantum Fourier transform to find the period of $a^x \bmod N$ (c) Quantum annealing to minimize a cost function (d) Entanglement between all possible factor pairs

Q9. In quantum error correction, the no-cloning theorem is circumvented by:

(a) Approximately cloning the state, which is good enough for error correction (b) Encoding the logical qubit in entangled states of multiple physical qubits and measuring syndromes that reveal error type without measuring the encoded state (c) Using classical error correction on the measurement outcomes (d) Accepting that quantum error correction is impossible in practice

Q10. Which quantum hardware platform currently leads in two-qubit gate fidelity (as of 2025)?

(a) Superconducting qubits (b) Trapped ion qubits (c) Photonic qubits (d) Neutral atom qubits

True/False (4 questions)

Q11. True or False: A quantum computer with $n$ qubits can solve any problem $2^n$ times faster than a classical computer.

Q12. True or False: The quantum Fourier transform can be implemented with $O(n^2)$ gates, which is exponentially faster than the classical FFT's $O(N \log N)$ operations (where $N = 2^n$).

Q13. True or False: If you apply Grover's algorithm for more than the optimal number of iterations, the success probability will continue to increase.

Q14. True or False: The Toffoli gate is universal for quantum computation by itself (without any additional gates).

Short Answer (5 questions)

Q15. Explain the difference between a qubit and a classical bit. Your answer should mention superposition, the Bloch sphere, and measurement.

Q16. What is "phase kickback" and why is it important? Describe the mechanism using the oracle $U_f|x\rangle|-\rangle = (-1)^{f(x)}|x\rangle|-\rangle$.

Q17. Why is Grover's quadratic speedup important in practice, even though it is "only" quadratic rather than exponential? Give two examples of real problems where a quadratic speedup would be significant.

Q18. Describe the three main challenges that make quantum error correction seem impossible, and briefly explain how each is overcome.

Q19. Compare the three major quantum hardware platforms (superconducting, trapped ion, photonic) in terms of their key strengths and weaknesses. Which platform would you choose for (a) a quantum computer requiring the most qubits and (b) a quantum computer requiring the highest gate fidelity?

Applied Scenarios (3 questions)

Q20. You are given the following quantum circuit acting on two qubits initialized to $|00\rangle$:

$$|00\rangle \xrightarrow{H_1} \xrightarrow{\text{CNOT}_{12}} \xrightarrow{Z_2} \xrightarrow{\text{CNOT}_{12}} \xrightarrow{H_1}$$

(a) Trace through the circuit step by step, writing the state after each gate. (b) What is the final state? (c) What is the probability of measuring $|00\rangle$? Of measuring $|11\rangle$?

Q21. A company claims their 100-qubit quantum computer can break RSA-2048 encryption. Evaluate this claim using what you know from this chapter.

(a) How many logical qubits does Shor's algorithm require for RSA-2048? (b) How many physical qubits per logical qubit are needed, given current error rates? (c) Is the company's claim credible? Justify your answer quantitatively.

Q22. You need to search an unsorted database of 1,000,000 entries for a specific item.

(a) How many queries does a classical search require on average? (b) How many queries does Grover's algorithm require? (c) If each query takes 1 microsecond, how long does each approach take? (d) How many qubits are needed to implement Grover's algorithm for this database? (e) Is this a realistic near-term application of quantum computing? Why or why not?

Answer Key

Q1: (a). The Born rule gives $P(|0\rangle) = |1/\sqrt{2}|^2 = 1/2$ and $P(|1\rangle) = |1/\sqrt{2}|^2 = 1/2$.

Q2: (b). $H|1\rangle = \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle) = |-\rangle$. The relative phase distinguishes $|+\rangle$ from $|-\rangle$.

Q3: (b). CNOT is the standard two-qubit entangling gate. Applied to $|+\rangle|0\rangle$, it creates the Bell state $|\Phi^+\rangle$.

Q4: (c). Universality means any $n$-qubit unitary can be approximated to arbitrary precision. The Solovay-Kitaev theorem guarantees efficient approximation.

Q5: (b). While quantum parallelism (evaluating $f$ in superposition) is necessary, the speedup comes from interference. The Hadamard transforms before and after the oracle create constructive interference at the correct answer.

Q6: (b). Grover achieves $O(\sqrt{N})$, a quadratic speedup. This is provably optimal for unstructured search.

Q8: (b). Shor reduces factoring to period finding, then uses the QFT to extract the period from the quantum state.

Q9: (b). Quantum error correction encodes information in entanglement and measures syndromes (parities) that reveal error locations without disturbing the encoded state.

Q10: (b). Trapped ion systems (e.g., Quantinuum H2) achieve $>99.8\%$ two-qubit gate fidelity, the highest among current platforms.

Q11: False. Quantum computers provide speedups only for specific, structured problems. For most computational tasks, they offer no advantage. The speedup depends on problem structure, not just hardware.

Q12: True. The QFT on $n$ qubits uses $O(n^2)$ gates, while the classical FFT on a vector of length $N = 2^n$ uses $O(N\log N) = O(n \cdot 2^n)$ operations. The quantum version is exponentially faster in the number of gates — but note the QFT transforms amplitudes, not a classically accessible vector.

Q13: False. Grover's algorithm is periodic: the success probability oscillates as a function of iteration count. Exceeding the optimal $k \approx \frac{\pi}{4}\sqrt{N}$ causes the state to rotate past the target, decreasing the success probability.

Q14: False. The Toffoli gate is universal for classical reversible computation but not for quantum computation. It cannot generate superpositions (it maps computational basis states to computational basis states). Adding the Hadamard gate makes $\{H, \text{Toffoli}\}$ universal for quantum computation.

Q15: A classical bit is in one definite state: 0 or 1. A qubit $|\psi\rangle = \alpha|0\rangle + \beta|1\rangle$ can be in a superposition, parametrized by two angles on the Bloch sphere. The key difference is that the qubit's state space is continuous (the surface of the Bloch sphere), while a classical bit has only two states. Upon measurement, the qubit collapses to $|0\rangle$ or $|1\rangle$ with probabilities $|\alpha|^2$ and $|\beta|^2$, destroying the superposition.

Q16: Phase kickback occurs when the oracle acts on the input register $|x\rangle$ with an ancilla prepared in $|-\rangle$: $U_f|x\rangle|-\rangle = (-1)^{f(x)}|x\rangle|-\rangle$. The function value $f(x)$ is "kicked back" as a phase on the input register, while the ancilla is unchanged. This converts the function evaluation into a phase, enabling interference. It is the mechanism underlying both Deutsch-Jozsa and Grover.

Q17: A quadratic speedup turns $O(N)$ into $O(\sqrt{N})$, which for large $N$ is substantial. For $N = 10^{18}$ (e.g., a cryptographic key space), classical search takes $\sim 10^{18}$ steps while Grover takes $\sim 10^9$ steps — the difference between billions of years and seconds. Examples: (1) breaking symmetric cryptographic keys (AES-128: $2^{128} \to 2^{64}$), (2) combinatorial optimization where the classical approach involves brute-force enumeration.

Q18: (1) No-cloning theorem: overcome by encoding in entangled states rather than copying. (2) Continuous errors: any error on a single qubit can be decomposed into a linear combination of $I$, $X$, $Y$, $Z$, so correcting these discrete errors suffices. (3) Measurement destroys the state: syndrome measurements detect errors without measuring the encoded state, by measuring only correlations (parities) between physical qubits.

Q19: Superconducting: fastest gates, most qubits, but short coherence times and requires extreme cooling. Trapped ion: highest fidelity, all-to-all connectivity, but slower gates and harder to scale. Photonic: room temperature, natural for networking, but difficult two-photon gates. (a) Most qubits: superconducting (already $>1000$). (b) Highest fidelity: trapped ion ($>99.8\%$).

Q20: (a) Step-by-step: $|00\rangle \xrightarrow{H_1} \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)|0\rangle \xrightarrow{\text{CNOT}} \frac{1}{\sqrt{2}}(|00\rangle + |11\rangle) \xrightarrow{Z_2} \frac{1}{\sqrt{2}}(|00\rangle - |11\rangle) = |\Phi^-\rangle \xrightarrow{\text{CNOT}} \frac{1}{\sqrt{2}}(|00\rangle - |10\rangle) \xrightarrow{H_1} |0\rangle|0\rangle - |0\rangle|0\rangle$... Let us recalculate carefully. After the second CNOT: $\frac{1}{\sqrt{2}}(|00\rangle - |10\rangle) = \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)|0\rangle = |-\rangle|0\rangle$. After $H_1$: $H|-\rangle|0\rangle = |1\rangle|0\rangle = |10\rangle$. (b) Final state: $|10\rangle$. (c) $P(|00\rangle) = 0$, $P(|11\rangle) = 0$, $P(|10\rangle) = 1$.

Q21: (a) Shor requires roughly 4,000-20,000 logical qubits for 2048-bit RSA. (b) With current error rates (~$10^{-3}$), each logical qubit requires roughly 1,000-10,000 physical qubits. (c) Total physical qubits needed: 4 million to 200 million. A 100-qubit machine is approximately 40,000-2,000,000 times too small. The claim is not credible.

Q22: (a) Classical: $N/2 = 500{,}000$ queries on average. (b) Grover: $\frac{\pi}{4}\sqrt{10^6} \approx 785$ queries. (c) Classical: 0.5 seconds. Grover: 0.785 milliseconds. (d) $n = \lceil\log_2(10^6)\rceil = 20$ qubits. (e) While 20 qubits is well within current capabilities, the bottleneck is the oracle implementation and circuit depth. Loading a classical database into a quantum oracle is typically as expensive as the classical search itself, limiting practical applicability. Grover's advantage is most significant when the oracle represents a computation (e.g., verifying a cryptographic hash) rather than a database lookup.