Quiz: The First Quantum Algorithms

Answers with explanations at the end.

1. State the three-step pattern shared by every algorithm in this chapter, and say which step has no classical analogue.

2. Write the amplitude of outcome $y$ after the three steps, and explain what determines whether it adds up or cancels.

3. For Deutsch–Jozsa, what is $P(\text{all zeros})$ for a constant function? For a balanced one? Are these approximate or exact?

4. Show why a balanced $f$ gives amplitude exactly 0 on the all-zeros outcome.

5. How many queries does Deutsch–Jozsa need, and what is the classical worst case? Give the numbers at $n = 50$.

6. Is the Deutsch–Jozsa advantage best explained as "evaluating $f$ on all $2^n$ inputs at once"? Explain.

7. What does Bernstein–Vazirani's oracle look like, and why does the measured bitstring equal the secret?

8. Bernstein–Vazirani goes from $n$ queries to 1. Is this an exponential speedup?

9. State Simon's promise and Simon's question.

10. What does a single Simon measurement give you? How many distinct outcomes are possible?

11. Why is one Simon measurement insufficient, unlike Deutsch–Jozsa and Bernstein–Vazirani?

12. What is the classical query complexity of Simon's problem, and what bounds it?

13. An implementation takes exactly $n-1$ Simon measurements and solves the resulting system. What fraction of runs succeed at large $n$, and why?

14. Why is 0…0 always a valid Simon measurement, and why is it never useful?

15. State the correct stopping condition for collecting Simon measurements, and confirm the query complexity is still $O(n)$.

16. Name the quantum and classical halves of Simon's, Shor's, and VQE. What is the common structure?

17. What is a promise problem? Give the promise for each of the three algorithms in this chapter.

18. A Deutsch–Jozsa run on an oracle marking one input out of sixteen gives $P(\text{all zeros}) = 0.759$. What does the standard decision rule conclude, and is it right?

19. How can you detect a violated promise from the output, and why does the standard rule miss it?

20. Why can't Deutsch–Jozsa verify its own promise? What follows about whose responsibility it is?

Answers

1. Superpose ($H^{\otimes n}$ on the input register), query (the phase oracle), interfere ($H^{\otimes n}$ again). Step 3 — interference — has no classical analogue. Evaluating $f$ on a superposition is easy and useless on its own (Chapter 19 §19.2); making the $2^n$ answers combine is the mechanism.

2. $\displaystyle \frac{1}{2^n}\sum_x (-1)^{f(x) + x\cdot y}$. It is a sum of $\pm1$ terms, and whether they add or cancel is determined entirely by the structure of $f$ — which is why each algorithm assumes a different structure and reads off a different thing.

3. Exactly 1 for constant, exactly 0 for balanced. Exact, not approximate — measured as 1.000 and 0.000 at $n = 3, 4, 5$. A single shot suffices and the answer is certain.

4. The $y = 0$ amplitude is $\frac{1}{2^n}\sum_x (-1)^{f(x)}$. A balanced $f$ is 0 on exactly half the inputs and 1 on the other half, so the sum contains $2^{n-1}$ terms of $+1$ and $2^{n-1}$ of $-1$, which cancel exactly.

5. One query quantum; $2^{n-1}+1$ classical in the worst case — one more than half, since seeing $2^{n-1}$ identical values still leaves both possibilities open. At $n = 50$: 562,949,953,421,313 versus 1.

6. No. That is the popular explanation and it is wrong: Chapter 19 §19.2 measured that computing $f$ on a superposition is trivial and completely useless, because the answer sits in a register where it cannot interfere. The advantage is in step 3 — the Hadamard layer computes a sum over all $2^n$ inputs into a single amplitude, and "is that sum zero?" is a global property. The measurement returns one bitstring, not $2^n$ answers.

7. A CX from input qubit $i$ onto the scratch qubit whenever $s_i = 1$. With the scratch in $|-\rangle$, each such CX kicks back a phase $(-1)^{x_i}$, so the register acquires the phase $(-1)^{s\cdot x}$ — and $H^{\otimes n}$ applied to that state gives exactly $|s\rangle$.

8. No — it is linear. $n$ queries to 1 is a hundredfold improvement at $n = 100$, which is a constant-factor-flavoured win rather than a change in complexity class. The historically important result is the recursive version's super-polynomial separation.

9. Promise: $f$ is two-to-one with a hidden period $s \neq 0$, so $f(x) = f(y) \iff y = x \oplus s$. Question: what is $s$?

10. A uniformly random $y$ satisfying $y \cdot s = 0 \pmod 2$ — one linear equation in the bits of $s$. There are $2^{n-1}$ such strings, and measurement produces exactly those (verified: 4 distinct outcomes at $n=3$, 8 at $n=4$).

11. Because one equation does not determine $s$. You need $n-1$ linearly independent equations to pin the solution space down to one dimension. Deutsch–Jozsa and Bernstein–Vazirani each extract their full answer in a single deterministic outcome; Simon's outcomes are random and partial.

12. $\Theta(2^{n/2})$. Classically you must find a collision — two inputs with the same output — and the birthday bound puts that at the square root of the domain size.

13. About 29% at large $n$. The measurements are uniformly random over an $(n-1)$-dimensional space, and the probability that $n-1$ random draws are linearly independent is $\prod_{k=1}^{n-1}(1-2^{-k}) \approx 0.2888$. It presents as intermittent failure, which is the hardest mode to diagnose.

14. It satisfies $y \cdot s = 0$ for every $s$, so it is always a legitimate measurement — and it contributes the equation $0 = 0$, which constrains nothing. Counting it consumes one of your slots and adds no rank.

15. Collect until the rank reaches $n-1$, discarding 0…0 and any vector linearly dependent on those already held. The expected number of shots is $n - 1 + O(1)$, so the $O(n)$ query complexity is unchanged — the fix is to the stopping condition, not the complexity.

16. Simon: sample $y$ with $y\cdot s = 0$ / Gaussian elimination over $\mathbb{F}_2$. Shor: sample a phase / continued fractions then GCD. VQE: evaluate an expectation value / the entire classical optimizer. Common structure: the quantum subroutine produces constraints, and classical computation turns constraints into answers.

17. A problem whose input is guaranteed to have a specific structure, with behaviour on inputs lacking it left undefined. Deutsch–Jozsa: $f$ is constant or balanced. Bernstein–Vazirani: $f(x) = s\cdot x$. Simon: $f$ is two-to-one with period $s$.

18. The standard rule — all zeros means constant, anything else means balanced — concludes BALANCED. It is wrong: the function is neither constant nor balanced, so it is outside the algorithm's domain entirely. There is no error, no warning, and no flag.

19. Count the distinct outcomes. Both valid promises produce exactly one: constant gives all-zeros with probability 1, balanced gives the single defining mask with probability 1. A violation produces a spread — at $n=4$, all sixteen outcomes, 76% on all-zeros plus a long thin tail. The standard rule misses it because it collapses the histogram to one scalar and then applies a two-branch rule to a three-case world. Add the third branch.

20. Because verifying the promise requires examining $f$ on exponentially many inputs — which is precisely the cost the algorithm exists to avoid. A one-query algorithm cannot afford an exponential precondition check. The promise is therefore imported from outside, and its correctness is the caller's responsibility — established by a test harness at small $n$, or by a structural argument about where $f$ came from.