Chapter 9: Oracles and Quantum Parallelism

9.1 The Oracle Model: Black-Box Functions

Imagine you are given a function $f$ that takes bit strings as input and produces bit strings as output. You know nothing about the internal workings of $f$ - you can only call it on inputs of your choice and observe the outputs. This is the oracle model of computation.

Query complexity

In the oracle model, we measure the cost of an algorithm by the number of times it queries the oracle - not by the total number of computational steps. This measure is called query complexity (or oracle complexity). The central question is always: what is the minimum number of queries needed to determine some property of $f$?

Classical and quantum computers obey different rules about how they can call the oracle. A classical algorithm must query $f$ on one specific input at a time. A quantum algorithm, thanks to superposition, can effectively query $f$ on many inputs simultaneously - though extracting useful information from this "quantum parallelism" requires careful use of interference.

The standard oracle (bit oracle)

Quantum mechanics requires all operations (except measurement) to be reversible, as you learned in Chapter 3. A classical function $f(x)$ that maps inputs to outputs is generally not reversible. To make it reversible, we use an auxiliary register and define the oracle unitary $U_f$ as:

Here $\oplus$ denotes addition modulo 2 (XOR). The input register $|x\rangle$ passes through unchanged, while the output register $|y\rangle$ is XORed with $f(x)$. This operation is its own inverse: applying $U_f$ twice restores the original state, since $y \oplus f(x) \oplus f(x) = y$.

The phase oracle (phase kickback)

A remarkably useful trick emerges when we set the auxiliary qubit to $|-\rangle = \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)$. Applying $U_f$ to $|x\rangle|-\rangle$ gives:

The function value $f(x)$ has been "kicked back" into the phase of the input register. The auxiliary qubit is unchanged. This is called the phase oracle, and it is the form used by nearly every oracle-based quantum algorithm. Instead of writing the answer in a separate register, the answer appears as a phase factor $(-1)^{f(x)}$ on the input state.

To see why this works, consider what happens when the auxiliary qubit is $|-\rangle$:

When $f(x) = 0$, this gives $|x\rangle \cdot \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle) = |x\rangle |-\rangle$. When $f(x) = 1$, this gives $|x\rangle \cdot \frac{1}{\sqrt{2}}(|1\rangle - |0\rangle) = -|x\rangle |-\rangle$. In both cases: $(-1)^{f(x)} |x\rangle |-\rangle$.

Implementing oracles as QASM circuits

In practice, an oracle is a specific quantum circuit built from standard gates. In QASM, we define oracles using the gate keyword, which creates a named sub-circuit. For example, here is an oracle that computes $f(x) = x$ (the identity function on one bit):

gate oracle_identity input, ancilla {
  cx input, ancilla;
}

And here is an oracle that computes $f(x) = 1$ (the constant-one function):

gate oracle_const1 input, ancilla {
  x ancilla;
}

The gate keyword defines a reusable sub-circuit. The parameter names after the gate name are formal qubit parameters - they get bound to actual qubits when the gate is called. Throughout this chapter, we will define each oracle as a named gate, making the circuits modular and clear.

The four possible 1-bit oracles

To build intuition, let us enumerate every oracle for a function $f : \{0,1\} \to \{0,1\}$. There are exactly four such functions, and each has a simple circuit implementation:

The last oracle, $f(x) = \overline{x}$ (NOT of the input), uses a sandwich pattern: flip the input with X, apply the CNOT, then flip the input back. This is equivalent to a negative-controlled NOT, which applies X to the ancilla when the input is $|0\rangle$. In QASM, you could also write this using the negctrl modifier: negctrl @ x input, ancilla;. We will use explicit gate definitions throughout this chapter for maximum clarity.

9.2 Deutsch's Algorithm: The Simplest Quantum Advantage

We begin with the simplest possible problem that demonstrates a quantum advantage. This algorithm, discovered by David Deutsch in 1985, is historically the first quantum algorithm to outperform all classical competitors.

The problem

Consider a function $f : \{0, 1\} \to \{0, 1\}$ that takes a single bit as input and produces a single bit as output. There are exactly four such functions:

A function is constant if it gives the same output for every input, and balanced if it gives 0 for half the inputs and 1 for the other half (for a one-bit function, that means $f(0) \neq f(1)$). The task: determine whether $f$ is constant or balanced.

Classical solution

Classically, you must evaluate $f$ on both inputs: first query $f(0)$, then query $f(1)$, and compare. That requires 2 queries. There is no shortcut - with only one query, you learn $f(0)$ or $f(1)$ but cannot compare them.

Quantum solution: 1 query

Deutsch's algorithm determines whether $f$ is constant or balanced using a single query. The circuit is:

1. Prepare two qubits: the input qubit in $|0\rangle$ and the ancilla in $|1\rangle$.
2. Apply $H$ to both qubits. The input becomes $|+\rangle = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$ and the ancilla becomes $|-\rangle = \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)$.
3. Apply the oracle $U_f$.
4. Apply $H$ to the input qubit.
5. Measure the input qubit.

Step-by-step derivation

After step 2 (Hadamards on both qubits):

After step 3 (oracle application). Using phase kickback, $U_f|x\rangle|-\rangle = (-1)^{f(x)}|x\rangle|-\rangle$:

Factor out $(-1)^{f(0)}$ from the input register:

Now there are two cases:

• If $f$ is constant, then $f(0) \oplus f(1) = 0$, so the input qubit is in state $|+\rangle$.
• If $f$ is balanced, then $f(0) \oplus f(1) = 1$, so the input qubit is in state $|-\rangle$.

After step 4 (Hadamard on input qubit): Since $H|+\rangle = |0\rangle$ and $H|-\rangle = |1\rangle$:

• Constant: input qubit is $|0\rangle$.
• Balanced: input qubit is $|1\rangle$.

Step 5 (measurement): Measuring the input qubit gives 0 for constant and 1 for balanced - with certainty, in a single query.

Try it: constant oracle

Here is Deutsch's algorithm with the constant oracle $f(x) = 0$. This oracle does nothing to the ancilla (the identity), so the input qubit should measure as $|0\rangle$ every time, indicating "constant."

You should see outcome 0 with 100% probability. The algorithm correctly identifies the oracle as constant.

What about the other constant function, $f(x) = 1$? Try modifying the oracle above to include x q1; inside the gate body. The X gate flips the ancilla unconditionally, implementing $f(x) = 1$. You should still see outcome 0 - because both constant functions produce the same result (constant), the algorithm does not distinguish between $f(x) = 0$ and $f(x) = 1$. It only detects whether $f$ is constant or balanced.

Try it: balanced oracle

Now try Deutsch's algorithm with the balanced oracle $f(x) = x$. This oracle is just a CNOT gate. The input qubit should measure as $|1\rangle$ every time, indicating "balanced."

You should see outcome 1 with 100% probability. One query was enough to determine that this function is balanced.

Interactive: Deutsch's Algorithm Step-Through

Walk through Deutsch's algorithm for all four possible oracles. At each gate, the full two-qubit state vector is shown. Watch how phase kickback encodes $f(0) \oplus f(1)$ into the relative phase of the input qubit.

9.3 Deutsch-Jozsa: Scaling Up

Deutsch's algorithm handles a one-bit input, which is a toy problem. In 1992, David Deutsch and Richard Jozsa generalized it to $n$-bit inputs, producing the first demonstration of an exponential quantum speedup in the oracle model.

The problem

Given a function $f : \{0, 1\}^n \to \{0, 1\}$, promised to be either:

• Constant: $f(x) = 0$ for all $x$, or $f(x) = 1$ for all $x$.
• Balanced: $f(x) = 0$ for exactly half the inputs, and $f(x) = 1$ for the other half.

Determine which type $f$ is.

Classical query complexity

A deterministic classical algorithm needs up to $2^{n-1} + 1$ queries in the worst case. To see why: after querying $2^{n-1}$ inputs and finding them all returning the same value, $f$ could still be balanced (the other half could return the opposite value). One more query is needed to break the tie. This is exponential in $n$.

The quantum circuit

The Deutsch-Jozsa algorithm uses exactly the same structure as Deutsch's algorithm, scaled to $n$ input qubits:

1. Prepare $n$ input qubits in $|0\rangle^{\otimes n}$ and one ancilla in $|1\rangle$.
2. Apply $H$ to all $n+1$ qubits.
3. Apply the oracle $U_f$.
4. Apply $H$ to the $n$ input qubits.
5. Measure the $n$ input qubits.

Why it works

After the Hadamards in step 2, the input register is in the uniform superposition:

After the oracle (using phase kickback), this becomes:

After applying $H^{\otimes n}$ to the input register, the amplitude of the all-zeros state $|0\rangle^{\otimes n}$ is:

If $f$ is constant, all $2^n$ terms $(-1)^{f(x)}$ are equal (all $+1$ or all $-1$), and the magnitude of this sum is $|\pm 2^n / 2^n| = 1$. The probability of measuring $|00\ldots0\rangle$ is $1$.

If $f$ is balanced, exactly $2^{n-1}$ terms are $+1$ and $2^{n-1}$ are $-1$. The sum cancels to 0, so the probability of measuring $|00\ldots0\rangle$ is $0$. By normalization, at least one other basis state must have nonzero amplitude, so measurement will always yield a string other than all zeros.

The decision rule is therefore simple: if the measurement result is $|00\ldots0\rangle$, output "constant"; otherwise, output "balanced." This is deterministic and requires just one oracle query.

Try it: 2-bit balanced oracle

Here is the Deutsch-Jozsa algorithm for $n = 2$ with a balanced oracle that computes $f(x_0, x_1) = x_0 \oplus x_1$. This function outputs 0 on inputs 00 and 11, and outputs 1 on inputs 01 and 10 - perfectly balanced. Since $f$ is balanced, the measurement should never produce the all-zeros outcome $|00\rangle$.

You should see the outcome $|11\rangle$ with 100% probability - never $|00\rangle$. The algorithm correctly identifies the function as balanced.

Exercise: build a Deutsch-Jozsa circuit

Below is a Deutsch-Jozsa circuit template for $n = 2$. The oracle is already defined for you: it computes $f(x_0, x_1) = x_0$ (balanced - outputs 0 on half the inputs and 1 on the other half). Complete the circuit by adding the Hadamard gates and measurement. If your circuit is correct, the measurement result will never be $|00\rangle$.

9.4 Bernstein-Vazirani: Finding Hidden Strings

The Deutsch-Jozsa algorithm answers a yes/no question about $f$. The Bernstein-Vazirani algorithm (1993) goes further: it extracts specific information from the oracle in a single query.

The problem

You are given an oracle that computes $f(x) = s \cdot x \pmod{2}$, where $s$ is a secret $n$-bit string and $s \cdot x = s_0 x_0 \oplus s_1 x_1 \oplus \cdots \oplus s_{n-1} x_{n-1}$ is the bitwise inner product modulo 2. Your task: find $s$.

Classical query complexity

Classically, each query reveals one bit of $s$. To find all $n$ bits, you need $n$ queries (you can query $f$ on each standard basis vector $e_i = 00\ldots010\ldots0$ with a 1 in position $i$, and $f(e_i) = s_i$). This is optimal - you cannot do better than $n$ queries classically.

Quantum: 1 query

The Bernstein-Vazirani circuit is identical to the Deutsch-Jozsa circuit. The only difference is the oracle and what we measure:

1. Prepare $|0\rangle^{\otimes n}|1\rangle$.
2. Apply $H$ to all $n+1$ qubits.
3. Apply the oracle $U_f$.
4. Apply $H^{\otimes n}$ to the input qubits.
5. Measure the input qubits. The result is $s$.

Why it works

After the oracle with phase kickback, the input register is in the state:

Applying $H^{\otimes n}$ transforms this into $|s\rangle$. This follows from the identity:

which holds because the $n$-qubit Hadamard acts as $H^{\otimes n}|y\rangle = \frac{1}{\sqrt{2^n}} \sum_x (-1)^{x \cdot y}|x\rangle$, and the Hadamard is its own inverse ($H^2 = I$). The state after the oracle is exactly $H^{\otimes n}|s\rangle$, so applying $H^{\otimes n}$ again yields $|s\rangle$.

More explicitly, the amplitude of basis state $|z\rangle$ after the final Hadamard layer is:

When $z = s$, every term in the sum equals $(-1)^0 = 1$, giving amplitude $2^n / 2^n = 1$. When $z \neq s$, the exponent $(s \oplus z) \cdot x$ takes values 0 and 1 equally often over all $x$, and the sum cancels to 0. So the only state with nonzero amplitude is $|s\rangle$.

Building the oracle

The oracle for $f(x) = s \cdot x \pmod{2}$ is straightforward: for each bit $s_i = 1$, apply a CNOT from input qubit $i$ to the ancilla. For example, if $s = 101$, the oracle is:

gate bv_oracle q0, q1, q2, anc {
  cx q0, anc;
  cx q2, anc;
}

Each CNOT contributes $x_i$ to the XOR sum in the ancilla, which (via phase kickback) becomes $(-1)^{s \cdot x}$ in the phase.

Try it: 3-bit secret string $s = 101$

Run the Bernstein-Vazirani algorithm to find the secret string $s = 101$. You should see the measurement outcome $|101\rangle$ with 100% probability.

The measurement yields $|101\rangle$ with certainty - the secret string revealed in a single query. A classical algorithm would need 3 separate queries.

9.5 Simon's Algorithm: Exponential Separation

The algorithms so far have demonstrated quantum advantages in the oracle model, but some of those advantages vanish when probabilistic classical algorithms are allowed (as with Deutsch-Jozsa). Simon's algorithm, published by Daniel Simon in 1994, achieves something stronger: an exponential speedup over all classical algorithms, including probabilistic ones. It is also historically significant as the direct inspiration for Shor's factoring algorithm.

The problem

Given a function $f : \{0,1\}^n \to \{0,1\}^n$ with the promise that there exists a secret string $s \in \{0,1\}^n$ such that for all $x, y$:

In other words, $f(x) = f(x \oplus s)$ for all $x$, and $f$ is otherwise one-to-one. If $s = 0^n$, then $f$ is a one-to-one function. If $s \neq 0^n$, then $f$ is exactly two-to-one, with each pair of colliding inputs differing by $s$. The task: find $s$.

Classical query complexity

Any classical algorithm - deterministic or probabilistic - requires $\Omega(2^{n/2})$ queries. The intuition comes from the birthday paradox: to find a collision $f(x) = f(y)$ with $x \neq y$ (which reveals $s = x \oplus y$), you need to evaluate $f$ on roughly $\sqrt{2^n} = 2^{n/2}$ inputs before a collision becomes likely.

Quantum: O(n) queries

Simon's algorithm finds $s$ using only $O(n)$ oracle queries. The algorithm has a quantum subroutine that is repeated $O(n)$ times, followed by classical post-processing.

The quantum subroutine

Each iteration of the quantum subroutine works as follows:

1. Prepare two $n$-qubit registers, both initialized to $|0\rangle^{\otimes n}$.
2. Apply $H^{\otimes n}$ to the first register.
3. Apply the oracle: $|x\rangle|0\rangle \to |x\rangle|f(x)\rangle$.
4. Apply $H^{\otimes n}$ to the first register.
5. Measure the first register. The result is a string $y$ satisfying $y \cdot s = 0 \pmod{2}$.

Why it works

After step 2, the state is:

After step 3 (oracle application):

Because $f(x) = f(x \oplus s)$, the terms with the same $f$-value pair up. If we consider the state conditioned on the second register having some value $f(x_0)$, the first register is in the state $\frac{1}{\sqrt{2}}(|x_0\rangle + |x_0 \oplus s\rangle)$. (When $s = 0^n$, the state is simply $|x_0\rangle$ with no pairing.)

After step 4, applying $H^{\otimes n}$ to the first register, the amplitude for measuring outcome $y$ in the first register involves the sum:

This is nonzero only when $(-1)^{y \cdot s} = 1$, i.e., when $y \cdot s = 0 \pmod{2}$. So every measurement outcome $y$ satisfies the constraint $y \cdot s \equiv 0 \pmod{2}$.

Classical post-processing

After repeating the quantum subroutine $O(n)$ times, we collect $n - 1$ linearly independent equations of the form $y_i \cdot s = 0 \pmod{2}$. This is a system of linear equations over $\mathbb{F}_2$ (the field with two elements), which can be solved efficiently by Gaussian elimination to find $s$.

For a concrete example with $n = 3$ and $s = 110$: suppose the quantum subroutine produces the outcomes $y_1 = 001$ and $y_2 = 110$. These give us the constraints:

• $y_1 \cdot s = 0 \cdot s_0 + 0 \cdot s_1 + 1 \cdot s_2 = s_2 = 0 \pmod{2}$
• $y_2 \cdot s = 1 \cdot s_0 + 1 \cdot s_1 + 0 \cdot s_2 = s_0 \oplus s_1 = 0 \pmod{2}$

From the first equation, $s_2 = 0$. From the second, $s_0 = s_1$. Combined with the knowledge that $s \neq 000$ (since $f$ is two-to-one, not one-to-one), we get $s = 110$. Two quantum queries plus classical linear algebra recovered the secret period.

Connection to Shor's algorithm

Simon's algorithm was the direct inspiration for Shor's factoring algorithm (Chapter 11). Both algorithms share the same high-level structure:

1. Use quantum superposition to evaluate a function on all inputs simultaneously.
2. The function has a hidden periodic structure (for Simon: $f(x) = f(x \oplus s)$; for Shor: $f(x) = a^x \bmod N$ is periodic).
3. Apply a quantum transform to the input register to extract information about the period.
4. Use classical post-processing to determine the period from the quantum measurement results.

The key difference is that Simon's problem has an abelian group structure over $\mathbb{Z}_2^n$ (XOR), while Shor's problem has a cyclic group structure over $\mathbb{Z}_r$. This led Shor to replace the Hadamard transform (the Fourier transform over $\mathbb{Z}_2^n$) with the Quantum Fourier Transform (the Fourier transform over $\mathbb{Z}_N$), which you will study in Chapter 10. Both are instances of the hidden subgroup problem, a unifying framework discussed further in Chapter 31.

Constructing a Simon oracle

Building an oracle for Simon's problem is more involved than for previous algorithms because $f$ maps $n$ bits to $n$ bits and must satisfy $f(x) = f(x \oplus s)$ for a given secret $s$. A standard construction works in two steps:

1. Copy the input register to the output register (using CNOT gates): this computes $f(x) = x$.
2. Pick any bit position $i$ where $s_i = 1$. Conditioned on $x_i = 1$, XOR $s$ into the output register.

This gives $f(x) = x$ when $x_i = 0$, and $f(x) = x \oplus s$ when $x_i = 1$. Since $x$ and $x \oplus s$ always differ in bit $i$ (because $s_i = 1$), the two cases partition all inputs into pairs with $f(x) = f(x \oplus s)$, exactly as Simon's promise requires.

For $s = 11$ with $n = 2$, we can build a compact oracle. We need $f(00) = f(11)$ and $f(01) = f(10)$. A valid function is $f(x_0 x_1) = (0, x_0 \oplus x_1)$:

Indeed, $f(00) = f(11) = 00$ and $f(01) = f(10) = 01$, with $00 \oplus 11 = 01 \oplus 10 = 11 = s$. The oracle circuit computes $\text{out}_1 = x_0 \oplus x_1$ using two CNOT gates and leaves $\text{out}_0 = 0$.

Let us run Simon's algorithm for $n = 2$ with this oracle. Each run of the quantum subroutine produces a string $y$ with $y \cdot s = 0 \pmod{2}$. For $s = 11$, the constraint $y_0 \oplus y_1 = 0$ means we should see only $|00\rangle$ and $|11\rangle$ in the first register.

The oracle applies two CNOTs to compute $\text{out}_1 = x_0 \oplus x_1$, which implements the function from the truth table. Note that Simon's algorithm does not use phase kickback like the previous algorithms - it uses the standard oracle that writes $f(x)$ into the output register. The entanglement between input and output registers, combined with the Hadamard transform, produces the linear constraints on $s$.

You should see approximately 50% $|00\rangle$ and 50% $|11\rangle$ in the measurement. The outcome $|11\rangle$ tells us $y = 11$, which satisfies $y \cdot s = 1 \oplus 1 = 0$ for $s = 11$. The outcome $|00\rangle$ is the trivial solution $0 \cdot s = 0$ and provides no information. After collecting the nontrivial constraint $y = 11$ (meaning $s_0 \oplus s_1 = 0$, so $s_0 = s_1$), we know $s \in \{00, 11\}$. Since the function is two-to-one (not one-to-one), $s \neq 00$, giving us $s = 11$.

In general, for $n$-bit Simon's problem, we would repeat the quantum subroutine until we collect $n - 1$ linearly independent constraint vectors, then solve the resulting linear system. For $n = 2$, a single nontrivial measurement suffices.

Summary of oracle algorithms

The following table summarizes the four algorithms covered in this chapter:

All four algorithms share the same core structure: prepare a superposition, apply the oracle (with phase kickback), apply Hadamard transforms, and measure. The pattern $H^{\otimes n} \to U_f \to H^{\otimes n} \to \text{Measure}$ is the prototype for all oracle-based quantum algorithms.

Looking ahead

The algorithms in this chapter reveal the fundamental toolkit of quantum speedups: superposition allows querying a function on many inputs at once, phase kickback encodes function values into quantum phases, and the Hadamard transform (or more generally, a Fourier transform) converts phase information into measurable amplitudes through interference.

In Chapter 10, you will study the Quantum Fourier Transform (QFT), which generalizes the Hadamard transform from the group $\mathbb{Z}_2^n$ to arbitrary cyclic groups $\mathbb{Z}_N$. This generalization is exactly what Shor needed to move from Simon's XOR-periodic functions to the modular arithmetic at the heart of integer factoring. Chapter 11 will then show how Shor's algorithm combines the QFT with modular exponentiation to break RSA encryption - a direct descendant of the oracle algorithms you have just mastered.

Grover's search algorithm (Chapter 12) takes a different approach: rather than exploiting hidden structure in $f$, it amplifies the amplitude of a single marked item through repeated applications of the oracle and a "diffusion" operator. Where the algorithms in this chapter achieve superpolynomial speedups for structured problems, Grover achieves a quadratic speedup for the unstructured search problem - provably the best possible for any quantum algorithm.

Interactive: Deutsch-Jozsa Explorer

Use Goqu's built-in Deutsch-Jozsa implementation to explore how the algorithm scales. No matter how many qubits you use, the algorithm determines whether the oracle is constant or balanced with just one query.

Interactive: Bernstein-Vazirani Explorer

Bernstein-Vazirani's algorithm recovers a secret bitstring $s$ hidden inside an oracle $f(x) = s \cdot x \pmod{2}$ using just one query. Enter a secret number below (interpreted as a binary string) and watch the algorithm recover it.

Interactive: Simon's Algorithm Walkthrough

Simon's algorithm finds a hidden period $s$ such that $f(x) = f(x \oplus s)$ for a two-to-one function. It requires multiple quantum rounds to build a system of linear equations, which are then solved by Gaussian elimination to reveal $s$.