Chapter 20 — Key Takeaways (The First Quantum Algorithms)

Four algorithms, one pattern, one promise. §20.5 is the part that generalizes.

★ The shared three-step pattern

   1. SUPERPOSE   H on every input qubit  ->  uniform over 2^n inputs
   2. QUERY       the phase oracle        ->  f(x) into the phase
   3. INTERFERE   H on every input qubit  ->  amplitudes combine

$$|0\rangle^{\otimes n} \xrightarrow{H^{\otimes n}} \frac{1}{\sqrt{2^n}}\sum_x |x\rangle \xrightarrow{O_f} \frac{1}{\sqrt{2^n}}\sum_x (-1)^{f(x)}|x\rangle \xrightarrow{H^{\otimes n}} \sum_y \left[\frac{1}{2^n}\sum_x (-1)^{f(x)+x\cdot y}\right]|y\rangle$$

The bracketed sum is everything — whether $\pm1$ terms add or cancel depends on the structure of $f$. Step 3 has no classical analogue.

Deutsch–Jozsa

Promise: $f$ is constant or balanced. Question: which?

   n=3 constant0   P(all zeros) = 1.000   -> CONSTANT
   n=3 balanced    P(all zeros) = 0.000   -> BALANCED
   n=5 constant1   P(all zeros) = 1.000   -> CONSTANT
   n=5 balanced    P(all zeros) = 0.000   -> BALANCED

Exactly 1 and exactly 0 — one shot suffices, the answer is certain.

Constant → $(-1)^{f(x)}$ is a global sign, so $H^{\otimes n}$ returns the register to $|0\dots0\rangle$. Balanced → the $y=0$ amplitude is $\frac{1}{2^n}\sum_x(-1)^{f(x)} = 0$ exactly.

    n     classical worst case     quantum
    3                        5           1
   20                  524,289           1
   50      562,949,953,421,313           1

⚛️ The advantage is NOT "evaluating $f$ on all inputs at once" — Ch. 19 §19.2 measured that as easy and useless. It is step 3: the Hadamard layer computes a sum over all $2^n$ inputs into a single amplitude. "Is $\sum_x(-1)^{f(x)}$ zero?" is a global property, and interference evaluates global properties without examining terms. The measurement returns one bitstring.

Bernstein–Vazirani

Promise: $f(x) = s\cdot x \bmod 2$. Question: what is $s$?

   n=4  secret=1011      measured=1011      1000/1000
   n=6  secret=101101    measured=101101    1000/1000
   n=8  secret=11010110  measured=11010110  1000/1000

Every shot exactly right, no post-processing at all. The oracle is a CX from each qubit $i$ with $s_i=1$; after $H^{\otimes n}$ the measured string is $s$.

🔬 The speedup is $n \to 1$ — LINEAR, not exponential. The classical bound is provable (each query returns one bit; you need $n$). The problem is not one anyone has. Its historical weight is the recursive version's super-polynomial separation — the first evidence quantum might be more than polynomially faster.

Simon's algorithm — the first exponential separation

Promise: two-to-one with $f(x)=f(y) \iff y = x\oplus s$. Question: what is $s$?

Each measurement returns a random $y$ with $y\cdot s = 0 \pmod 2$:

   n=3, s=110:  4 distinct outcomes (= 2^(n-1))   all satisfy y·s=0 ✓
   n=4, s=1011: 8 distinct outcomes (= 2^(n-1))   all satisfy y·s=0 ✓

    n   classical ~2^(n/2)   quantum O(n)
   20                1,024             20
   40            1,048,576             40
   80        1.1 x 10^12               80

Classically you need a collision, and the birthday bound puts that at $\Theta(2^{n/2})$.

★★ Half the algorithm is classical

Each measurement is one linear equation in the bits of $s$. Collect $n-1$ independent ones and solve over $\mathbb{F}_2$; the null space is one-dimensional and its nonzero vector is $s$.

⚠️ CHECK THE RANK, NOT THE SHOT COUNT. Measurements are uniformly random over the $2^{n-1}$ orthogonal strings. 0…0 is always valid and always useless, and $n-1$ random vectors span an $(n-1)$-dimensional space only about 29% of the time: $$\prod_{k=1}^{n-1}(1-2^{-k}) \approx 0.2888$$ A fixed-shot implementation fails intermittently — flakiness, the hardest failure mode to diagnose. Expected shots with rank-checking: $n-1+O(1)$, so $O(n)$ survives.

The structure recurs everywhere:

The quantum subroutine produces constraints; classical computation turns constraints into answers.

★★★ The promise

All four are promise problems: the input is guaranteed to have a structure, and behaviour without it is undefined.

   oracle                              P(all zeros)    standard rule
   constant (promise holds)                  1.0000         CONSTANT
   balanced (promise holds)                  0.0000         BALANCED
   marks ONE input (promise BROKEN)          0.7590         BALANCED   <- WRONG

No error. No warning. An answer.

But the distribution knows

   constant           1 outcome     {'0000': 2000}
   balanced           1 outcome     {'0110': 2000}
   promise broken    16 outcomes    {'0000': 1518, '0110': 40, '1111': 37, ...}

Both valid promises give exactly ONE outcome. A violation gives a spread — 76% plus a long thin tail. Add the third branch:

if   p_all_zeros > 0.99:   verdict = "constant"
elif p_all_zeros < 0.01:   verdict = "balanced"
else:                      verdict = "PROMISE VIOLATED"      # <- the missing one

The algorithm cannot verify its own promise — verification means examining $f$ on exponentially many inputs, which is exactly the cost it exists to avoid. The precondition is imported from outside, and its correctness is the caller's responsibility.

Ch. 12 §12.6's lesson again: read the distribution, not the scalar you reduced it to. There, four missing outcomes named a stuck qubit; here, a long tail names a broken assumption.

🔬 How much do these tell us?

The theorems are real — Deutsch–Jozsa's separation is exact and provable; Simon's exponential separation is foundational.

And the problems were constructed to exhibit them. Nobody needs to distinguish constant from balanced functions. These are existence proofs, not applications — demonstrations that the query-complexity gap is nonzero, built by people who needed that established first. A genuine contribution, and a different claim from "quantum computers are exponentially faster."

Simon's is the exception that justifies the exercise. Its hidden-subgroup structure — quantum sampling plus classical linear algebra — is exactly Shor's. A toy problem that led directly to the most consequential quantum algorithm known.

Common pitfalls

• Applying an algorithm to a function that violates its promise.
• Using a two-branch decision rule on a three-case world.
• Collapsing the histogram to a scalar and losing the diagnosis.
• Taking $n-1$ shots instead of collecting to rank $n-1$.
• Counting 0…0 as a useful equation.
• Treating the classical post-processing as an afterthought.
• Reading "one query vs $2^{n-1}$" as a general statement about quantum speed.

Project piece added this chapter

vqelab/algorithms.py — deutsch_jozsa() (with the PROMISE VIOLATED branch and a distinct_outcomes count), bernstein_vazirani(), simon() (collects to rank, reports redundant_shots), solve_f2(), and check_promise() (brute-force, exponential — what a harness can afford and the algorithm cannot). 14 tests pass, including test_the_standard_two_way_rule_would_have_been_wrong and test_every_simon_measurement_is_orthogonal_to_the_period.