Oracles and Black-Box Functions

algorithmsReading-focused

10 min read

Oracles and Black-Box Functions

What a quantum oracle is, why it has to be reversible, and how to build one from a classical boolean function.

Suggested before this lesson

Deutsch-Jozsa and Bernstein-Vazirani, the two algorithms this track builds toward, are both phrased as "you're given a black-box function $f$ : figure out a property of it using as few queries as possible." Before either algorithm makes sense, it's worth being precise about what that black box actually is as a circuit.

The Oracle Convention

A classical function $f:\{0,1\}^n \to \{0,1\}$ isn't automatically something you can turn into a quantum gate: quantum gates are unitary, which means reversible: you must always be able to undo them. A generic classical function usually isn't reversible (many inputs can map to the same output), so you can't just "compute $f(x)$ and overwrite the answer."

The standard fix is to never overwrite anything: XOR the result into a fresh ancilla qubit instead:

$U_f: |x\rangle|y\rangle \longrightarrow |x\rangle|y \oplus f(x)\rangle$

$x$ (the input register) passes through unchanged. $y$ (the ancilla) comes out XORed with $f(x)$ . This is always reversible (applying $U_f$ twice XORs $f(x)$ back out), no matter what $f$ itself does, which is exactly why it works as a gate even when $f$ isn't invertible.

U_{f}

as a Black Box

This is the shape every oracle in this course has: query register in on the left, unchanged on the right; ancilla in on the left, XORed with $f(x)$ on the right.

Black Box

Building One From $X$ and $CX$

For any $f$ that's a linear function of its inputs, $f(x_0, x_1, \ldots) = x_0 \oplus x_1 \oplus \ldots$ (XOR together whichever inputs the function actually depends on), the oracle is just a $CX$ from each relevant input qubit into the ancilla. Each $CX$ flips the ancilla exactly when that one input is 1, and XOR is exactly "flip an odd number of times."

Take $f(x_0, x_1) = x_0 \oplus x_1$ over 2 input qubits, with qubit 2 as the ancilla:

U_{f}

for

f (x_{0}, x_{1}) = x_{0} \oplus x_{1}

Set the input qubits (0, 1) and watch qubit 2 in the Exact State table: it lands on

|0\rangle

when the two inputs agree and

|1\rangle

when they differ, exactly XOR.

Circuit

Step through the circuit: after gate 2 of 2

3 / 3

Exact State

Basis state	Re	Probability
$∣000 ⟩$	1.000	100.0%
$∣001 ⟩$	0	0.0%
$∣010 ⟩$	0	0.0%
$∣011 ⟩$	0	0.0%
$∣100 ⟩$	0	0.0%
$∣101 ⟩$	0	0.0%
$∣110 ⟩$	0	0.0%
$∣111 ⟩$	0	0.0%

This kind of $f$ (depends on some but not all inputs in a perfectly balanced way) is called a balanced function: exactly half of all possible inputs give $f(x)=0$ and half give $f(x)=1$ . The other extreme is a constant function, $f(x) = 0$ for every $x$ (an oracle that does nothing at all) or $f(x)=1$ for every $x$ (an oracle that's just $X$ on the ancilla, ignoring the input register completely). Constant vs. balanced is exactly the distinction Deutsch-Jozsa is built to tell apart.

Exercise

Build the oracle for

f(x_0, x_1) = x_0 \oplus x_1

on a 3-qubit circuit, with qubit 2 as the ancilla:

CX

from qubit 0 into qubit 2, then

CX

from qubit 1 into qubit 2.

Live preview of the circuit detected in your code

Need a hint?

Check your understanding

Why does the oracle convention XOR the answer into a separate ancilla instead of just computing

f(x)

directly into some output qubit that starts at

|0\rangle

It's purely a stylistic convention with no real reason.

Quantum gates must be reversible (unitary), and XOR-into-an-ancilla is always reversible no matter what

f

is, even when

f

itself loses information (many

x

map to the same output).

It makes the circuit shorter.

It's only needed when

f

is balanced, not when it's constant.

The Oracle Convention

A classical function

f:\{0,1\}^n \to \{0,1\}

isn't automatically something you can turn into a quantum gate: quantum gates are unitary, which means reversible: you must always be able to undo them. A generic classical function usually isn't reversible (many inputs can map to the same output), so you can't just "compute

f(x)

and overwrite the answer."

The standard fix is to never overwrite anything: XOR the result into a fresh ancilla qubit instead:

U_f: |x\rangle|y\rangle \longrightarrow |x\rangle|y \oplus f(x)\rangle

x

(the input register) passes through unchanged.

y

(the ancilla) comes out XORed with

f(x)

. This is always reversible (applying

U_f

twice XORs

f(x)

back out), no matter what

f

itself does, which is exactly why it works as a gate even when

f

isn't invertible.

U_{f}

as a Black Box

This is the shape every oracle in this course has: query register in on the left, unchanged on the right; ancilla in on the left, XORed with $f(x)$ on the right.

Black Box

Building One From

X

and

CX

For any

f

that's a linear function of its inputs,

f(x_0, x_1, \ldots) = x_0 \oplus x_1 \oplus \ldots

(XOR together whichever inputs the function actually depends on), the oracle is just a

CX

from each relevant input qubit into the ancilla. Each

CX

flips the ancilla exactly when that one input is 1, and XOR is exactly "flip an odd number of times."

Take

f(x_0, x_1) = x_0 \oplus x_1

over 2 input qubits, with qubit 2 as the ancilla:

Python

U_{f}

for

f (x_{0}, x_{1}) = x_{0} \oplus x_{1}