The Deutsch–Jozsa Algorithm

Imagine a sealed black box. You feed it a string of bits, it spits out a single 0 or 1, and you are promised one of just two things is true: the box is constant (it answers the same value for every input) or it is balanced (it answers 0 for exactly half the inputs and 1 for the other half). Your job: decide which — constant or balanced.

Classically there is no shortcut in the worst case. To be certain, you may have to open the box again and again: for inputs of n bits there are $2^{n}$ possibilities, and you might need to test just over half of them before you can rule out "constant." That is exponential work.

In 1992, David Deutsch and Richard Jozsa showed something startling: a quantum computer can settle the question with a single query to the box. It was the first clean proof that a quantum machine can be exponentially faster than any classical one — the spark that lit the whole field of quantum algorithms.

Below is a hidden function on 4-bit inputs (16 possible inputs). It is secretly either constant or balanced — you don't know which. Probe it classically: each click reveals one more output. To be sure it's constant you may have to check $2^{n}$⁄2 + 1 = 9 inputs in the worst case.

<p class="hint">{{hint}}</p>
<div id="grid" class="grid"></div>
<div class="counts">
  <span>{{classical_queries_label}}: <b id="cq">0</b> / 9 {{worst_case}}</span>
  <span>{{quantum_queries_label}}: <b id="qq">0</b></span>
</div>
<div class="status" id="status">{{initial_status}}</div>
<div class="btns">
  <button id="classic" type="button">{{btn_classical}}</button>
  <button id="quantum" type="button">{{btn_quantum}}</button>
  <button id="reset" type="button" class="ghost">{{btn_new_function}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.grid { display: grid; grid-template-columns: repeat(8, 38px); gap: 5px; margin: .5rem 0; }
.bit { width: 38px; height: 38px; display: flex; align-items: center; justify-content: center;
       font: 700 15px ui-monospace, monospace; border-radius: 7px; background: #e8eef3;
       color: #1d3557; border: 1px solid #cdd9e3; }
.bit.q0 { background: #d4edda; border-color: #9ccaa9; color: #0a7d33; }
.bit.q1 { background: #f8d7da; border-color: #e0a3a9; color: #c92f3c; }
.bit small { font-size: 9px; font-weight: 600; opacity: .65; display: block; line-height: 1; }
.counts { display: flex; gap: 1.2rem; flex-wrap: wrap; font-size: .9rem; color: #444; margin: .3rem 0 .2rem; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.status.q { color: #5a2a9d; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button#quantum { background: #5a2a9d; border-color: #5a2a9d; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Now press Quantum query. The Deutsch–Jozsa algorithm prepares all inputs in superposition, runs the box once, and lets the answers interfere: a measurement of all-zeros means constant, anything else means balanced — guaranteed, after a single call. The classical counter can climb to nine; the quantum one never leaves one.

How big is the gap, exactly — and is it real?

• Classical, exact: to be certain you must, in the worst case, query $2^{n}$⁄2 + 1 inputs. The moment two outputs disagree you know it's balanced; but if the first half all match, you can't rule out constant until one more check.
• Quantum: the Deutsch–Jozsa algorithm answers with exactly one query, always correct. It puts the input register into an equal superposition, applies the box, and uses a layer of Hadamard gates so that the "constant" amplitudes pile up on the all-zeros outcome and the "balanced" ones cancel it out — pure interference.
• A proven separation. This is not a guess about hard cases: it is a theorem. Deutsch and Jozsa (1992), tightened by Cleve, Ekert, Macchiavello and Mosca in 1998 into the clean one-query form, give a genuine exponential gap in query complexity between quantum and exact classical computation.

One honest caveat: if you allow a tiny chance of error, a classical computer can decide constant-vs-balanced in a handful of random queries. The exponential gap is real for exact, deterministic classical algorithms. Either way, Deutsch–Jozsa was the first concrete problem where a quantum computer is provably faster — a foundational result in BQP, the class of problems quantum machines solve efficiently.

Deutsch–Jozsa rarely solves a real-world task on its own — the "constant or balanced" promise is artificial. Its value is the blueprint it revealed:

• The quantum recipe. Put inputs in superposition → query the function once → make the answers interfere so the one you want survives. Every flagship quantum algorithm follows this shape.
• Shor's algorithm. Factoring large numbers — the engine of RSA — uses the same interference trick over periodic functions, threatening today's public-key cryptography.
• Grover's search. Finding a needle in an unsorted haystack quadratically faster reuses superposition and amplitude steering.
• Teaching and benchmarking. Because it's small and provable, Deutsch–Jozsa is the "hello world" of quantum computing and a favorite test for new quantum hardware.

Learn why one query can beat many and you've met the core idea of quantum advantage — the same engine driving Shor's factoring and the search for problems quantum machines can crack that classical ones cannot.

Deutsch–Jozsa is a deliberately small puzzle with an outsized legacy. Decide whether a hidden box is constant or balanced: a classical computer may grind through exponentially many calls to be sure, while a quantum computer — exploiting superposition and interference — answers in exactly one.

It was the first ironclad demonstration that quantum computation is not just classical computation in disguise. The promise is contrived, but the lesson is permanent: the very same recipe of superposition-then-interference reappears in Shor's algorithm and across the quantum toolkit. One query was all it took to open the door.