# Oracle algorithms: Deutsch, Deutsch–Jozsa, and Bernstein–Vazirani {#oracles}

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

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

![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.](figures/oracles.svg)

## 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 [@deutsch].

## 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.

## 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 [@dj].

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.

## 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 [@bv].

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.

::: {.lab #lab-oracles}
**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.
:::

## Exercises

:::: {.exercise #ex09-1}
**9.1.** Run Deutsch algebraically for $f(0)=1,f(1)=0$.

::: {.solution}

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

::::

:::: {.exercise #ex09-2}
**9.2.** For n=3 and BV secret 101, list the inputs where f is one.

::: {.solution}

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

::::

:::: {.exercise #ex09-3}
**9.3.** In Deutsch–Jozsa, suppose f is one on exactly one quarter of the domain. What is the all-zero output probability?

::: {.solution}

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

::::

:::: {.exercise #ex09-4}
**9.4.** How many independent classical samples make $2^{1-k}\le1/128$?

::: {.solution}

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

::::

:::: {.exercise #ex09-5}
**9.5.** Why does replacing $|-\rangle$ with $|+\rangle$ in the oracle target remove the useful kickback?

::: {.solution}

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

::::

