Source-verifiedLevel 3

Deutsch-Jozsa Algorithm

The Deutsch-Jozsa algorithm determines whether a Boolean function is constant or balanced using only one query, providing an exponential speedup over classical deterministic algorithms.

See it move

A free signup brings you straight back to this concept.

Continue in the app →I already have an account

What it means

The Deutsch-Jozsa algorithm (1992) solves the following problem: given a black-box function f:{0,1}^n -> {0,1} that is promised to be either constant (same output for all inputs) or balanced (output 0 for half the inputs, 1 for the other half), determine which case it is.Classically, this requires 2^(n-1)+1 queries in the worst case.The quantum algorithm uses only ONE query by exploiting quantum parallelism and interference.The circuit applies H gates to create superposition, queries the oracle, applies H gates again, and measures.If all measurement results are |0⟩, the function is constant; otherwise, balanced.This was the first algorithm proving quantum speedup.

Everyday analogy

Imagine a sealed box of switches wired to a lamp that is either always the same (constant) or lit for exactly half of the inputs (balanced). Classically you may have to try more than half of the inputs to be sure; Deutsch-Jozsa arranges for the amplitudes to interfere so that one query reveals which kind of box it is — without telling you any individual output.
Think of it as testing whether a sealed ballot box contains all identical votes or a perfect split -- quantum mechanics lets you check with a single peek.

Common misconceptions

  • The Deutsch-Jozsa speedup is over DETERMINISTIC classical algorithms -- probabilistic classical algorithms can solve it efficiently with bounded error.
  • The algorithm does NOT tell you WHAT the function computes -- only whether it is constant or balanced.

Key takeaways

  • Determines constant vs balanced with just one oracle query (exponential speedup over classical deterministic).
  • First algorithm demonstrating provable quantum advantage.
  • Uses superposition, phase kickback, and interference as key quantum techniques.

Check your understanding

How many oracle queries does the Deutsch-Jozsa algorithm require?

  1. A.n
  2. B.2^n
  3. C.1
  4. D.log(n)
Show the answer

Answer: C. 1

Why: The Deutsch-Jozsa algorithm requires exactly 1 oracle query, compared to 2^(n-1)+1 queries needed classically in the worst case.

Builds on

QubitSuperpositionHadamard GateQuantum Measurement

Related concepts

OracleInterferenceGrover's AlgorithmQuantum Phase Estimation

Primary source: Deutsch & Jozsa, Rapid solution of problems by quantum computation, Proc. R. Soc. A 439, 553 (1992), doi:10.1098/rspa.1992.0167

Learn it hands-on

This concept is part of a 46-level curriculum with an interactive simulator and Lumen, a tutor that checks its answers and labels how sure each one is. Levels 1–5 are free.

Start freeSee the curriculum