Self-Assessment Quiz: Quantum Parallelism and Interference

Twenty questions on where quantum speedup actually comes from: superposition, phase kickback, interference, and the limits imposed by measurement. Aim for 16+.

Question 1

Applying $H^{\otimes n}$ to $|0\rangle^{\otimes n}$ produces:

A) $|1\rangle^{\otimes n}$ B) An equal superposition of all $2^n$ basis states C) An entangled state D) A random basis state

Question 2

Evaluating $f$ on that superposition gives $\sum_x |x\rangle|f(x)\rangle$. Measuring immediately yields:

A) All $2^n$ values of $f$ B) One random pair $(x, f(x))$ C) The value of $f$ at $x=0$ D) Nothing

Question 3

Therefore quantum parallelism by itself provides:

A) Exponential speedup B) No advantage over classical random sampling C) Quadratic speedup D) Certainty

Question 4

The ingredient that converts parallelism into advantage is:

A) Entanglement alone B) Interference — arranging amplitudes so wrong answers cancel C) More qubits D) Faster gates

Question 5

Phase kickback occurs when:

A) A controlled-$U$ acts on an eigenstate of $U$, transferring $U$'s eigenphase to the control B) A gate is measured C) Two qubits are swapped D) A qubit decoheres

Question 6

For $U|\psi\rangle = e^{i\theta}|\psi\rangle$, controlled-$U$ with control $|+\rangle$ produces control state:

A) $|+\rangle$ B) $\frac{1}{\sqrt2}(|0\rangle + e^{i\theta}|1\rangle)$ C) $|-\rangle$ D) $|0\rangle$

Question 7

The oracle $U_f|x\rangle|y\rangle = |x\rangle|y \oplus f(x)\rangle$ with the target in $|-\rangle$ gives:

A) $(-1)^{f(x)}|x\rangle|-\rangle$ B) $|x\rangle|+\rangle$ C) $|f(x)\rangle|-\rangle$ D) No change

Question 8

That trick is called:

A) Phase kickback / phase oracle conversion B) Uncomputation C) Amplitude damping D) Teleportation

Question 9

Constructive interference means amplitudes:

A) Cancel B) Add in phase, increasing probability C) Are measured D) Decohere

Question 10

Destructive interference requires:

A) Entanglement B) Amplitudes of opposite sign (or phase) meeting on the same basis state C) Measurement D) At least 3 qubits

Question 11

Interference requires the state to be:

A) Mixed B) Coherent (pure, with well-defined relative phases) C) Classical D) Measured

Question 12

A quantum algorithm's final Hadamard layer typically serves to:

A) Reset the qubits B) Convert phase information into measurable amplitude C) Entangle the register D) Correct errors

Question 13

Which classical resource can reproduce quantum interference?

A) Randomness B) Probabilistic sampling C) None — probabilities are non-negative and cannot cancel D) Parallel processors

Question 14

The Holevo bound implies that from $n$ qubits you can extract at most:

A) $2^n$ classical bits B) $n$ classical bits C) $n^2$ bits D) Unlimited

Question 15

An algorithm that queries an oracle in superposition but never interferes:

A) Still gets exponential speedup B) Is equivalent to classical random guessing C) Fails to run D) Is faster by $\sqrt N$

Question 16

True or false: A quantum computer "tries all answers simultaneously."

Question 17

True or false: Interference can increase the probability of the right answer above the classical guess rate without any additional queries.

Question 18

True or false: Decoherence destroys the ability to interfere.

Question 19

Short answer. Explain why the $|-\rangle$ target state converts a bit-flip oracle into a phase oracle, showing the algebra.

Question 20

Short answer. A colleague proposes computing $f$ on all $2^{50}$ inputs in superposition and then "reading off the maximum." What is wrong with this?

Answer Key

Q Ans Note
1 B The uniform superposition, the starting point of nearly every quantum algorithm.
2 B Measurement samples one branch. The other $2^n - 1$ evaluations are inaccessible.
3 B Sampling one random input-output pair is exactly what a classical machine does by picking $x$ at random.
4 B Interference is the mechanism; superposition merely sets it up.
5 A The eigenphase moves from the target register onto the control's relative phase.
6 B The $|1\rangle$ branch acquires $e^{i\theta}$, converting a global phase on the target into a relative phase on the control — which is measurable.
7 A $|-\rangle$ is the $-1$ eigenstate of $X$, so the conditional flip becomes a conditional sign.
8 A Used in Deutsch–Jozsa, Bernstein–Vazirani, Grover's oracle, and phase estimation.
9 B Same-phase amplitudes add.
10 B Opposite phases cancel — impossible for classical probabilities, which never subtract.
11 B Coherence is the prerequisite; this is why uncomputation (Ch. 7) and low decoherence matter so much.
12 B The final $H^{\otimes n}$ converts phases installed by the oracle into amplitude differences the Born rule can see.
13 C Probabilities are non-negative, so classical mixtures cannot cancel. Amplitudes are complex and can. This is the sharpest statement of what makes quantum different.
14 B $n$ qubits yield at most $n$ classical bits of accessible information.
15 B Without interference the algorithm is a randomized classical sampler wearing a quantum costume.
16 False It evaluates in superposition but returns one sampled outcome. The phrase describes the setup and omits the mechanism that matters.
17 True Deutsch–Jozsa does exactly this: one query, certainty, where classical needs exponentially many. The information came from interference, not from extra queries.
18 True Decoherence randomizes relative phases, so amplitudes no longer combine predictably — the state becomes a classical mixture.
19 — $|-\rangle = (|0\rangle - |1\rangle)/\sqrt2$. Then $|y \oplus f(x)\rangle$ maps $|0\rangle - |1\rangle$ to $|f(x)\rangle - |1\oplus f(x)\rangle$. If $f(x)=0$ this is unchanged; if $f(x)=1$ it is $|1\rangle - |0\rangle = -(|0\rangle - |1\rangle)$. So the target is unchanged up to a factor $(-1)^{f(x)}$, which attaches to $|x\rangle$: $U_f|x\rangle|-\rangle = (-1)^{f(x)}|x\rangle|-\rangle$.
20 — There is no "reading off." Measurement returns a single basis state sampled with probability $|\text{amplitude}|^2$, and after evaluating $f$ in superposition every $x$ has amplitude $2^{-25}$ — the maximizing $x$ is no more likely than any other. Finding a maximum requires an algorithm that concentrates amplitude on it, e.g. Grover-based maximum finding, which costs $O(\sqrt{2^{50}}) \approx 3\times10^{7}$ queries — a quadratic speedup, not the free lunch proposed.