Chapter 20: The First Quantum Algorithms

"They are exact, they are provably faster, and every one of them solves a problem someone invented so that they would."

Overview

Chapter 19 built the oracle. This chapter uses it, four times, in the algorithms that first demonstrated quantum computers can do something classical computers cannot.

All four are exact: no sampling error, no approximation, no repetition-until-confident. Measured:

  Deutsch–Jozsa,  n=5, constant:   P(all zeros) = 1.000
  Deutsch–Jozsa,  n=5, balanced:   P(all zeros) = 0.000
  Bernstein–Vazirani, n=8:         secret recovered on 1000 of 1000 shots

And the separations are real. Deutsch–Jozsa at $n = 50$:

$$\text{classical worst case: } 562{,}949{,}953{,}421{,}313 \text{ queries} \qquad \text{quantum: } \mathbf{1}$$

Simon's algorithm goes further — it is the first exponential separation, and it is the direct ancestor of Shor's (Chapter 23).

Then the honest part, which is this chapter's real content.

Every one of these algorithms solves a promise problem. You are promised the function is constant or balanced, promised it has the linear form $f(x) = s \cdot x$, promised it is two-to-one with a hidden period. The algorithms exploit that structure, and they cannot verify it.

Hand Deutsch–Jozsa a function that is neither constant nor balanced:

  P(all zeros) = 0.7590
  Deutsch–Jozsa reports: BALANCED        <- confidently wrong

No error. No warning. An answer.

In this chapter, you will learn to:

• Implement all three algorithms and verify them exactly.
• See the shared three-step pattern they instantiate.
• Solve Simon's linear system over $\mathbb{F}_2$.
• Explain what a promise problem is.
• Recognize a violated promise from the output distribution.

Learning Paths

How to read this chapter by track. - 🔰 Beginner — §20.2 and §20.3. Bernstein–Vazirani is the most satisfying circuit in the book. - 🔬 Researcher — §20.5 and §20.6; the promise structure is what every later algorithm inherits. - 🤖 Quantum ML — skim; §20.6's pattern recurs in kernel methods. - 🏗️ Quantum Engineer — §20.4's post-processing is the half nobody implements carefully. - 🔐 Security — §20.4 and §20.6, then straight to Chapter 23; Simon's is Shor's in miniature.

20.1 The Shared Pattern

All three algorithms are the same three steps. Learn the pattern and the individual algorithms become variations.

   1. SUPERPOSE      H on every input qubit  ->  uniform over all 2^n inputs
   2. QUERY          the phase oracle        ->  f(x) written 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 quantity is everything. It is a sum of $\pm1$ terms, and whether it adds up or cancels depends on the structure of $f$. The algorithms differ only in what structure they assume and what they read off the result.

Step 3 is the part that has no classical analogue. Computing $f$ on a superposition is easy (Chapter 19 §19.2); what makes these algorithms work is that the second Hadamard layer makes the $2^n$ answers interfere, so that global information about $f$ concentrates into a few outcomes.

The bracketed quantity, derived

The whole chapter runs on one line of algebra. For a single qubit,

$$H|b\rangle = \tfrac{1}{\sqrt2}\left(|0\rangle + (-1)^{b}|1\rangle\right) = \frac{1}{\sqrt2}\sum_{c \in \{0,1\}} (-1)^{bc}|c\rangle$$

Tensor $n$ copies. The exponents add, so the signs multiply:

$$H^{\otimes n}|x\rangle = \frac{1}{\sqrt{2^n}}\sum_{y \in \{0,1\}^n} (-1)^{x\cdot y}|y\rangle, \qquad x\cdot y \equiv \sum_{i=1}^{n} x_i y_i \pmod 2$$

That is the entire mechanism. Applied to $|0\rangle^{\otimes n}$ it gives every $x$ the sign $(-1)^{0} = +1$ — the uniform superposition of step 1. Applied a second time, to $\frac{1}{\sqrt{2^n}}\sum_x(-1)^{f(x)}|x\rangle$, it gives

$$\frac{1}{\sqrt{2^n}}\sum_x (-1)^{f(x)} \cdot \frac{1}{\sqrt{2^n}}\sum_y (-1)^{x\cdot y}|y\rangle = \sum_y \underbrace{\left[\frac{1}{2^n}\sum_x (-1)^{f(x)+x\cdot y}\right]}_{\hat F(y)}|y\rangle$$

which is the formula above with the bracket named. $\hat F(y)$ is the Walsh–Hadamard transform of the sign function $F(x) = (-1)^{f(x)}$, and the measured probability is $P(y) = \hat F(y)^2$.

One identity does all the work in the three sections that follow. The sum factorizes across bit positions, so

$$\sum_{x \in \{0,1\}^n} (-1)^{x\cdot z} = \prod_{i=1}^{n}\left(1 + (-1)^{z_i}\right) = \begin{cases} 2^n & z = 0\\ 0 & z \neq 0\end{cases}$$

A single 1 anywhere in $z$ contributes a factor $1 + (-1) = 0$ and kills the whole product. Every exact result in this chapter is that fact wearing a different hat.

📐 Math Aside — $H^{\otimes n}$ is a Fourier transform, which is why Chapter 22 will look familiar.

The identity above is the orthogonality relation for the characters of the group $(\mathbb{Z}_2)^n$. The functions $\chi_y(x) = (-1)^{x\cdot y}$ are that group's characters, they are orthogonal, and expanding a function in them is a Fourier transform.

So $H^{\otimes n}$ is the quantum Fourier transform over $(\mathbb{Z}_2)^n$ — the same object Chapter 22 §22.1 builds over $\mathbb{Z}_{2^n}$, with the group swapped. The reason Chapter 22's circuit is full of controlled phase rotations while this one is bare Hadamards is that $\mathbb{Z}_{2^n}$'s characters are $e^{2\pi i xy/2^n}$ — complex roots of unity, needing genuine rotations — while $(\mathbb{Z}_2)^n$'s are $\pm1$, needing none.

This is not an analogy; it is the same construction. Deutsch–Jozsa, Bernstein–Vazirani and Simon's algorithm are the hidden-subgroup problem over $(\mathbb{Z}_2)^n$; Shor's (Chapter 23) is the hidden-subgroup problem over $\mathbb{Z}_N$. Everything here is Chapter 23 with an easier group — which is also why the algebra here is exact and Chapter 23's is not. $+1$ and $-1$ cancel perfectly; $e^{2\pi i k/2^n}$ does not, which is where Chapter 23's continued fractions come from.

Parseval falls out for free: $\sum_y \hat F(y)^2 = \frac{1}{2^n}\sum_x F(x)^2 = 1$, since $F(x) = \pm1$. The probabilities sum to one for algebraic reasons, which is a useful check when you are computing amplitudes by hand and want to know whether you dropped a term.

Why a phase oracle and not a bit oracle

Chapter 19 built both. This chapter uses only one, and the reason is visible in the formula.

The bit oracle computes $U_f|x\rangle|y\rangle = |x\rangle|y\oplus f(x)\rangle$. Run it on a superposition with the scratch qubit in $|0\rangle$ and you get

$$\frac{1}{\sqrt{2^n}}\sum_x |x\rangle\,|f(x)\rangle$$

and then the second Hadamard layer does nothing useful, because the input register is now entangled with the scratch qubit. Different $x$ values carry different scratch states, so their amplitudes cannot cancel: interference between two branches requires that everything outside the interfering register agree, and here it does not.

Chapter 19 §19.2 measured what that leaves you with — a measurement returning one uniformly random $(x, f(x))$ pair. One evaluation, chosen for you at random, which is strictly worse than choosing $x$ yourself.

The phase oracle fixes exactly this. Putting the scratch qubit in $|-\rangle$ makes it an eigenvector of the $X$ that $U_f$ conditionally applies, so the scratch state factors out:

$$U_f\left(|x\rangle|-\rangle\right) = (-1)^{f(x)}|x\rangle|-\rangle$$

The scratch qubit ends unentangled and the answer is in the phase. Chapter 19 §19.3 verified the amplitude ratio as exactly $+1$ where $f = 0$ and exactly $-1$ where $f = 1$, and vqelab/oracles.py asserts the scratch qubit is unentangled afterwards — because the failure is otherwise invisible. An un-uncomputed ancilla leaves the input register mixed, the interference silently stops working, and the circuit still runs and still returns bitstrings.

A phase is a thing amplitudes can cancel; a bit in another register is not. That single sentence is why all three algorithms in this chapter begin by putting a qubit in $|-\rangle$.

20.2 Deutsch–Jozsa

The promise: $f: \{0,1\}^n \to \{0,1\}$ is either constant (same value for every input) or balanced (0 on exactly half the inputs, 1 on the other half). It is guaranteed to be one of these.

The question: which?

Classically, in the worst case you must check $2^{n-1} + 1$ inputs — one more than half, since seeing $2^{n-1}$ identical values still leaves both possibilities open.

Quantum: one query. Substitute into §20.1's formula. If $f$ is constant, $(-1)^{f(x)}$ is a global sign, and the second Hadamard layer returns the register exactly to $|0\rangle^{\otimes n}$. If $f$ is balanced, the $y = 0$ amplitude is

$$\frac{1}{2^n}\sum_x (-1)^{f(x)} = 0$$

because the $+1$ and $-1$ terms cancel exactly.

$$\boxed{\;P(\text{all zeros}) = 1 \text{ if constant}, \quad 0 \text{ if balanced}\;}$$

Measured, 1000 shots each:

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

Exactly 1 and exactly 0. Not approximately — a single shot suffices, and the answer is certain.

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

⚛️ The Physics Underneath — where the exponential advantage actually comes from.

It is tempting to say the quantum computer "evaluated $f$ on all $2^n$ inputs at once." That statement is popular, and it is the wrong explanation — Chapter 19 §19.2 measured that evaluating $f$ on a superposition is trivially easy and completely useless on its own.

The advantage comes from step 3. The Hadamard layer computes a sum over all $2^n$ inputs and deposits it in a single amplitude. The question "is $\sum_x (-1)^{f(x)}$ zero or not?" is a global property of $f$, and interference is a mechanism for evaluating global properties without examining the terms individually.

The measurement returns one bitstring, not $2^n$ answers. What you get is one global fact, which happens to be the fact you asked for — because the problem was chosen so that it would be.

Constant and balanced, term by term

The two outcomes above are worth computing, because the shape of each answer is the point.

Constant $f$. Write $f(x) = c$ for every $x$. Then $(-1)^{f(x)} = (-1)^c$ pulls out of the sum, and §20.1's identity finishes it:

$$\hat F(y) = \frac{1}{2^n}\sum_x (-1)^{c + x\cdot y} = \frac{(-1)^c}{2^n}\sum_x (-1)^{x\cdot y} = (-1)^c\,\delta_{y,0}$$

Every amplitude except $y = 0$ is exactly zero, and the $y = 0$ amplitude is $\pm1$. The global sign $(-1)^c$ is unobservable — which is why constant-0 and constant-1 are indistinguishable here, and why the algorithm reports constant rather than which constant. The measured table shows both returning 1.000, and that is not a coincidence; it is the same state up to a phase.

Balanced $f$. Only $y = 0$ matters, and the sum is a count:

$$\hat F(0) = \frac{1}{2^n}\sum_x (-1)^{f(x)} = \frac{1}{2^n}\Big(\underbrace{2^{n-1}}_{f=0}(+1) + \underbrace{2^{n-1}}_{f=1}(-1)\Big) = 0$$

Exactly zero, by counting. Not small — zero, because "balanced" is precisely the statement that the $+1$ and $-1$ terms arrive in equal numbers. That is why the measured column reads 0.000 and not 0.003: there is no approximation anywhere in the argument, so there is nothing for a finite shot count to blur.

And that is the whole algorithm. One shot decides it because the two cases put probability 1 and probability 0 on the same outcome, and no amount of sampling is required to tell 1 from 0.

📐 Math Aside — the classical bound is a bound on exact algorithms, and that is a much weaker statement than it reads as.

$2^{n-1}+1$ is the worst case for a classical algorithm that must be always right. Allow it to be wrong with small probability and the problem collapses.

Query $k$ distinct inputs at random. If any two answers differ, $f$ is balanced — certainly, no error possible. If all $k$ agree, answer constant. A constant $f$ is then never misclassified. A balanced $f$ fools you only if all $k$ draws landed in the same half, which for $2^n \gg k$ has probability

$$2\prod_{i=0}^{k-1}\frac{2^{n-1}-i}{2^{n}-i} \;\longrightarrow\; 2\cdot 2^{-k} = 2^{-(k-1)}$$

text k queries P(a balanced f fools you) 2 5.000e-01 5 6.250e-02 10 1.953e-03 21 9.537e-07 41 9.095e-13

Twenty-one queries put the error below one in a million — at every $n$. Forty-one put it below $10^{-12}$, which is smaller than the probability that the hardware running the quantum version returns a wrong answer.

So the bounded-error classical query complexity of Deutsch–Jozsa is $O(1)$, not $2^{n-1}+1$. The exponential separation exists only against classical algorithms forbidden to make mistakes — and quantum computers make mistakes constantly (see this chapter's noise report in §20.5).

This does not make the theorem wrong. Deutsch–Jozsa was built to exhibit an exact separation, it does, and in 1992 that was the point. It makes the theorem narrower than "exponentially faster" implies, in exactly the way Chapter 19 §19.7 warned. Simon's algorithm is the one that survives this objection — its $\Theta(2^{n/2})$ classical bound holds for randomized algorithms too — and that is a large part of why it, and not Deutsch–Jozsa, is Shor's ancestor.

📊 What the Numbers Say — the 562-trillion column and the 1 column count different things.

Both columns are labelled "queries," and that label hides three substitutions.

Column one counts evaluations of a cheap classical function; column two counts invocations of a reversible quantum circuit implementing the same function. Chapter 19 §19.5 measured the gap: an 8-input marked-state oracle is 26,978 T gates without ancillas and 55 with six of them. One quantum query is not one classical evaluation, and at $n = 50$ it is not close.

Column one is a worst case; column two is exact. The classical worst case requires an adversary handing the algorithm the least helpful $2^{n-1}$ inputs first. The average case is far better, and the bounded-error case is $O(1)$.

Neither column counts building the oracle. To run Deutsch–Jozsa you must already possess a circuit for $f$ — and if you possess a circuit for $f$ you can read it. A classical algorithm allowed to inspect $f$ rather than only query it is not bound by column one at all.

The correct reading is: in the query model, against an exact classical algorithm, with the oracle supplied free, the gap is exponential. Four qualifications, all real, and the theorem is true with every one of them attached.

⚙️ Under the Transpiler — the query in the measured runs is free, and that is not an accident.

example-01-deutsch-jozsa.py builds its balanced oracle as $f(x) = m\cdot x$ — one CX per set bit of the mask. Transpiled to Clifford+T (basis h x cx t tdg s sdg z, optimization_level=1, Qiskit 2.5.1, seed_transpiler=42):

text balanced-by-parity oracle n cx T depth 3 2 0 5 4 2 0 5 5 3 0 6 8 5 0 8

Zero T gates. Depth under ten. And the cx count is the popcount of the mask, not $n$ — it does not grow with the problem size at all, only with how many bits the secret happens to set.

The same Deutsch–Jozsa circuit with a general oracle — Chapter 19's marked-set construction, one input flagged, no ancillas — measured under the identical settings:

text single-marked-input oracle n cx T depth 3 14 1,905 3,912 4 36 2,605 4,762 6 124 11,998 22,582 8 252 26,950 43,733

Same algorithm, same query count. Totalling every gate in the transpiled circuit, $n = 8$ gives 17 gates for the parity oracle against 68,927 for the general one — a factor of 4,054. The T count reproduces Chapter 19 §19.5's 26,978 to within 0.1%; the small difference is the synthesis path taken through the surrounding Hadamard and X layers, not a disagreement.

The oracle is cheap because the promise made it cheap. A parity is the most structured balanced function there is. §20.5 works out what a generic balanced function costs, and the answer is not comfortable.

20.3 Bernstein–Vazirani

The promise: $f(x) = s \cdot x \bmod 2$ for some hidden $n$-bit string $s$.

The question: what is $s$?

Classically, $n$ queries: set $x = 100\ldots0$ to read $s_0$, then $010\ldots0$ for $s_1$, and so on. One bit per query, and that is optimal.

Quantum: one query, and the register comes out holding $s$ exactly. The oracle is a CX from each input qubit $i$ with $s_i = 1$ onto the scratch qubit — and after the second Hadamard layer, the measured bitstring is $s$.

Measured:

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

Every shot, exactly right. No sampling, no majority vote.

This is the most satisfying circuit in the book: a hidden $n$-bit string extracted in a single query, deterministically, with no post-processing at all.

Deriving the output

Substitute $f(x) = s\cdot x$ into $\hat F(y)$ and the answer falls out in two lines:

$$\hat F(y) = \frac{1}{2^n}\sum_x (-1)^{s\cdot x + x\cdot y} = \frac{1}{2^n}\sum_x (-1)^{x\cdot(s\oplus y)} = \delta_{s\oplus y,\,0} = \delta_{y,s}$$

using §20.1's identity in the last step. The state after step 3 is exactly $|s\rangle$ — amplitude 1 on the secret, amplitude 0 on all $2^n - 1$ other strings.

That is why the measured column reads 1000/1000 and not 963/1000. There is no distribution to sample. The circuit is a deterministic unitary map from $|0\rangle^{\otimes n}$ to $|s\rangle$, and the measurement is a readout of a basis state rather than an estimate of anything.

The middle step is where the trick lives. $s\cdot x + x\cdot y \equiv x\cdot(s\oplus y)$ holds because addition mod 2 distributes over the bitwise dot product: $\sum_i s_i x_i + \sum_i x_i y_i = \sum_i x_i(s_i + y_i)$, and $s_i + y_i \bmod 2$ is $s_i \oplus y_i$. Read that way, the second Hadamard layer correlates the oracle's phase pattern against every candidate $y$ at once, and fires only where the patterns match. Bernstein–Vazirani is matched filtering over $2^n$ filters in one pass, and the "one query" is the single pass.

🔬 Honest Assessment — what the $n\to1$ speedup is and is not.

Is it real? Yes. The classical lower bound of $n$ queries is provable — each query returns one bit, and you need $n$ bits.

Is it exponential? No. It is linear: $n$ queries to 1. For $n = 100$ that is a hundredfold improvement in query count, which is a constant-factor-flavoured win, not a change in complexity class.

Is it useful? Not directly. "Recover the hidden string in a function you already know is a parity function" is not a problem anyone has. Bernstein–Vazirani exists to demonstrate a mechanism, and it does so with unusual clarity.

What it genuinely established — in the recursive version Bernstein and Vazirani actually published — is a super-polynomial separation in the query model, which was the first evidence that quantum computers might be more than polynomially faster than classical ones. The one-query parity trick is the pedagogical residue of a deeper result.

Bernstein–Vazirani and Deutsch–Jozsa are the same circuit

Compare the two implementations in this chapter's code/ directory, gate for gate.

   deutsch_jozsa(n, "balanced", mask)      bernstein_vazirani(secret, n)
   -----------------------------------     ------------------------------------
   x(n); h(n)                              x(n); h(n)
   h(range(n))                             h(range(n))
   cx(i, n) for each set bit of mask       cx(i, n) for each set bit of secret
   h(range(n))                             h(range(n))
   measure(range(n), range(n))             measure(range(n), range(n))

They are identical. Not similar — the same gates in the same order, with the mask renamed.

The reason is arithmetic: every non-zero parity function is balanced. If $s \neq 0$ then $s\cdot x$ is 0 on exactly half the inputs and 1 on the other half, so a Bernstein–Vazirani oracle is a legal Deutsch–Jozsa balanced oracle. Run Deutsch–Jozsa on it and §20.3's derivation applies unchanged: the register ends in $|s\rangle$, whatever you have decided to call the algorithm.

The difference lives entirely in what the caller reads off the bitstring.

   Bernstein–Vazirani reads:   all n bits          ->  s
   Deutsch–Jozsa reads:        "is it all zeros?"  ->  1 bit

Deutsch–Jozsa discards $n-1$ bits of a perfectly good answer. That is not a criticism — it is answering a smaller question — but it explains something the measured output shows and the prose has not. §20.5's table records a genuine balanced oracle producing {'0110': 2000}: a single non-zero outcome, the same one every shot. That outcome is the mask. Deutsch–Jozsa's "balanced" verdict is Bernstein–Vazirani's answer, compressed to a boolean.

It also sharpens the honest assessment above. Bernstein–Vazirani's $n \to 1$ speedup is not a second phenomenon stacked on Deutsch–Jozsa's; it is the same interference, read more carefully. This chapter has more algorithms than it has mechanisms, and Simon's is the second mechanism.

🔀 In Another Framework — the same three steps in Cirq and PennyLane, and one thing that will trip you.

Cirq 1.7.0, $n = 8$, $s = 11010110$:

python q = cirq.LineQubit.range(n + 1) c = cirq.Circuit( cirq.X(q[n]), cirq.H(q[n]), [cirq.H(q[i]) for i in range(n)], [cirq.CNOT(q[i], q[n]) for i in range(n) if (secret >> i) & 1], [cirq.H(q[i]) for i in range(n)], cirq.measure(*q[:n], key="s"), )

PennyLane 0.45.1 is the same circuit as a QNode on default.qubit with shots=1000, returning qml.counts(wires=range(n)); the gate names change to qml.PauliX, qml.Hadamard, qml.CNOT.

All three frameworks recover the secret on 1000 of 1000 shots with exactly one distinct outcome. Measured:

text Qiskit 2.5.1 outcome string 11010110 int 214 1000/1000 distinct 1 Cirq 1.7.0 bit array 01101011 int 107 1000/1000 distinct 1 PennyLane 0.45.1 outcome string 01101011 1000/1000 distinct 1

The strings are reversed, the integers differ by more than a factor of two, and every run is correct. Qiskit's get_counts() prints qubit $n-1$ leftmost; Cirq's measurement array and PennyLane's counts put wire 0 first. $214 = 11010110_2$ and $107 = 01101011_2$ are the same eight bits read in opposite directions.

A bit-order bug in this algorithm is invisible in the success rate. You still get one clean outcome on every shot, so every "did it work" check passes — the failure surfaces only as a secret that is the bit-reversal of the one you planted. Chapter 18 §18.2 tabulates the general hazard. Bernstein–Vazirani is where it is easiest to hit, because the output is the answer, with no post-processing stage to launder the convention.

20.4 Simon's Algorithm

The first exponential separation, and structurally the most important algorithm in this chapter, because Shor's (Chapter 23) is the same idea over a different group.

The promise: $f: \{0,1\}^n \to \{0,1\}^n$ is two-to-one with a hidden period $s \neq 0$:

$$f(x) = f(y) \iff y = x \oplus s$$

The question: what is $s$?

Classically you must find a collision — two inputs with the same output — and by the birthday bound that takes $\Theta(2^{n/2})$ queries.

Quantum: $O(n)$ queries. But unlike the previous two, one query is not enough, and the algorithm has a genuinely essential classical post-processing stage.

What one query gives you

Apply §20.1's pattern with the oracle's output register left unmeasured. Each measurement of the input register returns a random $y$ satisfying

$$y \cdot s = 0 \pmod 2$$

Verified, for two different periods:

   n=3, s=110:  4 distinct y values measured
                all satisfy y·s = 0 (mod 2)?  True
                sample: ['000', '001', '110', '111']

   n=4, s=1011: 8 distinct y values measured
                all satisfy y·s = 0 (mod 2)?  True

Note $2^{n-1}$ distinct values in each case — exactly the strings orthogonal to $s$, and nothing else. Each measurement is one linear equation in the unknown bits of $s$.

Where the orthogonality comes from

The two measured facts — exactly $2^{n-1}$ distinct outcomes, and every one satisfies $y\cdot s = 0$ — are the same fact, and three lines of algebra produce both.

After the Hadamards and the oracle, the state is

$$\frac{1}{\sqrt{2^n}}\sum_{x} |x\rangle\,|f(x)\rangle$$

The promise says $f$ is two-to-one with $f(x) = f(x\oplus s)$, so the $2^n$ inputs fall into $2^{n-1}$ pairs $\{x_0,\, x_0\oplus s\}$, one per distinct output value. Grouped that way, the state is a uniform superposition over pairs:

$$\frac{1}{\sqrt{2^{n-1}}}\sum_{\text{pairs}} \frac{|x_0\rangle + |x_0\oplus s\rangle}{\sqrt2}\, \big|f(x_0)\big\rangle$$

Apply $H^{\otimes n}$ to the input register of one pair, using §20.1's transform:

$$\frac{|x_0\rangle + |x_0\oplus s\rangle}{\sqrt2} \;\xrightarrow{\;H^{\otimes n}\;}\; \frac{1}{\sqrt{2^{n+1}}}\sum_y \Big[(-1)^{x_0\cdot y} + (-1)^{(x_0\oplus s)\cdot y}\Big]|y\rangle$$

Since $(x_0\oplus s)\cdot y = x_0\cdot y + s\cdot y \pmod 2$, the bracket factors:

$$(-1)^{x_0\cdot y}\Big[1 + (-1)^{s\cdot y}\Big] = \begin{cases} 2\,(-1)^{x_0\cdot y} & s\cdot y = 0\\[2pt] 0 & s\cdot y = 1\end{cases}$$

That bracket is the whole algorithm. Strings not orthogonal to $s$ get $1 + (-1) = 0$ — destructive interference, exactly. Strings orthogonal to $s$ get amplitude $2/\sqrt{2^{n+1}}$, so

$$P(y) = \frac{4}{2^{n+1}} = \frac{1}{2^{n-1}} \quad\text{for each of the } 2^{n-1} \text{ strings with } y\cdot s = 0$$

Uniform over the orthogonal complement of $s$, and exactly zero everywhere else. Both measured facts, derived: $2^{n-1}$ distinct outcomes because that is how many strings survive, and all of them orthogonal because the rest have amplitude zero rather than small amplitude.

Note what does not appear in the answer: $x_0$. It survives only as an unobservable sign $(-1)^{x_0\cdot y}$ inside each pair's contribution. The algorithm learns nothing about which pair it landed in — which is exactly right, because that is not what you asked.

📐 Math Aside — you never have to measure the output register.

The derivation above collapses to one pair, as if the output register had been measured. The circuit in example-02-bernstein-vazirani-and-simon.py does no such thing: it measures the input register only and leaves the $n$ output qubits alone entirely.

Both give the same distribution, by the principle of deferred measurement: a measurement on a register that is never subsequently acted upon can be moved to the end of the circuit or omitted without changing the statistics of the other registers. Tracing out the output register produces the same mixture over pairs that measuring it would.

This is a real saving, not a formality. Simon's needs $n$ output qubits it never reads, and a mid-circuit measurement is expensive: Chapter 39 measured measure at 1,560 ns against sx at 32–64 ns — a factor of 24 to 49 — and Chapter 9's dynamic circuits exist largely to manage that cost. Here you pay none of it, because deferred measurement says the measurement was never doing any work.

The one thing you cannot do is reuse those qubits mid-circuit without measuring or resetting them. The entanglement is load-bearing: it is what makes the input register a mixture over pairs rather than a coherent superposition over everything, and that mixture is where the $2^{n-1}$-fold cancellation comes from.

The classical half

Collect $n-1$ linearly independent equations and solve the system over $\mathbb{F}_2$. The solution space is one-dimensional, and the nonzero solution is $s$.

This is not an afterthought. Roughly half the work is Gaussian elimination over $\mathbb{F}_2$, and the algorithm is incomplete without it. Chapter 23 has the same structure — a quantum subroutine producing a constraint, and classical post-processing (there, a continued-fraction expansion) turning constraints into the answer.

⚠️ Common Pitfall — the measurements are random, and some are useless.

Each shot gives a uniformly random $y$ orthogonal to $s$. Some will be linearly dependent on ones you already have, and $y = 0$ is always a valid measurement and always useless.

So you do not run the circuit $n-1$ times; you run it until you have $n-1$ independent equations, which takes $n-1 + O(1)$ shots in expectation. An implementation that assumes a fixed shot count will occasionally return an underdetermined system, and the failure looks like the algorithm being wrong rather than unlucky.

Check the rank, not the count.

How many shots, exactly

"$n-1 + O(1)$" is right, and the $O(1)$ has a closed form worth knowing.

Suppose you hold $k$ independent equations. Their span inside the orthogonal complement of $s$ — an $(n-1)$-dimensional space over $\mathbb{F}_2$ — contains $2^k$ vectors. The next measurement is uniform over all $2^{n-1}$ of them, so it is useful with probability

$$1 - \frac{2^{k}}{2^{n-1}} = 1 - 2^{\,k-n+1}$$

The number of draws needed to advance from rank $k$ to rank $k+1$ is geometric with that success probability, so its mean is the reciprocal. Summing over $k = 0,\dots,n-2$ and substituting $j = n-1-k$:

$$\mathbb{E}[\text{shots}] = \sum_{j=1}^{n-1}\frac{1}{1 - 2^{-j}} = (n-1) + \sum_{j=1}^{n-1}\frac{1}{2^{j}-1}$$

The correction converges, and fast:

    n     E[shots]     n-1     excess
    3       3.3333       2     1.3333
    4       4.4762       3     1.4762
    6       6.5751       5     1.5751
   10      10.6047       9     1.6047
   20      20.6067      19     1.6067
   40      40.6067      39     1.6067

$$\sum_{j=1}^{\infty}\frac{1}{2^j - 1} = 1.606695\ldots$$

The $O(1)$ is 1.6067 — the Erdős–Borwein constant — and it is effectively constant from $n = 10$ onward. So the honest statement of Simon's shot cost is $n + 0.61$ shots on average, at every size. Rank-checking does not cost you a factor; it costs you under two extra shots.

Which is the entire argument for doing it. The fixed-shot version saves those 1.6 shots and succeeds only

    n    P(n-1 random draws span)
    3                     0.3750
    4                     0.3281
    6                     0.2980
   10                     0.2894
   20                     0.2888
   limit                  0.288788

Under 29%. You are trading a 71% failure rate for 1.6 shots, and the failure is silent — an underdetermined system that looks like the algorithm being wrong. Case Study 2 is what that trade looks like from inside a debugging session.

📊 What the Numbers Say — "used 3 outcomes to reach rank 2" is one draw from a distribution.

Case Study 2 reports what the rank-based collector consumed:

text n=3, s=110: used 3 outcomes to reach rank 2 (need 2) n=4, s=1011: used 4 outcomes to reach rank 3 (need 3)

Both exceed $n-1$ by exactly one, and it is tempting to read "one redundant shot" as the rule.

It is not a rule; it is a single sample each. The derivation above puts the means at 3.3333 and 4.4762, and the distributions are long-tailed to the right. At $n = 4$ the three steps succeed with probability $7/8$, $3/4$ and $1/2$ — so a run finishes in the minimum 3 shots only $\tfrac78\cdot\tfrac34\cdot\tfrac12 = 0.3281$ of the time, which is exactly the independence figure in the table above, arrived at from the other direction. Runs consuming 6, 8 or 12 shots have small but entirely real probability, and no run can consume fewer than 3.

Two runs landing within one shot of their means is a coincidence, not a specification. This book has documented seven occasions where its author drew a conclusion from a sample this size and had to correct it in print. The defensible claim is "the mean is $n - 1 + 1.61$", which is derived and exact; "it uses one extra shot" is an observation about two runs.

This is also why redundant_shots is on the result object rather than assumed. A quantity that is usually 1 or 2 and occasionally 8 is precisely the kind of thing that must be reported rather than inferred.

🧱 Project Checkpoint — vqelab/algorithms.py: the four, with their post-processing.

deutsch_jozsa(oracle, n), bernstein_vazirani(oracle, n), and simon(oracle, n), each returning a result object carrying the answer and the evidence for it.

solve_f2(equations) does Gaussian elimination over $\mathbb{F}_2$ — the half of Simon's algorithm that is not quantum, and the half that is usually skipped in tutorials.

simon() collects shots until the rank reaches $n-1$, rather than assuming a fixed count, and reports how many shots it needed and how many were redundant.

check_promise(truth_table) verifies, by brute force, that a function actually satisfies the promise its algorithm requires — which is exactly what the quantum algorithm cannot do, and therefore what a test harness must.

Its tests assert: Deutsch–Jozsa returns constant with probability exactly 1 and balanced with probability exactly 0; Bernstein–Vazirani recovers the secret on every shot for several $n$; every Simon measurement satisfies $y \cdot s = 0$; and an oracle violating the promise is rejected by check_promise while the algorithm happily returns an answer.

20.5 The Promise

Now the part that matters more than the algorithms.

Every algorithm in this chapter solves a promise problem. The input is guaranteed to have a specific structure, and the algorithm's behaviour on inputs lacking that structure is undefined.

• Deutsch–Jozsa: promised constant or balanced.
• Bernstein–Vazirani: promised $f(x) = s\cdot x$.
• Simon: promised two-to-one with period $s$.

What happens when the promise is violated? Take a function that is neither constant nor balanced — one that returns 1 on exactly one input out of sixteen — and run Deutsch–Jozsa on it:

   n=4, oracle marks a single input (neither constant nor balanced)

   P(all zeros) = 0.7590
   Deutsch–Jozsa reports: BALANCED

   top outcomes: {'0000': 1518, '0110': 40, '1111': 37, '1100': 36}

Confidently wrong. The standard decision rule — all zeros means constant, anything else means balanced — sees a non-zero outcome 24% of the time and reports "balanced." The function is neither.

There is no error, no warning, and no flag. The circuit ran correctly; the algorithm returned an answer; the answer is meaningless.

The exact shape of a broken promise

$0.7590$ is not an arbitrary number. Deriving it explains both where it came from and — more importantly — the limits of the detector this section is about to recommend.

Let $f$ be 1 on exactly $m$ of the $2^n$ inputs. The all-zeros amplitude is just the mean of $(-1)^{f(x)}$:

$$\hat F(0) = \frac{1}{2^n}\Big[(2^n - m)(+1) + m(-1)\Big] = 1 - \frac{2m}{2^n} \qquad\Longrightarrow\qquad \boxed{\;P(\text{all zeros}) = \left(1 - \frac{2m}{2^n}\right)^{2}\;}$$

Constant is $m = 0$ or $m = 2^n$, giving $P = 1$. Balanced is $m = 2^{n-1}$, giving $P = 0$. Every value in between is a violated promise, and the formula says exactly what it looks like. Checked against the exact statevector at $n = 4$:

    m   derived (1 - 2m/2^n)^2   exact statevector    |diff|
    0                 1.000000            1.000000   1.4e-15
    1                 0.765625            0.765625   5.2e-15
    2                 0.562500            0.562500   7.3e-15
    3                 0.390625            0.390625   7.4e-15
    4                 0.250000            0.250000   6.2e-15
    5                 0.140625            0.140625   4.3e-15
    6                 0.062500            0.062500   2.2e-15
    7                 0.015625            0.015625   5.9e-16
    8                 0.000000            0.000000   2.4e-31

The chapter's $0.7590$ is the $m = 1$ row, sampled. Derived, $P = 0.765625$; at 2,000 shots the standard error is $\sqrt{p(1-p)/N} = 0.00947$, and the measured value sits 0.70 standard errors below the derived one. The two agree, and now the number has a reason rather than a provenance.

Now read the last rows. At $m = 7$ — a function wrong on one input out of sixteen, in the other direction — $P = 0.015625$. The honest rule uses a tolerance of 0.01 and catches it, barely. Widen the tolerance to 0.02 and the detector reports "balanced" for a function that is not. And at 2,000 shots the gap between 0.015625 and the 0.01 threshold is about two standard errors, so the tolerance is not a free parameter: it is a joint decision about how large a violation you will tolerate missing and how many shots you are willing to spend distinguishing it from the threshold.

★★ And the detector gets exponentially worse as $n$ grows. Fix $m = 1$ — the same "marks a single input" oracle measured above — and let $n$ increase:

     n         2^n      P(all zeros)        1 - P    shots for one non-zero outcome
     4          16       0.765625000    2.344e-01                                 4
     8         256       0.984436035    1.556e-02                                64
    12       4,096       0.999023676    9.763e-04                             1,024
    16      65,536       0.999938966    6.103e-05                            16,384
    20   1,048,576       0.999996185    3.815e-06                           262,144

At $n = 20$, a function that is wrong on exactly one input out of a million is reported CONSTANT with $P = 0.999996$, and you need about $2^{18} = 262{,}144$ shots to see a single non-zero outcome at all — before any question of statistical confidence in it.

The signature this section recommends reading is real at $n = 4$ and useless at $n = 20$. That is not a flaw in the advice; it is the advice's domain of validity, and it is worth stating plainly because the case where you most want a promise check — large $n$, where brute-force verification is impossible — is exactly the case where the histogram cannot supply one.

The general statement: the violation Deutsch–Jozsa can detect is measured in the fraction $m/2^n$, while the promise you actually care about is violated in the count $m$. Those two diverge exponentially, and the algorithm is only sensitive to the first.

🐛 Debug This — the distribution knows, even though the algorithm does not.

Count the distinct outcomes, on 2000 shots at $n = 4$:

text constant (promise holds) 1 outcome {'0000': 2000} balanced (promise holds) 1 outcome {'0110': 2000} marks one input (promise BROKEN) 16 outcomes {'0000': 1518, '0110': 40, ...}

Both valid promises produce exactly one outcome. A constant function gives all-zeros with probability 1; a balanced function gives the single mask that defines it, also with probability 1.

The broken oracle produces all sixteen — 76% on all-zeros and a long thin tail across everything else. That shape is the signature of a violated promise, and it is unmistakable in the histogram while being invisible to the yes/no decision rule.

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

This is Chapter 12 §12.6's lesson arriving in a new setting: read the distribution, not just the scalar you reduced it to. There, four missing outcomes named a stuck qubit; here, a long tail names a broken assumption.

📉 Noise Report — on hardware, noise and a violated promise produce the same signature.

Every number in this chapter comes from AerSimulator with no noise model. The exactness is a property of the simulator, and the histogram diagnostic above depends on it.

A balanced Deutsch–Jozsa or Bernstein–Vazirani query is $\mathrm{popcount}(s)$ CX gates. Chapter 30 §30.3 measured that a single chip quotes two-qubit error rates from 0.00750 to 0.07205 — a factor of 9.6 across one device — and Chapter 30 §30.4 established that a median-error estimate predicted Chapter 28's circuit fidelity to within 12%, so a product-of-gate-fidelities estimate is worth making. It predicts:

text CX gates at err 0.00750 at err 0.07205 4 0.9703 0.7415 6 0.9558 0.6385 8 0.9416 0.5498

The same eight-CX circuit is predicted between 94% and 55% fidelity depending only on which qubits the transpiler picked. Chapter 29 measured that choice mattering directly: a hardware-aware level-1 layout scored 0.9116 against a naive level-3's 0.7720.

Now put that beside the diagnostic. A broken promise shows up as probability leaking out of the expected outcome into a spread across the register. Depolarizing noise does exactly the same thing. At 55% predicted fidelity you would see roughly the pattern §20.5 calls the signature of a violated promise, produced by a circuit whose promise is perfectly intact.

So the rule needs a qualifier. On a simulator, a spread means the promise is broken. On hardware, a spread means the promise is broken or the device is noisy, and the histogram cannot tell you which. Chapter 27 §27.3's answer is the right one: assert a relation between two runs rather than a threshold on one. Run a known-good constant oracle on the same qubits in the same job and compare shapes — a control circuit absorbs the noise that a fixed tolerance cannot.

💰 Cost and Queue — "one query" is not one billable unit.

Deutsch–Jozsa needs a single shot. Chapter 39 measured a Bell circuit at 4,096 shots consuming 6.93 ms of QPU time — 1.69 µs per shot, matching the instruction-duration total for a short circuit. So the algorithm's entire execution is under two microseconds.

And Chapter 39 §39.3 measured utilization at a five-minute queue as $2.31\times10^{-5}$ — the wall clock was 43,340× the device time. For a one-shot job it is far worse: $1.69\times10^{-6} / 300 = 5.6\times10^{-9}$ of the wall clock spent computing.

The unit query complexity counts is not the unit anyone is billed in. Chapter 39 priced one VQE run three ways — \$50 on per-minute billing, \$7,432 per-shot, \$185,542 on a trapped-ion machine — and the spread is entirely which unit the invoice counts. A one-query algorithm and a thousand-shot algorithm cost nearly the same under per-minute billing and differ by three orders of magnitude under per-shot billing, for identical physics.

The consequence for this chapter is sharper than that. The promise-violation detector needs the histogram, so it needs many shots even though the algorithm needs one. At $n = 20$ with $m = 1$ that is 262,144 shots for a single expected non-zero outcome — about 0.44 s of QPU time at Chapter 39's 1.69 µs per shot, and a per-shot invoice 262,144 times the one "one query" implies. The safety check costs five orders of magnitude more than the algorithm it is checking, which is the real reason it is rarely implemented.

🗝️ Version Note — Qiskit does not ship these algorithms, and the module that used to is gone.

There is no DeutschJozsa class to import. Verified against the environment used throughout this book:

text import qiskit.algorithms -> ModuleNotFoundError import qiskit_algorithms -> ModuleNotFoundError

qiskit.algorithms was deprecated and removed; its successor qiskit-algorithms is a separate package and is not installed with Qiskit 2.5.1. These algorithms are five lines of circuit construction each, and shipping them as classes was never buying much.

What Qiskit 2.5.1 does ship in qiskit.circuit.library is the oracle machinery and several of this chapter's relatives:

text PhaseOracle PRESENT a phase oracle from a boolean expression GroverOperator PRESENT Chapter 21's iterate InnerProduct PRESENT the s·x primitive itself HiddenLinearFunction PRESENT a relative of Bernstein–Vazirani FourierChecking PRESENT another promise problem in the same family IQP PRESENT the circuit family behind Chapter 34's feature map

PhaseOracle is the one worth knowing. It takes a boolean expression string and builds §20.1's step 2 directly — verified: PhaseOracle("(a & b) | (~a & c)") is a 3-qubit diagonal unitary whose entries are exactly $\pm1$, with no scratch qubit at all, so the $|-\rangle$ preparation is not merely handled, it is unnecessary.

It inherits every cost consideration in Chapter 19 §19.5 anyway, because it still has to synthesize a multi-controlled operation. Hand it a circuit with no spare qubits and it will do so without ancillas, which Chapter 19 §19.6 priced at 26,978 T gates against 55 — and it will not warn you.

🔬 Honest Assessment — how much do promise problems tell us?

The theorems are real. Deutsch–Jozsa's separation is exact and provable, and Simon's exponential separation is one of the foundational results in the field.

And the problems were constructed to exhibit them. Nobody needs to distinguish constant from balanced functions. Nobody has a parity oracle whose string they want. These are not applications; they are existence proofs — demonstrations that the query-complexity gap between quantum and classical is not zero, built by people who needed to establish that before anything else was worth attempting.

That was a genuine and important contribution, and it is a different claim from "quantum computers are exponentially faster."

Simon's is the exception that justifies the exercise. Its structure — a hidden subgroup, found by quantum sampling plus classical linear algebra — is exactly the structure of Shor's algorithm, which factors integers, which matters enormously. Simon's algorithm is a toy, and it is a toy that led directly to the most consequential quantum algorithm known. That is the strongest possible argument for studying contrived problems carefully.

What query complexity models, and what it leaves out

Chapter 19 §19.7 named three gaps between "one query" and "one operation." This chapter is where they become concrete, so they are worth restating against specific algorithms.

Query complexity counts oracle invocations and nothing else. Gate count, depth, qubit count, the cost of constructing the oracle, and the cost of running it under error correction are all outside the model, deliberately — that restriction is what makes the lower bounds provable.

For Deutsch–Jozsa, the gap is construction cost. The oracle measured above is a parity: at most $n$ CX gates, zero T gates. A generic balanced function is not a parity, and it is not cheap. Count them. There are $\binom{2^n}{2^{n-1}}$ balanced functions on $n$ bits, and

$$\log_2\binom{16}{8} = 13.7 \text{ bits}, \qquad \log_2\binom{2^{20}}{2^{19}} = 1{,}048{,}566 \text{ bits}$$

Naming a generic balanced function on 20 bits takes about a million bits — 128 KB. A circuit of $g$ gates from a fixed gate set on $n+1$ qubits is describable in $O(g \log n)$ bits, so a counting argument forces almost every balanced function to need $\Omega(2^n / \log n)$ gates. The argument is crude and it is airtight: you cannot compress $2^n$ bits of specification into a subexponential circuit for most functions.

So for almost every instance of the problem Deutsch–Jozsa solves, the "one query" is a circuit exponentially large in $n$ — and building it required knowing $f$ on all $2^n$ inputs, which is strictly more work than the classical algorithm's $2^{n-1}+1$ queries. The algorithm wins the query count and loses the total.

The functions with cheap oracles are the structured ones, and structured functions are precisely the ones a classical algorithm can also exploit. That shape recurs through the rest of the book, and it is not specific to this chapter.

Simon's algorithm is the exception, again. Its promise — two-to-one with a hidden period — is itself a strong structural constraint, so a periodic $f$ generally does have a compact circuit; and unlike Deutsch–Jozsa, its separation survives bounded error. The one algorithm here whose separation is robust is also the one whose oracles are plausibly cheap. That is not a coincidence, and it is why Chapter 23 exists.

Where this would flip

An oracle separation becomes practically useful when four conditions hold at once. Scoring this chapter's algorithms against them is the most compact summary of its argument.

   condition                                     D–J     B–V      Simon    Shor (Ch.23)
   ---------------------------------------------------------------------------------
   1. separation survives bounded error           no      no        yes             yes
   2. oracle cheap relative to queries saved      no*    yes   plausibly             yes
   3. promise is a property of the problem        no      no       no**             yes
   4. classical rival genuinely query-bound       no      no         no             n/a

* cheap for parities, exponential for generic balanced functions, as above. ** the hidden-subgroup structure is a real property of real problems; the specific two-to-one-over-$(\mathbb{Z}_2)^n$ form is not.

Condition 1 is the one Deutsch–Jozsa fails hardest, and failing it costs the entire headline: 21 random classical queries beat the $2^{n-1}+1$ worst case at every $n$, with error below $10^{-6}$.

Condition 4 is the one everybody forgets. The classical lower bound holds over algorithms that may only evaluate $f$ at points. Real classical algorithms read source, exploit sparsity, use algebraic structure and index data. And you must have a circuit for $f$ to run the quantum algorithm at all — which means the classical competitor could have inspected it.

Condition 3 is what turns Simon's into Shor's. Order-finding's "promise" — that $a^r \equiv 1 \pmod N$ for some $r$ — is not a precondition someone imposed to make an algorithm work. It is a theorem about modular arithmetic. Nobody has to verify Shor's promise, because number theory already did, and that single difference separates a toy from the most consequential quantum algorithm known.

So the thing to look for in any claimed oracle speedup is condition 3: ask where the promise came from. If it came from the problem, the separation may survive contact with practice. If it came from the algorithm's requirements, you are looking at an existence proof — valuable, and not an application.

🧪 Run It — three experiments, ordered by how much they will change your mind.

Sweep the violation. Change example-03-broken-promise.py's neither() to mark $m$ inputs for $m = 1,\dots,7$ at $n = 4$, and plot $P(\text{all zeros})$ against $m$. Check each point against $(1 - 2m/2^n)^2$. Then repeat at $n = 8$ with $m = 1$ and watch the detector's margin collapse from 0.234 to 0.0156 — the same broken function, eight times harder to see.

Break Bernstein–Vazirani's promise instead. Replace the CX oracle with a non-parity function — an AND of two inputs is the easiest — and look at the output distribution. Deutsch–Jozsa's violation produced a spike plus a tail; predict what a parity violation looks like before you run it, using §20.1's $\hat F(y)$, then check. (Exercise 20.23 is this experiment written out.)

Make Simon's fail on purpose. Take exactly $n-1$ shots at $n = 6$, solve, and repeat 100 times. The derivation in §20.4 predicts a success rate of 0.2980. If your measured rate lands near it, you have reproduced Case Study 2's bug deliberately — which is a far better way to understand a flaky failure than meeting it in production.

Then set $s = 0$, so $f$ becomes one-to-one and the promise is violated in the one way the algorithm explicitly forbids. §20.4's derivation tells you what to expect before you run it: with $s = 0$ every $y$ satisfies $y \cdot s = 0$, so the constraint is vacuous. Predict the distribution, then confirm it, and notice that nothing in the output announces the problem.

20.6 Summary

All three algorithms are the same three steps: superpose with $H^{\otimes n}$, query the phase oracle, interfere with $H^{\otimes n}$. The final amplitude of outcome $y$ is $\frac{1}{2^n}\sum_x (-1)^{f(x) + x\cdot y}$, and whether that sum adds or cancels depends on the structure of $f$. Step 3 is the step with no classical analogue — evaluating $f$ on a superposition is easy and useless; making the answers interfere is the mechanism.

Deutsch–Jozsa distinguishes constant from balanced in one query against a classical worst case of $2^{n-1}+1$ — at $n=50$, one query versus 562 trillion. Measured: $P(\text{all zeros})$ exactly 1.000 for constant and exactly 0.000 for balanced. The advantage is not "evaluating $f$ on all inputs at once" but that interference evaluates a global property of $f$ without examining terms individually.

Bernstein–Vazirani recovers a hidden $n$-bit string in one query, deterministically — measured 1000 of 1000 shots correct at $n = 4, 6, 8$. The speedup is $n \to 1$, which is linear, not exponential, and the problem is not one anyone has. Its historical importance is the recursive version's super-polynomial separation.

Simon's algorithm gives the first exponential separation: $O(n)$ queries against $\Theta(2^{n/2})$ classically. Each measurement returns a random $y$ with $y \cdot s = 0 \pmod 2$ — verified: every measured value satisfies it, and exactly the $2^{n-1}$ orthogonal strings appear. Half the algorithm is classical: collect $n-1$ independent equations and solve over $\mathbb{F}_2$. Check the rank, not the shot count — $y=0$ is always valid and always useless.

★★ Every one of these is a promise problem, and the algorithms cannot verify the promise. Given a function that is neither constant nor balanced:

   P(all zeros) = 0.7590   ->   Deutsch–Jozsa reports BALANCED

No error, no warning, an answer. The distribution reveals it — 76% on all-zeros plus a long thin tail, where a genuine balanced function concentrates on a single outcome — but the scalar decision rule does not. Add the third branch: neither cleanly 1 nor cleanly 0 means promise violated.

★★ The violation has a closed form. A function that is 1 on $m$ of $2^n$ inputs gives $P(\text{all zeros}) = \left(1 - 2m/2^n\right)^2$ — verified against the exact statevector to $10^{-15}$, and the source of the 0.7590 above ($m=1$, $n=4$: derived 0.765625, measured 0.70 standard errors away at 2,000 shots). It also bounds the diagnostic. At $n = 20$ a single wrong input gives $P = 0.999996$, needing $2^{18} = 262{,}144$ shots to see one non-zero outcome — about 0.44 s of QPU time at Chapter 39's 1.69 µs per shot. The histogram check is real at $n = 4$ and useless at $n = 20$, because the algorithm is sensitive to the fraction $m/2^n$ while the promise is violated in the count $m$.

★ And Deutsch–Jozsa's exponential separation does not survive bounded error. Twenty-one random classical queries misclassify a balanced function with probability $9.5\times10^{-7}$, at every $n$; the $2^{n-1}+1$ bound applies only to classical algorithms forbidden to be wrong. Simon's does survive — its $\Theta(2^{n/2})$ classical bound holds for randomized algorithms too — which is the second reason it, and not Deutsch–Jozsa, is Shor's ancestor.

Bernstein–Vazirani and Deutsch–Jozsa are literally the same circuit, since every non-zero parity is balanced; the difference is that one reads all $n$ bits and the other reads one. And the expected shot count for Simon's is $n - 1 + 1.6067$ — the Erdős–Borwein constant, effectively fixed from $n = 10$ on. Rank-checking costs under two extra shots and buys a success rate of 1 instead of 0.29.

These problems were constructed to exhibit their separations. They are existence proofs, not applications — and that was a genuine contribution, distinct from the claim that quantum computers are exponentially faster in general. Simon's is the exception: its hidden-subgroup structure is exactly Shor's, which is why a toy problem about periodic functions led to the most consequential quantum algorithm known.

Next: Chapter 21 — Grover's algorithm, the one everybody has heard of. It drops the promise, which makes it far more general than anything here — and the quadratic speedup that buys is worth considerably less than it sounds once Chapter 19's oracle pricing is applied to it.