Skip to content

CHAPTER 09

# Oracle algorithms: Deutsch, Deutsch–Jozsa, and Bernstein–Vazirani

Learning goals. Define a reversible oracle, derive phase kickback, and compare three algorithms without confusing query complexity with runtime.

## 9.1 A black box is an explicit resource assumption

For a Boolean function f:{0,1}n→{0,1}f:\{0,1\}^n\to\{0,1\}, the standard oracle is

U f|x⟩|y⟩=|x⟩|y⊕f(x)⟩.U_f|x\rangle|y\rangle=|x\rangle|y\oplus f(x)\rangle.

It preserves x and is reversible even when f is not. An oracle problem counts calls to this operation as units. A physical implementation must still compute f coherently, route its controls, and uncompute temporary work. A black-box separation can teach a mechanism without being a practical application.

Prepare the target in |−⟩=(|0⟩−|1⟩)/2|-\rangle=(|0\rangle-|1\rangle)/\sqrt2. Since X|−⟩=−|−⟩X|-\rangle=-|-\rangle,

U f|x⟩|−⟩=|x⟩|f(x)⟩−|x⟩|1⊕f(x)⟩2=(−1)f(x)|x⟩|−⟩.\begin{aligned} U_f|x\rangle|-\rangle &=\frac{|x\rangle|f(x)\rangle-|x\rangle|1\oplus f(x)\rangle}{\sqrt2}\\ &=(-1)^{f(x)}|x\rangle|-\rangle. \end{aligned}

The target returns to the same state and the phase appears on the input branch. This phase kickback implements O f|x⟩=(−1)f(x)|x⟩O_f|x\rangle=(-1)^{f(x)}|x\rangle.

Figure 9.1. A shared circuit pattern for the three oracle algorithms. The work qubit begins in 1 and becomes minus after H; the reversible oracle imprints its function as a phase on the input register.

## 9.2 Deutsch’s one-bit problem

There are four one-bit Boolean functions. Two are constant; two are balanced. The task is to determine f(0)⊕f(1)f(0)\oplus f(1). One classical deterministic query cannot distinguish a constant function from a balanced one agreeing at the queried input.

Prepare |+⟩|−⟩|+\rangle|-\rangle, query, and apply H to the first qubit. Ignoring the unchanged target,

(−1)f(0)|0⟩+(−1)f(1)|1⟩2→H(−1)f(0)+(−1)f(1)2|0⟩+(−1)f(0)−(−1)f(1)2|1⟩.\frac{(-1)^{f(0)}|0\rangle+(-1)^{f(1)}|1\rangle}{\sqrt2} \xrightarrow H \frac{(-1)^{f(0)}+(-1)^{f(1)}}2|0\rangle +\frac{(-1)^{f(0)}-(-1)^{f(1)}}2|1\rangle.

If the values agree, the second amplitude cancels and result 0 is certain. If they differ, the first amplitude cancels and result 1 is certain. The algorithm reveals parity, not both function values. One query’s information is reorganized through interference [11].

## 9.3 The Hadamard transform on bit strings

For one bit,

H|x⟩=1 2∑y=0 1(−1)x y|y⟩.H|x\rangle=\frac1{\sqrt2}\sum_{y=0}^1(-1)^{xy}|y\rangle.

Taking tensor products yields

H⊗n|x⟩=1 2 n∑y(−1)x⋅y|y⟩,H^{\otimes n}|x\rangle =\frac1{\sqrt{2^n}}\sum_y(-1)^{x\cdot y}|y\rangle,

where x⋅y=⨁j x j y j x\cdot y=\bigoplus_jx_jy_j is a binary dot product. The exponent may be computed modulo two. This is the Fourier transform of the group of bit strings under XOR.

The useful cancellation identity is

∑x(−1)x⋅z={2 n,z=0 n,0,z≠0 n.\sum_x(-1)^{x\cdot z} =\begin{cases}2^n,&z=0^n,\\0,&z\ne0^n.\end{cases}

If a bit of z is one, pair each x with the string obtained by flipping that bit. The two terms have opposite signs and cancel. This pairing proof is the engine behind both algorithms below.

## 9.4 Deutsch–Jozsa and its promise

The promise is that f is either constant or balanced over all 2 n 2^n inputs. Other functions are outside the problem. Starting in |0 n⟩|0^n\rangle, apply Hadamards, the phase oracle, and Hadamards again. The amplitude of output y is

A(y)=1 2 n∑x(−1)f(x)+x⋅y.A(y)=\frac1{2^n}\sum_x(-1)^{f(x)+x\cdot y}.

At y=0 n y=0^n, this is the average of (−1)f(x)(-1)^{f(x)}. A constant function gives amplitude +1+1 or −1-1. A balanced function gives zero. Therefore observing all zeros means constant and any nonzero output means balanced, under the promise [12].

An exact deterministic classical algorithm can require 2 n−1+1 2^{n-1}+1 queries: after seeing the same value on half the domain, both cases remain possible. But a randomized classical algorithm can distinguish the cases with bounded error using only a number of samples logarithmic in the inverse error tolerance. For k independent uniformly sampled inputs to a balanced function, the probability all answers match is 2 1−k 2^{1-k}. The dramatic exact deterministic comparison is not an exponential separation from bounded-error classical computation.

## 9.5 Bernstein–Vazirani

Now promise f s(x)=s⋅x f_s(x)=s\cdot x for a hidden n-bit string s. The same circuit has

A(y)=1 2 n∑x(−1)s⋅x+x⋅y=1 2 n∑x(−1)x⋅(s⊕y).A(y)=\frac1{2^n}\sum_x(-1)^{s\cdot x+x\cdot y} =\frac1{2^n}\sum_x(-1)^{x\cdot(s\oplus y)}.

The cancellation identity gives A(y)=1 A(y)=1 if y=s y=s, zero otherwise. One quantum oracle query recovers the whole string. Classically, querying each unit vector e j e_j reveals s j s_j, requiring n deterministic queries in the worst case [13].

An added constant offset b b in f(x)=s⋅x⊕b f(x)=s\cdot x\oplus b contributes only global phase (−1)b(-1)^b. This circuit still returns s but does not identify b. This is a concrete example of a global phase carrying no accessible measurement information.

The BV input state after the oracle actually factors:

1 2 n∑x(−1)s⋅x|x⟩=⨂j|0⟩+(−1)s j|1⟩2.\frac1{\sqrt{2^n}}\sum_x(-1)^{s\cdot x}|x\rangle =\bigotimes_j\frac{|0\rangle+(-1)^{s_j}|1\rangle}{\sqrt2}.

Entanglement among these input qubits is unnecessary for this query advantage. Claims that every speedup requires entanglement in every stage would therefore be misleading.

Laboratory L13 — Oracle interference. Choose Deutsch’s complete truth table, a promised Deutsch–Jozsa instance, or a BV secret. Inspect preparation, oracle phases, final amplitudes, and sampled results. The DJ panel uses a stated family of balanced parity functions; the proof applies to every promised balanced function.

## 9.6 Exercises

9.1. Run Deutsch algebraically for f(0)=1,f(1)=0 f(0)=1,f(1)=0.

Show solution / guidance

The queried state is (−|0⟩+|1⟩)/2=−|−⟩(-|0\rangle+|1\rangle)/\sqrt2=-|-\rangle. H gives −|1⟩-|1\rangle, so result 1 is certain.

9.2. For n=3 and BV secret 101, list the inputs where f is one.

Show solution / guidance

f(x)=x 0⊕x 2 f(x)=x_0\oplus x_2. The inputs are 001, 011, 100, 110. Their amplitudes acquire minus signs; the final result is 101.

9.3. In Deutsch–Jozsa, suppose f is one on exactly one quarter of the domain. What is the all-zero output probability?

Show solution / guidance

The amplitude is (3/4)−(1/4)=1/2(3/4)-(1/4)=1/2, giving probability 1/4 1/4. This is outside the promise, so the circuit is not an exact classifier for this case.

9.4. How many independent classical samples make 2 1−k≤1/128 2^{1-k}\le1/128?

Show solution / guidance

1−k≤−7 1-k\le-7, so k=8 suffices. This bound assumes uniformly random inputs and the exact promise.

9.5. Why does replacing |−⟩|-\rangle with |+⟩|+\rangle in the oracle target remove the useful kickback?

Show solution / guidance

X|+⟩=|+⟩X|+\rangle=|+\rangle, so both f values leave the target and phase unchanged. The input returns to |0 n⟩|0^n\rangle after the final Hadamards.

IN THIS CHAPTER