In 1992, physicists David Deutsch and Richard Jozsa posed a deceptively simple question. Imagine you have a black box containing a function that takes a string of bits as input. This function is guaranteed to be one of two types: either “constant,” meaning it gives the same output for every single input, or “balanced,” meaning it outputs 0 for exactly half its inputs and 1 for the other half. How many times must you use the box to figure out which type it is?
Classically, the answer is frustrating. To be absolutely certain, you might have to check just over half of all possible inputs. If the function takes a 100-bit number, the number of inputs is astronomical, far more than the number of atoms in the known universe. Checking even half of them is impossible. The Deutsch-Jozsa algorithm, however, solves the problem with a single call to the function. This was one of the first formal demonstrations that a quantum computer could solve a problem exponentially faster than any deterministic classical computer.
The algorithm achieves this feat not by checking every input in parallel, but by cleverly using quantum interference. It begins by placing a set of qubits into a superposition representing all possible inputs. When the black box function is applied to this superposition, it doesn’t compute all the outputs. Instead, it imparts a subtle shift, called a phase, to the quantum state. This phase shift depends on the global property of the function, whether it is constant or balanced.
A final set of quantum gates causes the different quantum states in the superposition to interfere with one another. For a constant function, all states interfere constructively, leading to a single, predictable outcome upon measurement. For a balanced function, the interference is destructive in a way that guarantees a different outcome. The Deutsch-Jozsa algorithm is more of a foundational lesson than a practical tool, but its true value was in establishing the core pattern for many quantum algorithms: prepare a superposition, apply a function to encode a global property into phases, and use interference to reveal the answer.
Subscribe on Substack at https://qubitguy.substack.com/
