Self-Assessment Quiz: Why Quantum Computing?

Twenty questions on complexity classes, where quantum speedups come from, what they do not cover, and how to read a quantum-advantage claim. Answer each before opening the key. Aim for 16+.

Question 1

A quantum computer's advantage over a classical one comes from:

A) Trying every possible answer simultaneously and reading them all out B) Superposition, entanglement, and interference arranging amplitudes so wrong answers cancel C) Running the same classical algorithm at a higher clock speed D) Storing exponentially more classical bits per unit volume

Question 2

The complexity class of problems a quantum computer can solve efficiently with bounded error is:

A) NP B) BQP C) PSPACE D) BPP

Question 3

Which statement about BQP and NP is correct as of today?

A) NP $\subseteq$ BQP is proven B) BQP $\subseteq$ NP is proven C) Neither containment is known D) They are known to be equal

Question 4

Shor's algorithm factors an $n$-bit integer in time polynomial in $n$. Its most direct consequence is:

A) All encryption becomes impossible B) RSA and Diffie–Hellman become breakable, while symmetric ciphers are only weakened C) AES-256 becomes trivially breakable D) Hash functions are no longer collision-resistant

Question 5

Grover's algorithm searches an unstructured space of $N$ items in roughly:

A) $\log N$ queries B) $\sqrt{N}$ queries C) $N/2$ queries D) constant queries

Question 6

For $N = 10^{12}$, Grover reduces the query count to about:

A) $10^3$ B) $10^6$ C) $10^9$ D) $10^{11}$

Question 7

Grover's quadratic speedup is proven optimal for unstructured search. This means:

A) No quantum algorithm can beat $\Theta(\sqrt{N})$ queries without exploiting problem structure B) No classical algorithm can beat $\Theta(N)$ C) Grover will eventually be improved to $\log N$ D) The bound holds only for $N < 2^{40}$

Question 8

Which task should you expect no meaningful quantum speedup for?

A) Simulating molecular ground-state energies B) Factoring a 2048-bit RSA modulus C) Sorting a large database by a key, or serving web requests D) Estimating eigenvalues of a sparse Hamiltonian

Question 9

Feynman's 1981 argument for quantum computers was essentially that:

A) Classical computers would soon stop getting faster B) Simulating quantum systems classically costs resources exponential in particle count C) Cryptography needed a new foundation D) Transistors were approaching atomic scale

Question 10

"Quantum supremacy" / "quantum advantage" experiments demonstrate:

A) A useful commercial application running faster than classical hardware B) A specific, often contrived, task performed faster than the best known classical simulation C) That BQP $\ne$ BPP has been proven D) That error correction is no longer necessary

Question 11

Google's 2019 Sycamore result was disputed primarily because:

A) The device did not actually have 53 qubits B) Improved classical simulation algorithms narrowed or erased the claimed gap C) The random-circuit-sampling task was later shown to be in P D) The measurements were not reproducible

Question 12

NISQ stands for:

A) Non-Interacting Stabilizer Qubits B) Noisy Intermediate-Scale Quantum C) Networked Ion-Sequenced Qubits D) Non-Ideal Superconducting Qubits

Question 13

The single biggest obstacle between today's machines and cryptographically relevant factoring is:

A) Insufficient clock speed B) The number of error-corrected logical qubits, which requires orders of magnitude more physical qubits C) A lack of suitable programming languages D) Insufficient classical memory to store the output

Question 14

Current estimates put the physical-qubit cost of factoring a 2048-bit RSA integer at roughly:

A) Thousands B) Tens of thousands C) Millions D) Trillions

Question 15

"Harvest now, decrypt later" describes:

A) A quantum error-correction strategy B) Recording encrypted traffic today to decrypt once quantum computers mature C) A method of extracting more shots from a noisy device D) Caching circuit compilations between runs

Question 16

True or false: A quantum computer can solve NP-complete problems in polynomial time.

Question 17

True or false: The exponential size of an $n$-qubit state space ($2^n$ amplitudes) by itself guarantees an exponential speedup.

Question 18

True or false: Symmetric cryptography is unaffected by quantum computing.

Question 19

Short answer. A vendor claims their 100-qubit machine "outperforms a supercomputer." List three questions you would ask before accepting the claim.

Question 20

Short answer. Explain, in two sentences, why "quantum computers try all answers at once" is a misleading description of quantum parallelism.

Answer Key

Q Ans Note
1 B Superposition creates the branches; interference is what makes the useful ones survive measurement. Without interference there is no advantage.
2 B BQP: bounded-error quantum polynomial time.
3 C Neither BQP $\subseteq$ NP nor NP $\subseteq$ BQP is known. BQP $\subseteq$ PSPACE is known.
4 B Shor breaks factoring and discrete log, so RSA, DH, and ECC fall. Grover only halves the effective key length of symmetric ciphers.
5 B $\approx \frac{\pi}{4}\sqrt{N}$ queries.
6 B $\sqrt{10^{12}} = 10^6$.
7 A The BBBV lower bound. Structure (as in Shor) is what buys exponential speedups; unstructured search cannot do better than quadratic.
8 C General-purpose data processing, I/O-bound work, and sorting see no asymptotic quantum benefit.
9 B Simulating $n$ interacting quantum particles needs $\sim 2^n$ classical amplitudes — hence "make the simulator quantum."
10 B The tasks are chosen to be hard classically, not to be useful. That is a legitimate scientific milestone and not a product.
11 B IBM and later groups showed tensor-network and related methods cut the classical time dramatically. The result stands as a milestone; the headline margin did not.
12 B Preskill's 2018 term for the current era: hundreds to thousands of noisy, uncorrected qubits.
13 B Logical qubits, not physical ones, are the currency. Surface-code overhead is roughly $10^3$ physical per logical at current error rates.
14 C Gidney and Ekerå's widely cited estimate is ~20 million noisy physical qubits for an 8-hour factorization.
15 B The reason post-quantum migration is urgent now for long-lived secrets, even though no machine can break RSA today.
16 False No such algorithm is known, and most researchers doubt one exists. Quantum speedups exploit structure; NP-completeness is precisely the absence of exploitable structure.
17 False State-space size is necessary but nowhere near sufficient — you must extract a classical answer, and measurement collapses the state. Interference is what converts amplitude into a readable answer.
18 False "Unaffected" is too strong. Grover gives a quadratic speedup on key search, so AES-128 has ~64 bits of quantum security. Doubling key length restores the margin, which is why AES-256 is the recommendation rather than abandoning symmetric crypto.
19 — Reasonable questions: outperforms at what specific task? (contrived sampling vs. useful workload); compared against which classical algorithm (best known, or a naive one?); are the qubits error-corrected, and what is the two-qubit gate fidelity and circuit depth?; is the result peer-reviewed and reproducible?; does the advantage survive better classical algorithms?
20 — The state does hold $2^n$ amplitudes, but measurement returns exactly one $n$-bit string, sampled from those amplitudes. The algorithm's job is to arrange interference so the desired string has large amplitude before you measure; "trying everything at once" describes the first half and silently skips the half that actually matters.