ExperimentIntermediateInteractive experiment

Deutsch–Jozsa with Three Qubits

For the balanced f(x)=s·x with s=101 the circuit outputs 101 with certainty and never 000; a constant f always gives 000.

Goal

Verify that constant and balanced functions can be distinguished with one query.

Approximate duration: 5 minutes

Steps

  1. Choose $n=3$, the balanced type and $s=101$.
  2. Run and measure.
  3. Change the type to constant.
  4. Try other values of $s$.
Loading the simulator…
What theory predicts

Theory predicts for the balanced function $f(x)=s\cdot x$: $P(101)=1$ and $P(000)=0$; and for the constant function: $P(000)=1$.

The Deutsch–Jozsa algorithm generalises the problem to $n$ bits: $f$ is either constant or balanced (half the inputs give 1). After H on all qubits, the oracle and H again, the amplitude of the outcome $0^n$ equals $\frac{1}{2^n}\sum_x(-1)^{f(x)}$, i.e. $\pm1$ for a constant function and 0 for a balanced one.

Classically, with complete certainty, $2^{n-1}+1$ queries are needed in the worst case, while the quantum algorithm needs one. But a randomised classical algorithm solves the problem with a small error probability using only a few queries, so this advantage does not count as a practical speed-up.

Test your understanding

The quiz needs JavaScript.

Related topics

References

  1. David Deutsch; Richard Jozsa (1992). Rapid solution of problems by quantum computation. Proc. R. Soc. Lond. A 439(1907):553–558 doi:10.1098/rspa.1992.0167
  2. Michael A. Nielsen; Isaac L. Chuang (2010). Quantum Computation and Quantum Information (10th Anniversary Edition). Cambridge University Press doi:10.1017/CBO9780511976667The standard reference for quantum computing; the Crossref record gives 2012 for the Cambridge Core online edition.