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\to\{0,1\}$, the standard oracle is

$$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 $|-\rangle=(|0\rangle-|1\rangle)/\sqrt2$. Since $X|-\rangle=-|-\rangle$,

$$\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\rangle=(-1)^{f(x)}|x\rangle$.

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)\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,

$$\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\rangle=\frac1{\sqrt2}\sum_{y=0}^1(-1)^{xy}|y\rangle.$$

Taking tensor products yields

$$H^{\otimes n}|x\rangle =\frac1{\sqrt{2^n}}\sum_y(-1)^{x\cdot y}|y\rangle,$$

where $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

$$\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$ inputs. Other functions are outside the problem. Starting in $|0^n\rangle$, apply Hadamards, the phase oracle, and Hadamards again. The amplitude of output y is

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

At $y=0^n$, this is the average of $(-1)^{f(x)}$. A constant function gives amplitude $+1$ or $-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$ 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}$. 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\cdot x$ for a hidden n-bit string s. The same circuit has

$$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$ if $y=s$, zero otherwise. One quantum oracle query recovers the whole string. Classically, querying each unit vector $e_j$ reveals $s_j$, requiring n deterministic queries in the worst case [13].

An added constant offset $b$ in $f(x)=s\cdot x\oplus b$ contributes only global phase $(-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:

$$\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.

9.6 Exercises