Part IV. Protocols and Algorithms · Chapter 28

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.

Steven GellerPublished July 25, 2026Revised August 14, 2026

Lab

In this chapter 8 sections

Reader question. What common mechanism lets Deutsch-style and Bernstein–Vazirani circuits learn a promised property with few oracle queries?

Prepare superposition, use phase kickback to encode a promised Boolean structure, and apply Hadamards to Fourier-analyze that phase; the algorithms differ in the promise and decoded property, so their query advantage must be stated against matching classical models.

Scope and non-goals.

This chapter does not present these algorithms as practical application speedups.
It does not conflate deterministic and bounded-error classical query baselines or omit the promise.

Figure 28.1. 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.

Three promises, three questions

Write the exact task for Deutsch, Deutsch–Jozsa, and Bernstein–Vazirani.

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.

Evidence boundary. Deutsch's algorithm distinguishes constant from balanced one-bit functions under a promise. [David Deutsch] [Michael A. Nielsen]

One phase-oracle circuit pattern

Derive the shared preparation and kickback.

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

f_s(x)=s\cdot x\pmod2

With the target prepared as $\lvert-\rangle$ , the oracle acts through phase kickback:

U_f\lvert x\rangle\lvert-\rangle=(-1)^{f(x)}\lvert x\rangle\lvert-\rangle

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

\begin{aligned}H^2&=I,\\HZH&=X.\end{aligned}

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.

Evidence boundary. Bernstein–Vazirani recovers a hidden linear string with one quantum query in its oracle model. [Ethan Bernstein] [John Preskill]

Deutsch reads parity of two truth-table values

Trace the one-bit case fully.

Evidence boundary. Hadamard/Fourier analysis converts phase-encoded linear structure into a computational-basis result. [John Watrous] [Michael A. Nielsen]

x,s\in\{0,1\}^n,\qquad f_s(x)=s\cdot x\pmod2

Bernstein–Vazirani turns phase into a hidden string

Expand the n-bit transform.

These algorithms are unit tests for the standard quantum pattern:

prepare registers, including the $\lvert-\rangle$ 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 ⋅ 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.

Query tables before runtime stories

Compare exact classical and quantum information access.

Deutsch-Jozsa gives an exact one-query separation from deterministic classical black-box testing under its constant-or-balanced promise; randomized classical sampling changes the practical comparison when bounded error is allowed. Bernstein-Vazirani returns n hidden bits in one query where direct classical bit queries require n, but a physical phase oracle for an explicit linear function may itself cost O(n) gates. State the model before calling either result a runtime speedup.

Promise-algorithm circuit suite

Acceptance contract for Promise-algorithm circuit suite
Field	Reader-visible record
Format	Parameterized oracle generator and exhaustive small-n tests
Verification	For every n≤5 hidden string and all one-bit Deutsch functions, tests promise classification, query count, output, and compiled gate count.
Availability	Source-embedded acceptance record; no separate download is claimed

{
  "artifact": "Promise-algorithm circuit suite",
  "format": "Parameterized oracle generator and exhaustive small-n tests",
  "acceptance_test": "For every n≤5 hidden string and all one-bit Deutsch functions, tests promise classification, query count, output, and compiled gate count.",
  "publication_state": "source-embedded contract and worked fixture"
}

Executable reference fixture

Run with Python 3.11 or later. The final assertion is the chapter-level pass condition for this small instance.

import math

def h(state, qubit, count):
    mask = 1 << (count - 1 - qubit)
    output = state[:]
    scale = math.sqrt(0.5)
    for basis in range(len(state)):
        if basis & mask == 0:
            paired = basis | mask
            output[basis] = (state[basis] + state[paired]) * scale
            output[paired] = (state[basis] - state[paired]) * scale
    return output

def query_oracle(state, function, input_qubits):
    output = [0j] * len(state)
    for basis, amplitude in enumerate(state):
        x = basis >> 1
        y = basis & 1
        destination = (x << 1) | (y ^ function(x))
        output[destination] += amplitude
    return output

def one_query_state(function, input_qubits, target_one=True, query_count=1):
    total = input_qubits + 1
    state = [0j] * (1 << total)
    state[1 if target_one else 0] = 1.0
    for qubit in range(total):
        state = h(state, qubit, total)
    before_oracle = state[:]
    for _ in range(query_count):
        state = query_oracle(state, function, input_qubits)
    after_oracle = state[:]
    for qubit in range(input_qubits):
        state = h(state, qubit, total)
    probabilities = [0.0] * (1 << input_qubits)
    for basis, amplitude in enumerate(state):
        probabilities[basis >> 1] += abs(amplitude) ** 2
    return before_oracle, after_oracle, probabilities

def assert_kickback(after_oracle, function, input_qubits):
    expected_size = math.sqrt(1 / (1 << (input_qubits + 1)))
    for x in range(1 << input_qubits):
        phase = -1 if function(x) else 1
        assert abs(after_oracle[(x << 1)] - phase * expected_size) < 1e-12
        assert abs(after_oracle[(x << 1) | 1] + phase * expected_size) < 1e-12

def classify_dj(table):
    size = len(table)
    input_qubits = size.bit_length() - 1
    if 1 << input_qubits != size:
        raise ValueError("truth table length must be a power of two")
    ones = sum(table)
    if ones not in (0, size, size // 2):
        raise ValueError("Deutsch-Jozsa promise violated")
    function = lambda x: table[x]
    _, kicked, probabilities = one_query_state(function, input_qubits)
    assert_kickback(kicked, function, input_qubits)
    measured_zero = probabilities[0] > 1.0 - 1e-12
    return "constant" if measured_zero else "balanced", probabilities

deutsch_tables = 0
for encoded in range(4):
    table = tuple((encoded >> x) & 1 for x in range(2))
    classification, probabilities = classify_dj(table)
    assert classification == ("constant" if sum(table) in (0, 2) else "balanced")
    deutsch_tables += 1
assert deutsch_tables == 4

promised_tables = 0
for encoded in range(1 << 8):
    table = tuple((encoded >> x) & 1 for x in range(8))
    if sum(table) in (0, 4, 8):
        classification, probabilities = classify_dj(table)
        assert classification == ("constant" if sum(table) in (0, 8) else "balanced")
        if classification == "balanced":
            assert probabilities[0] < 1e-12
        promised_tables += 1
assert promised_tables == 72

promise_rejected = False
try:
    classify_dj((1, 0, 0, 0, 0, 0, 0, 0))
except ValueError:
    promise_rejected = True
assert promise_rejected

bv_cases = 0
for input_qubits in range(1, 6):
    for secret in range(1 << input_qubits):
        for offset in (0, 1):
            function = lambda x, secret=secret, offset=offset: ((x & secret).bit_count() & 1) ^ offset
            _, kicked, probabilities = one_query_state(function, input_qubits)
            assert_kickback(kicked, function, input_qubits)
            assert abs(probabilities[secret] - 1.0) < 1e-12
            assert sum(value > 1e-12 for value in probabilities) == 1
            ledger = {
                "oracle_queries": 1,
                "hadamards": 2 * input_qubits + 1,
                "compiled_oracle_cnot": secret.bit_count(),
                "compiled_oracle_x": offset,
            }
            assert ledger["oracle_queries"] == 1
            assert ledger["hadamards"] == 2 * input_qubits + 1
            assert ledger["compiled_oracle_cnot"] + ledger["compiled_oracle_x"] == secret.bit_count() + offset
            bv_cases += 1

witness_secret = 0b1011
witness = lambda x: (x & witness_secret).bit_count() & 1
_, _, correct = one_query_state(witness, 4)
_, _, target_mutation = one_query_state(witness, 4, target_one=False)
_, _, double_query_mutation = one_query_state(witness, 4, query_count=2)
assert correct[witness_secret] > 1.0 - 1e-12
assert target_mutation[0] > 1.0 - 1e-12 and target_mutation[witness_secret] < 1e-12
assert double_query_mutation[0] > 1.0 - 1e-12 and double_query_mutation[witness_secret] < 1e-12
print(f"PASS: 28 one-query algorithms Deutsch={deutsch_tables} DJ={promised_tables} BV={bv_cases} witness_success={correct[witness_secret]:.1f} target_mutant_success={target_mutation[witness_secret]:.1f}")

Scope boundary

This chapter does not present these algorithms as practical application speedups.
It does not conflate deterministic and bounded-error classical query baselines or omit the promise.

Depth commitment. Three contracts, one common circuit derivation, two complete traces, and exhaustive tests.

Practice problem

Derive and run Bernstein–Vazirani for secret 1011, showing the phase after the oracle and every final output amplitude.

Deliverable: Symbolic n-bit derivation specialized to 1011, circuit, and deterministic count result.
Pass condition: The suite generates the secret oracle, asserts one oracle call and output 1011, and matches the amplitude table.

Verification record

Expected solution form. Walsh-Hadamard derivation plus exhaustive n≤5 regression tests.

Model answer. For secret s=1011, phase kickback gives amplitude sign (-1)^(s dot x). The final Hadamards implement the character orthogonality sum, leaving amplitude one on |1011> and zero on every other output; one oracle query recovers the string in the promise model.

Model result and check. CI reruns every secret and checks the submitted trace for 1011.

Acceptance test. The suite generates the secret oracle, asserts one oracle call and output 1011, and matches the amplitude table.

Companion work

Artifacts for this chapter

These entries resolve to checked-in local source. Commands are reproduced exactly from the chapter manifest, and source-embedded fixtures are exported as direct downloads.

algorithm fixture
Promise-algorithm circuit suite
Download fixture (.py)Verification record (.json)
Reproduce or test
python3 tools/validate_briefs.py --briefs data/editorial_briefs_00_35.json --from 0 --through 35 --check-rewritten-sources --execute-artifacts

Provenance

Sources and review

The load-bearing claims in the chapter are mapped inline to this registered source set. A citation supports only the bounded claim beside it.

External review: Open.

How review works Revision history Report or inspect errata

Book contents

Part IV. Protocols and Algorithms

Deutsch, Deutsch-Jozsa, and Bernstein-Vazirani

Three promises, three questions

One phase-oracle circuit pattern

Deutsch reads parity of two truth-table values

Bernstein–Vazirani turns phase into a hidden string

Query tables before runtime stories

Promise-algorithm circuit suite

Artifacts for this chapter

Promise-algorithm circuit suite

Sources and review

Cite this chapter

Three promises, three questions#

One phase-oracle circuit pattern#

Deutsch reads parity of two truth-table values#

Bernstein–Vazirani turns phase into a hidden string#

Query tables before runtime stories#

Promise-algorithm circuit suite#

Artifacts for this chapter

Promise-algorithm circuit suite

Sources and review

Prerequisites for this chapter

Next concepts from this chapter

Three promises, three questions

One phase-oracle circuit pattern

Deutsch reads parity of two truth-table values

Bernstein–Vazirani turns phase into a hidden string

Query tables before runtime stories

Promise-algorithm circuit suite