Deutsch Algorithm: Balanced Function
With one oracle query Deutsch's algorithm decides that f(x)=x is balanced: q0 reads 1 with certainty.
Goal
Implement the first quantum algorithm that beats the classical query count for the same problem.
Approximate duration: 5 minutes
Steps
- Choose $f$ = identity.
- Follow the phase after the oracle.
- Run and measure $q_0$.
- Try the four functions: const0, const1, identity, not.
Theory predicts for identity and not: $P(q_0=1)=1$ (balanced), and for const0 and const1: $P(q_0=0)=1$ (constant). One query suffices in every case.
The problem: a function $f:\{0,1\}\to\{0,1\}$ is either constant ($f(0)=f(1)$) or balanced. Classically, two queries are needed. The algorithm prepares $|+\rangle|-\rangle$, then the oracle $U_f|x\rangle|y\rangle=|x\rangle|y\oplus f(x)\rangle$ is applied, so the phase $(-1)^{f(x)}$ appears on the input qubit (Phase Kickback); then H and measurement: outcome 0 means constant and 1 means balanced.
This is an advantage in the number of queries for a contrived problem (1 versus 2), not evidence of a general practical speed-up.
Test your understanding
The quiz needs JavaScript.
Related topics
References
- David Deutsch (1985). Quantum theory, the Church–Turing principle and the universal quantum computer. Proc. R. Soc. Lond. A 400(1818):97–117 doi:10.1098/rspa.1985.0070
- 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.
