  Probably the simplest and most frequently used way to illustrate the power of
quantum computing is to solve the so-called {\it Deutsch's problem}. Consider a
Boolean function $f: \{0,1\} \to \{0,1\}$ and suppose that we have a
(classical) black box to compute it. The problem asks whether $f$ is constant
(that is, $f(0) = f(1)$) or balanced ($f(0) \not= f(1)$). Classically, to solve
the problem seems to require the computation of $f(0)$ and $ f(1)$, and then
the comparison of results. Is it possible to solve the problem with {\em only
one} query on $f$? In a famous paper published in 1985, Deutsch posed the
problem and obtained a ``quantum'' {\em partial affirmative answer}. In 1998 a
complete, probability-one solution was presented by Cleve, Ekert, Macchiavello,
and Mosca. Here we will show that the quantum solution can be {\it
de-quantised} to a deterministic simpler solution which is as efficient as the
quantum one. The use of ``superposition'', a key ingredient of quantum
algorithm, is--in this specific case--classically available.

Quantum Physics