Deutsch-Jozsa algorithm

In plain terms

The problem is deliberately artificial. A black box computes a function that's promised to be one of two kinds, constant, giving the same answer on every input, or balanced, giving one answer on exactly half the inputs and the other answer on the rest, and your job is to decide which kind it is while asking the box as few questions as possible.

Classically, certainty is expensive, as in the worst case you must check just over half of all inputs, and the number of inputs grows exponentially with the size of the problem. A quantum procedure asks once. It queries the box on a superposition of all inputs at the same time, a single state in which every input is present with some amplitude, and it arranges the interference between those amplitudes so that a constant function and a balanced function produce perfectly distinguishable outcomes.

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

In CSD

This is one of the corpus's algorithm witnesses, and the corpus is precise about what such witnesses are for. They're scope evidence and not foundations, as the algorithms presuppose the unitary-evolution pillar rather than support it, and their theorems concern circuit semantics and query counts and 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, and not a fragment tuned to make the foundational theorems pass. A reconstruction of quantum mechanics that couldn't run a quantum algorithm would invite a fair question.

Mathematically

One oracle query decides constant-versus-balanced with certainty, whereas exact classical algorithms need 2^(n-1)+1 queries in the worst case for an n-bit input.

The honest footnote is that if the classical side is allowed a tiny error probability, a handful of random queries suffice, so the exponential separation is against exact classical computation. The problem was built to exhibit a separation, and it 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, without teaching duties, working from home. The universal quantum computer is his 1985 construction, and this algorithm came in 1992 with Richard Jozsa, later of Bristol and Cambridge.

Deutsch is also the most committed Everettian alive, and he has argued in print that quantum computation is evidence for many worlds, asking where else the computation would 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.

Related entries

• Bernstein-Vazirani algorithmA hidden string of bits costs one classical question per bit, or exactly one quantum question in total, so the Bernstein-Vazirani algorithm is the cleanest single-query win the field has.
• Simon's algorithmSimon's algorithm was the exponential separation that convinced Shor, as a hidden bitwise mask, unfindable classically without exponential work, falls to a handful of quantum queries and some linear algebra.
• Grover's algorithmGrover's algorithm finds one marked item in an unsorted list in a number of steps proportional to the square root of the list size, and a separate theorem shows that no quantum algorithm can do better.
• Hadamard testThe Hadamard test turns a matrix element, a complex number buried inside an operator, into the bias of a single coin.
• quantum Fourier transformThe quantum Fourier transform runs Fourier's transform as a single reversible motion of a quantum register, and it's the lens that turns hidden periods and phases into outcomes a measurement can land on.