Academy K

Deutsch's Algorithm

InterviewConceptualquantum algorithmsoraclesinterference

Related module: Early algorithms

Problem statement

In Deutsch's algorithm, we have a black-box function f:{0,1}→{0,1}f:\{0,1\}\to\{0,1\} implemented as a unitary Uf∣x⟩∣y⟩=∣x⟩∣y⊕f(x)⟩U_f|x\rangle|y\rangle = |x\rangle|y \oplus f(x)\rangle.

The algorithm determines whether ff is constant (f(0)=f(1)f(0)=f(1)) or balanced (f(0)≠f(1)f(0)\neq f(1)) with a single query.

  1. What initial state do we prepare?
  2. After applying UfU_f, what interference pattern reveals the answer?
  3. Why can't a classical computer do this with one query?

Practise this problem

Verify you understand it—not just that you read the answer.

Learn the foundations

The Quantum Computing track covers this topic and more in depth.