  In 1985, David Deutsch challenged the Church-Turing thesis by stating that
his quantum model of computation "could, in principle, be built and would have
many remarkable properties not reproducible by any Turing machine". While this
is thought to be true in general, there is usually no way of knowing that the
corresponding classical algorithms are the best possible solutions. Here we
provide an efficient classical simulation of the Deutsch-Jozsa algorithm, which
was one of the first examples of quantum computational speed-up. Our conclusion
is that the Deutsch-Jozsa quantum algorithm owes its speed-up to resources that
are not necessarily quantum-mechanical, and when compared with the classical
simulation offers no speed-up at all.
