Part IV. Protocols and Algorithms

Deutsch, Deutsch-Jozsa, and Bernstein-Vazirani

Three small algorithms from the field's first decade still teach the core move of quantum algorithm design: ask one structured question, hide the answer in phase, and let a basis change read it back.

Listen to this chapter

Deutsch, Deutsch–Jozsa, and Bernstein–Vazirani solve no practical problem, and they still earn a full chapter, because nearly every serious quantum algorithm since reuses their trick: convert a global property into a phase pattern, then decode it with Hadamards.

By the end you will be able to trace Bernstein–Vazirani line by line, state exactly what its one-query separation proves, and explain why the promise in the problem statement is doing the heavy lifting.

Core concepts: phase kickback, Hadamard as basis change, oracle promise, query separation.

Notice that the oracle is queried once, yet both bits of the hidden string come out. The answer never travels through the target register — it lives in the phase pattern the final Hadamards decode.

The pattern these algorithms teach

Each of the three algorithms poses a question about a black-box function and answers it with fewer queries than any classical algorithm allowed the same access. Deutsch's problem asks whether a one-bit function is constant or balanced — one quantum query, two classical. Deutsch–Jozsa scales that to $n$ bits, where a deterministic classical algorithm can need exponentially many queries in the worst case. Bernstein–Vazirani hides an $n$ -bit string inside a linear function and recovers all of it in one query, where a classical learner needs $n$ .

The separations are real and the problems are contrived. Both facts matter. These algorithms exist to make a mechanism visible: a quantum circuit can interrogate a structured oracle, write the answer into relative phases, and use interference to expose a global property that no single classical query can see. Learn the mechanism here and you will recognize it inside every heavier algorithm that follows.

The machinery, precisely

For Bernstein–Vazirani, the hidden string $s$ defines the function:

f_{s} (x) = s \cdot x mod 2

With the target prepared as $∣ - ⟩$ , the oracle acts through phase kickback:

U_{f} ∣ x ⟩ ∣ - ⟩ = (- 1)^{f (x)} ∣ x ⟩ ∣ - ⟩

Hadamards do the decoding, and they earn their keep here. $H$ is a basis-change gate, not a randomness button:

H^{2} H Z H = I = X

The first identity says the encoding is exactly reversible; the second says $H$ converts phase information (a $Z$ -type sign) into bit information (an $X$ -type flip). The final Hadamard layer in these circuits is that conversion, applied to every input qubit at once.

Worked example: two-bit Bernstein-Vazirani

Start with two input qubits and a target:

∣ 00 ⟩ ∣ 1 ⟩

Hadamards on all three wires create a uniform superposition over inputs and the minus state on the target:

\frac{1}{2} x \sum ∣ x ⟩ \otimes ∣ - ⟩

The oracle writes the hidden string into the phases:

\frac{1}{2} x \sum (- 1)^{s \cdot x} ∣ x ⟩ \otimes ∣ - ⟩

Now apply $H$ to the two input qubits. The phase pattern is precisely the Fourier-like signature of $s$ , and the basis change concentrates all amplitude on one basis state:

∣ s ⟩

Measure the input register and you read the hidden string directly — one query, both bits. Deutsch's algorithm is the same skeleton with a one-bit input and a different question; Deutsch–Jozsa is the same skeleton with the constant-versus-balanced promise.

Where the intuition fails

The first trap is saying the oracle prints the hidden string. It never does. The string becomes a pattern of signs on branches of a superposition, and only the final basis change makes that pattern measurable. Skip the phase step in your explanation and you have described a faster lookup, which is not what happened.

The second trap is overgeneralizing the separation. One query beats $n$ queries here because the promise guarantees a perfectly linear function and the oracle answers coherently. A real dataset with no such promise gets no such speedup. The promise and the access model carry the meaning; the query count is just their shadow.

The engineering view

For a computer scientist, these algorithms are unit tests for the standard quantum pattern:

prepare registers, including the $∣ - ⟩$ target;
create superposition over inputs;
query the structured oracle once;
let phase kickback encode the answer;
apply interference — the final Hadamard layer;
measure a compact answer.

Debugging an implementation means checking each step in isolation: target preparation, oracle convention, final Hadamards, measurement register. A useful test is to run more than one hidden string. If $s = 00$ , the phase pattern is flat and the output should read 00; if $s = 10$ , branches with first bit 1 pick up a sign and the output should read 10. If only one case works, your oracle is probably hard-coded rather than computing $s \cdot x mod 2$ .

This is also the right place to feel the difference between a black box and a compiled circuit. A simulator can hand you the oracle as a function. Hardware needs it decomposed into gates, controls, and possibly ancillas — a decomposition whose depth belongs in any honest cost accounting, even though the query-complexity lesson survives it.

What this buys you in diligence

If a pitch cites these algorithms as proof of broad quantum advantage, ask three questions: what real workload carries the same promise structure, how is the oracle implemented and at what depth, and what is the classical baseline under equal access? The algorithms demonstrate a mechanism. A mechanism is not a market, and a one-query toy is not a product roadmap.

Exercise

Run the two-bit case by hand. Take Bernstein–Vazirani with $s = 10$ and trace it from $∣ 00 ⟩ ∣ 1 ⟩$ to measurement.

Write the state after each layer: first Hadamards, oracle, final Hadamards.
State the classical query count for learning a two-bit $s$ under the same black-box access, and for $n$ bits generally.
Mark the exact line of your derivation where phase becomes a measurable bit string, and explain it using $H Z H = X$ .
Repeat with $s = 00$ and confirm the flat phase pattern still yields the right answer.
Close with one sentence: does this toy support a product claim, or only a mechanism claim?

Check your understanding

Answer without notes: in Bernstein–Vazirani, where does the hidden string live between the oracle call and the final measurement, and what makes it readable at the end?

A passing answer says "in relative phases on the input register," credits the final Hadamard layer with the basis change, and names the promise that makes one query sufficient.

Oral defense: walk a colleague through the four state vectors of the worked example on a whiteboard, with no notes.

If you get stuck

If the string seems to appear from nowhere, your gap is phase kickback or the basis change — rework Chapter 27 (Oracles and Query Complexity) and then the Hadamard identities above. If interference itself feels shaky, Chapter 6 (Interference as the Engine of Quantum Algorithms) is the repair chapter for that.