Introduction

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 2n2^{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.

One Query, Not Many

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 2n2^{n}⁄2 + 1 = 9 inputs in the worst case.

<p class="hint">A hidden function on 4-bit inputs is secretly <b>constant</b> (same answer everywhere) or <b>balanced</b> (0 for half, 1 for the other half). Probe it <b>classically</b> — one input per click — or run the <b>quantum</b> algorithm, which decides in a single query. New function makes a fresh secret box.</p>
<div id="grid" class="grid"></div>
<div class="counts">
  <span>Classical queries: <b id="cq">0</b> / 9 worst case</span>
  <span>Quantum queries: <b id="qq">0</b></span>
</div>
<div class="status" id="status">Probe the box to decide: constant or balanced?</div>
<div class="btns">
  <button id="classic" type="button">Classical query</button>
  <button id="quantum" type="button">Quantum query</button>
  <button id="reset" type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Deutsch-Jozsa: a hidden function f on n-bit inputs is promised to be either
    // CONSTANT (same output for all 2^n inputs) or BALANCED (0 for exactly half,
    // 1 for the other half). Deciding which classically needs, in the worst case,
    // 2^(n-1)+1 queries to be CERTAIN. A quantum computer needs exactly ONE query.
const N = 4;                 // 4-bit inputs -> 16 cases
const SIZE = 1 << N;         // 16
const WORST = SIZE / 2 + 1;  // 9 classical queries, worst case (certainty)
let truth = [];   // the hidden outputs f(0..15)
let kind = '';    // 'constant' | 'balanced'
let revealed = [];
let cq = 0, qq = 0, order = [];

function makeFunction(){
  // 50/50 pick constant or balanced
  if (Math.random() < 0.5){
    kind = 'constant';
    const v = Math.random() < 0.5 ? 0 : 1;
    truth = Array(SIZE).fill(v);
  } else {
    kind = 'balanced';
    // exactly half 1s, half 0s, shuffled
    truth = Array(SIZE).fill(0).map((_,i)=> i < SIZE/2 ? 1 : 0);
    for (let i = truth.length-1; i>0; i--){ const j = (Math.random()*(i+1))|0; [truth[i],truth[j]]=[truth[j],truth[i]]; }
  }
  revealed = Array(SIZE).fill(null);
  // a worst-case-ish probe order: classical learner can't do better than this on adversarial inputs
  order = Array.from({length:SIZE}, (_,i)=>i);
  cq = 0; qq = 0;
}

function render(){
  const g = document.getElementById('grid'); g.innerHTML = '';
  for (let i=0;i<SIZE;i++){
    const d = document.createElement('div');
    const r = revealed[i];
    d.className = 'bit' + (r===0?' q0':r===1?' q1':'');
    const lbl = i.toString(2).padStart(N,'0');
    d.innerHTML = '<span>'+(r===null?'?':r)+'</span><small>'+lbl+'</small>';
    g.appendChild(d);
  }
  document.getElementById('cq').textContent = cq;
  document.getElementById('qq').textContent = qq;
}
function setStatus(t,cls){ const s=document.getElementById('status'); s.textContent=t; s.className='status '+cls; }

// CLASSICAL: reveal one more output. Decide as soon as logic forces it.
function classicalProbe(){
  // find next unrevealed in order
  const idx = order.find(i => revealed[i] === null);
  if (idx === undefined){ return; }
  revealed[idx] = truth[idx]; cq++;
  const seen = revealed.filter(v => v !== null);
  const ones = seen.filter(v=>v===1).length, zeros = seen.length - ones;
  render();
  // Two distinct values seen => must be BALANCED (constant ruled out).
  if (ones > 0 && zeros > 0){
    setStatus(fmt('Two different outputs after %cq% queries -> BALANCED. (It was %kind%.)', { cq: cq, kind: kind }), kind==='balanced'?'ok':'bad');
    return;
  }
  // Saw more than half identical with no disagreement => must be CONSTANT.
  if (seen.length >= WORST){
    setStatus(fmt('All %cq% agree, past the halfway mark -> CONSTANT. (It was %kind%.)', { cq: cq, kind: kind }), kind==='constant'?'ok':'bad');
    return;
  }
  setStatus(fmt('So far all the same. Not yet certain — keep probing (%cq%/%WORST%).', { cq: cq, WORST: WORST }),'');
}

// QUANTUM: one query, always correct. We compute the Deutsch-Jozsa outcome
    // exactly: measuring |0..0> with probability |(1/2^n) * sum_x (-1)^f(x)|^2.
    // = 1 iff f is constant, 0 iff f is balanced.
function quantumProbe(){
  qq = 1;
  let amp = 0;
  for (let x=0;x<SIZE;x++) amp += (truth[x] ? -1 : 1);
  amp /= SIZE;                       // amplitude of the all-zeros outcome
  const pAllZero = amp*amp;          // probability of measuring 0000
  const verdict = pAllZero > 0.5 ? 'constant' : 'balanced';
  // reveal everything just to show the box (the algorithm did NOT need to)
  for (let i=0;i<SIZE;i++) revealed[i] = truth[i];
  render();
  setStatus(fmt('Quantum query #1 -> measured %v% => %toUpperCase%. One query, always right. (It was %kind%.)', { v: verdict==='constant'?'all-zeros':'non-zero', toUpperCase: verdict.toUpperCase(), kind: kind }), 'q');
}

document.getElementById('classic').addEventListener('click', classicalProbe);
document.getElementById('quantum').addEventListener('click', quantumProbe);
document.getElementById('reset').addEventListener('click', ()=>{ makeFunction(); render(); setStatus('New hidden box. Probe to decide: constant or balanced?',''); });
makeFunction(); render();
Result
Console

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.

The Real Complexity

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

  • Classical, exact: to be certain you must, in the worst case, query 2n2^{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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/deutsch-jozsa/Content licensed under CC BY-NC 4.0.