Deutsch's Algorithm

Historically the first algorithm to demonstrate a quantum speedup: with a single oracle query, decide whether a one-bit function is constant or balanced — where a classical deterministic algorithm must query twice. Deutsch's algorithm needs a single oracle query and is always correct.

The problem it solves

Consider a Boolean function f that takes one bit in and returns one bit out. There are only four such functions, and they fall into two classes:

We do not care which specific function f is — only which class it belongs to. Classically, knowing f(0) alone (or f(1) alone) settles nothing: you must learn both values and compare them. A classical deterministic algorithm therefore needs 2 queries; Deutsch's algorithm needs just 1 oracle query, and is always correct.

Intuition — asking for a global property in one question

The key realisation is that "constant vs. balanced" is a global property: it depends only on the parity (XOR) of the two values, f(0)⊕f(1). A constant function has parity 0; a balanced function has parity 1. A classical circuit can only probe the function at one point per query, so it can never read out this global parity directly.

A quantum circuit can feed both inputs through the oracle in superposition at once, then use interference to collect "the difference between the two points" into a single measurement. Instead of evaluating the function point by point, we ask directly: "are these two points the same or not?"

Why it works — phase kickback

The trick is to prepare the auxiliary qubit in the state |−⟩ = (|0⟩ − |1⟩)/√2 (the code does this with an x followed by an h). When the reversible oracle |x⟩|y⟩ → |x⟩|y⊕f(x)⟩ acts on |−⟩, something elegant happens: the XOR no longer flips the auxiliary qubit, but instead kicks back a phase of (−1)^f(x) onto the data qubit:

|x⟩|−⟩ → (−1)f(x) |x⟩|−⟩

So the data qubit goes from (|0⟩+|1⟩)/√2 to ((−1)f(0)|0⟩ + (−1)f(1)|1⟩)/√2. The relative phase between the two components encodes exactly the parity f(0)⊕f(1) we are after:

• If f(0)=f(1) (constant), the two phases agree and the state is proportional to |0⟩+|1⟩ = |+⟩.
• If f(0)≠f(1) (balanced), the two phases differ and the state is proportional to |0⟩−|1⟩ = |−⟩.

A final Hadamard on the data qubit maps |+⟩ back to |0⟩ and |−⟩ back to |1⟩. The measurement is therefore deterministic: read 0 for constant, read 1 for balanced.

The mechanism

What it shows — and what it doesn't

• A toy, but a genuine one. Deutsch's algorithm has no practical use of its own, but it is the first clean proof that quantum can solve a problem with fewer queries — the advantage is in query complexity, not runtime or memory.
• The advantage is deterministic. There is no probabilistic trade-off here: a classical deterministic algorithm needs 2 queries, quantum needs 1, and it is right every time.
• It generalises. Extended to an n-bit function (promised constant or balanced) it becomes the Deutsch–Jozsa algorithm: classically up to 2ⁿ⁻¹+1 queries in the worst case, quantum still just 1 — from exponential to constant. (This compares against deterministic/exact classical algorithms; a bounded-error randomized classical algorithm also needs only a constant number of queries.)
• It breaks nothing. The real legacy is phase kickback itself — Bernstein–Vazirani, Simon, and even Grover all reuse it.

The algorithm, step by step

1. Prepare the auxiliary qubit in |−⟩ (flip with x, then h).
2. Apply h to the data qubit to make the |+⟩ superposition.
3. Call the oracle; via phase kickback, the parity f(0)⊕f(1) is written into the data qubit's relative phase.
4. Apply h again to the data qubit, turning the phase difference into a computational 0 or 1.
5. Measure: 0 ⇒ constant, 1 ⇒ balanced.

Seeing it in code

Read it line by line against the theory above: x(q[1]) followed by h(q[1]) prepares the auxiliary qubit in |−⟩; h(q[0]) superposes the data qubit; when oracle_balanced=True is passed, the x.ctrl(q[0], q[1]) CNOT is the balanced oracle f(x)=x, and it is what triggers phase kickback; the closing h(q[0]) completes the interference so that mz(q[0]) reports the function's class deterministically.

The example only demonstrates the constant oracle f(x)=0 and the balanced oracle f(x)=x. To realize f(x)=1, add one x(q[1]) on the auxiliary qubit in the oracle; to realize f(x)=1⊕x, add an auxiliary flip on top of the CNOT. Whichever constant or balanced oracle you pick, the measurement still stabilizes to 0 (constant) or 1 (balanced) respectively.

import qalgora

@qalgora.kernel
def deutsch(oracle_balanced: bool):
    q = qalgora.qvector(2)
    x(q[1])
    h(q[0]); h(q[1])
    if oracle_balanced:          # f(x) = x  ->  CNOT oracle
        x.ctrl(q[0], q[1])
    h(q[0])
    mz(q[0])                     # 0 => constant, 1 => balanced

print(qalgora.sample(deutsch, True))    # balanced -> always 1
print(qalgora.sample(deutsch, False))   # constant -> always 0

References

• D. Deutsch, "Quantum theory, the Church-Turing principle and the universal quantum computer," Proc. R. Soc. Lond. A 400, 97-117 (1985). doi:10.1098/rspa.1985.0070