  It is generally believed that entanglement is essential for quantum
computing. We present here a few simple examples in which quantum computing
without entanglement is better than anything classically achievable, in terms
of the reliability of the outcome after a xed number of oracle calls. Using a
separable (that is, unentangled) n-qubit state, we show that the Deutsch-Jozsa
problem and the Simon problem can be solved more reliably by a quantum computer
than by the best possible classical algorithm, even probabilistic. We conclude
that: (a) entanglement is not essential for quantum computing; and (b) some
advantage of quantum algorithms over classical algorithms persists even when
the quantum state contains an arbitrarily small amount of information|that is,
even when the state is arbitrarily close to being totally mixed.

Quantum Physics;Computational Complexity