Deutsch-Jozsa algorithm

In plain terms

Here is the problem, and it is deliberately artificial. A black box computes a function that is promised to be one of two kinds: constant (same answer on every input) or balanced (half one answer, half the other). Your job: decide which, asking the box as few questions as possible.

Classically, certainty is expensive. In the worst case you must check just over half of all inputs -- exponentially many, as inputs grow. A quantum procedure asks once. It queries the box on a superposition of all inputs simultaneously and arranges the interference so that constant and balanced produce perfectly distinguishable outcomes.

Nobody has ever needed to solve this problem. That was never the point. The point was existence: here is a task where quantum provably beats classical. The door it opened, others walked through.

In CSD

One of the corpus's algorithm witnesses, and the corpus is precise about what such witnesses are for. They are scope evidence, not foundations: the algorithms presuppose the unitary-evolution pillar rather than support it, and their theorems concern circuit semantics and query counts, not where quantum mechanics comes from.

What they demonstrate is that the formalised machinery is the real thing -- strong enough to express and verify genuine algorithms with their amplitude bookkeeping intact, not a fragment tuned to make the foundational theorems pass. A reconstruction of quantum mechanics that could not run a quantum algorithm would invite a fair question.

Mathematically

One oracle query decides constant-versus-balanced with certainty; exact classical algorithms need 2^(n-1)+1 queries in the worst case. The honest footnote: allow the classical side a tiny error probability and a handful of random queries suffice -- the exponential separation is against EXACT classical computation. The problem was built to exhibit a separation, and does exactly that much.

The name

David Deutsch, born in Haifa in 1953, studied at Cambridge and Oxford and has remained at Oxford's Clarendon Laboratory in a famously unusual arrangement -- largely unsalaried, no teaching, working from home. The universal quantum computer is his 1985 construction; this algorithm came in 1992 with Richard Jozsa, later of Bristol and Cambridge.

Deutsch is also the most committed Everettian alive, and has argued in print that quantum computation is evidence for many worlds -- where else, he asks, would the computation happen? Most of the field declines the inference, and this programme, being single-trajectory, rejects it outright. The algorithm works either way, which is rather the point against the argument.