Deutsch's Algorithm

Suppose we have some box that implements a function $f: \{0,1\} \to \{0,1\}$. We don't know what function it is, and the only way we can figure it out is by "querying" this box, i.e. sending an input into the box and checking the output.

There are exactly four possible single-bit functions, which we'll denote by $f_{0}, f_{1}, f_{2},$ and $f_{3}$:

1. Constant zero ($f_{0}$): $f_{0}(0) = 0, f_{1}(1) = 0$
2. Constant one ($f_{1}$): $f_{1}(0) = 1, f_{1}(1) = 1$
3. Identity ($f_{2}$): $f_{2}(0) = 0, f_{2}(1) = 1$
4. NOT ($f_{3}$): $f_{3}(0) = 1, f_{3}(1) = 0$

We can classify these into two types:

• Constant functions: Output same value for both inputs ($f_{0}$ and $f_{1}$)
• Balanced functions: Output $0$ for one input and $1$ for the other ($f_{2}$ and $f_{3}$)

The Deutsch Problem: Given a black-box function $f$, determine whether it's constant or balanced using the minimum number of queries.

Classical Analysis: To determine if $f$ is constant or balanced, we need to check if $f(0) = f(1)$ or $f(0) \neq f(1)$.

...