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
- Choose $n=3$, the balanced type and $s=101$.
- Run and measure.
- Change the type to constant.
- Try other values of $s$.
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
- 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
- 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.
