Deutsch Algorithm

Overview

Deutsch’s algorithm is the first “complete” quantum algorithm many people learn.

Problem: you are given black-box access to a function

$$f:\{0,1\}\to\{0,1\}.$$

You want to decide whether $f$ is:

• constant: $f(0)=f(1)$, or
• balanced: $f(0)\neq f(1)$.

Why it’s interesting:

• Classically, in the worst case you need two queries (evaluate $f(0)$ and $f(1)$).
• Deutsch’s algorithm solves it with one oracle query (in the ideal model), using interference.

Intuition

The trick is not “computing both values at once and reading them out.” Measurement won’t let you extract both $f(0)$ and $f(1)$ directly.

Instead, the algorithm:

1. queries the oracle in a superposition,
2. encodes information about $f(0)$ and $f(1)$ into relative phase,
3. uses interference to make the measurement outcome depend only on “same vs different.”

So the algorithm extracts a global property (constant vs balanced), not the full truth table.

Algorithm Structure

High-level steps:

1. Prepare two qubits in $|0\rangle|1\rangle$.
2. Apply H to both to create $|+\rangle| - \rangle$.
3. Query the oracle once.
4. Apply H to the first qubit.
5. Measure the first qubit:
   • outcome 0 means constant,
   • outcome 1 means balanced.

Formal Description

Oracle model

Use the standard reversible oracle

$$U_f|x\rangle|y\rangle = |x\rangle|y\oplus f(x)\rangle.$$

Key preparation: the phase-kickback target

Prepare the second qubit as

$$| - \rangle = \tfrac{1}{\sqrt{2}}(|0\rangle - |1\rangle).$$

If you apply $y\mapsto y\oplus f(x)$ to $| - \rangle$, the effect is a phase:

$$|x\rangle| - \rangle \xrightarrow{\;U_f\;} (-1)^{f(x)}|x\rangle| - \rangle.$$

So after the oracle, the second qubit returns to $| - \rangle$ and the function value is stored as a sign on the $|x\rangle$ branch.

Interference step

Start with

$$|0\rangle|1\rangle \xrightarrow{\;H\otimes H\;} |+\rangle| - \rangle = \tfrac{1}{\sqrt{2}}(|0\rangle+|1\rangle)\otimes| - \rangle.$$

Apply the oracle:

$$\tfrac{1}{\sqrt{2}}\big(|0\rangle+|1\rangle\big)| - \rangle \mapsto \tfrac{1}{\sqrt{2}}\big((-1)^{f(0)}|0\rangle + (-1)^{f(1)}|1\rangle\big)| - \rangle.$$

Now apply H to the first qubit. If $f(0)=f(1)$, the two phases match and interfere into $|0\rangle$. If $f(0)\neq f(1)$, they interfere into $|1\rangle$.

So measuring the first qubit tells you constant vs balanced.

Worked Example

Consider two cases.

Case A: constant function $f(0)=f(1)=0$

Then $(-1)^{f(0)}=(-1)^{f(1)}=1$, so the first-qubit state before the final H is

$$\tfrac{1}{\sqrt{2}}(|0\rangle+|1\rangle)=|+\rangle.$$

Applying H gives $H|+\rangle=|0\rangle$. So you measure 0 with certainty.

Case B: balanced function with $f(0)=0,\;f(1)=1$

Then the state before the final H is

$$\tfrac{1}{\sqrt{2}}(|0\rangle-|1\rangle)=| - \rangle.$$

Applying H gives $H| - \rangle=|1\rangle$. So you measure 1 with certainty.

Turtle Tip

Common Pitfalls

Quick Check

What’s Next

Deutsch’s algorithm solves the 1-bit version of a promise problem. Next we generalize the same interference idea to $n$ input bits: the Deutsch–Jozsa algorithm (constant vs balanced functions on many-bit inputs).