Quantum Computing Without Entanglement
<|reference_start|>Quantum Computing Without Entanglement: 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.<|reference_end|>
@article{biham2003quantum,
    title={Quantum Computing Without Entanglement},
    author={Eli Biham, Gilles Brassard, Dan Kenigsberg and Tal Mor},
    journal={Theoretical Computer Science, Volume 320, Issue 1, Pages 15 - 33,
  June 2004.},
    year={2003},
    doi={10.1016/j.tcs.2004.03.041},
    archivePrefix={arXiv},
    eprint={quant-ph/0306182},
    primaryClass={quant-ph cs.CC}
}