  A long-standing aim of quantum information research is to understand what
gives quantum computers their advantage. This requires separating problems that
need genuinely quantum resources from those for which classical resources are
enough. Two examples of quantum speed-up are the Deutsch-Jozsa and Simon's
problem, both efficiently solvable on a quantum Turing machine, and both
believed to lack efficient classical solutions. Here we present a framework
that can simulate both quantum algorithms efficiently, solving the
Deutsch-Jozsa problem with probability 1 using only one oracle query, and
Simon's problem using linearly many oracle queries, just as expected of an
ideal quantum computer. The presented simulation framework is in turn
efficiently simulatable in a classical probabilistic Turing machine. This shows
that the Deutsch-Jozsa and Simon's problem do not require any genuinely quantum
resources, and that the quantum algorithms show no speed-up when compared with
their corresponding classical simulation. Finally, this gives insight into what
properties are needed in the two algorithms, and calls for further study of
oracle separation between quantum and classical computation.
