Home/Quantum Physics/Lessons/Deutsch’s Algorithm

▶

Deutsch’s Algorithm

Determine a function’s property with one query instead of two

intermediate2 qubits·~3 min

The question

Can you determine a property of a function with fewer queries than classically possible?

Before you start

Imagine you are given a mystery function f that takes one bit as input and returns one bit. The function is either constant (f(0) = f(1), both outputs the same) or balanced (f(0) $\neq =$ f(1), outputs differ). Classically, you need to check both inputs to know. This experiment shows that a quantum circuit can answer the question with just one evaluation of f.

What you will see

The trick works in three parts. First, prepare the helper qubit (q1) in a special state |−⟩ so that the oracle encodes its answer as a phase rather than a visible bit flip. Second, put the input qubit (q0) in superposition so both f(0) and f(1) are evaluated at once, but the results land as relative phases. Third, apply a final Hadamard that converts the phase pattern into a definite measurement: $∣0 ⟩$ means constant, $∣1 ⟩$ means balanced. In this experiment the oracle is a CNOT, which implements the balanced function f(x) = x.

The circuit

Circuit

Open in simulator →

▶ Try it in the simulator

Step-by-step walkthrough

Apply X to qubit 1 (the helper qubit)

Flip the helper qubit from $∣0 ⟩$ to $∣1 ⟩$ . This is the first step in preparing the eigenstate that enables phase kickback. The Bloch sphere for qubit 1 moves to the south pole.

∣0 ⟩ \otimes ∣1 ⟩

Apply H to both qubits

Hadamard on qubit 0 creates superposition of both inputs: $(∣0 ⟩ + ∣1 ⟩) / 2$ . Hadamard on qubit 1 converts $∣1 ⟩$ into |−⟩ = ( $∣0 ⟩$ − $∣1 ⟩ / 2$ , the eigenstate that enables kickback. Both qubits are now ready for the oracle (the black-box gate that encodes the function).

\frac{∣0 ⟩ + ∣1 ⟩}{2} \otimes \frac{∣0 ⟩ - ∣1 ⟩}{2}

Apply the oracle (CNOT)

The CNOT gate acts as the oracle for the balanced function f(x) = x. It applies X to qubit 1 when qubit 0 is $∣1 ⟩$ . Since qubit 1 is in |−⟩ (eigenstate of X), the target stays unchanged and the control's $∣1 ⟩$ branch picks up a −1 phase via kickback. The input qubit is now in ( $∣0 ⟩$ − $∣1 ⟩ / 2$ .

\frac{∣0 ⟩ - ∣1 ⟩}{2} \otimes \frac{∣0 ⟩ - ∣1 ⟩}{2}

Apply H to qubit 0 (input)

The final Hadamard converts the phase pattern on qubit 0 into a definite bit. H maps ( $∣0 ⟩$ − $∣1 ⟩ / 2$ to $∣1 ⟩$ . This means the function is balanced. If the function had been constant, the phase pattern would have been $(∣0 ⟩ + ∣1 ⟩) / 2$ , and H would have given $∣0 ⟩$ instead.

∣1 ⟩ \otimes \frac{∣0 ⟩ - ∣1 ⟩}{2}

Measure qubit 0

Read the input qubit. You get $∣1 ⟩$ with certainty, which means the function is balanced (f(0) $\neq =$ f(1)). A single quantum query determined a global property that classically requires two separate evaluations. There is no randomness in this outcome.

What to notice

The ancilla qubit (q1) is prepared in |−⟩ via X then H. This is the same eigenstate preparation you saw in the phase kickback experiment.
After the CNOT oracle, the helper qubit (ancilla) does not change. The oracle's answer appears as a phase on qubit 0.
The final Hadamard on qubit 0 converts the phase into a definite bit: $∣1 ⟩$ means balanced, $∣0 ⟩$ means constant.
The result is deterministic, not probabilistic. Every shot returns the same answer.

Tempting but wrong

It is tempting to think the algorithm computes f(0) and f(1) separately and then compares them. That is not what happens. The algorithm never learns the individual values of f(0) or f(1). It determines the global property (constant vs balanced) directly through interference, without revealing either individual output.

Expected result

Qubit 0 measures $∣1 ⟩$ with certainty on every shot, confirming the function is balanced. The ancilla qubit remains in |−⟩. This deterministic result from a single query is the quantum advantage.

Connection to the theory

This experiment brings together both the Phase Kickback lesson and the Deutsch's Algorithm lesson. It shows the full chain: eigenstate preparation enables kickback, superposition queries both inputs simultaneously, and interference extracts the global property. This same pattern (prepare, query, interfere) is the blueprint for every quantum algorithm.

Read the full lesson →

Test your understanding

In this experiment, the oracle is a CNOT. What type of function does it implement?

▶ Load in simulator ↗ Nielsen and Chuang, Quantum Computation and Quantum Information ↗ MIT OCW 8.06: quantum computing notes

Phase Kickback

Quantum Teleportation

← Back to all lessons