%0 Generic %1 citeulike:1165318 %A Biham, Eli %A Brassard, Gilles %A Kenigsberg, Dan %A Mor, Tal %D 2003 %K computing entanglement quantum without %T Quantum Computing Without Entanglement %U http://arxiv.org/abs/quant-ph/0306182 %X 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.

@misc{citeulike:1165318, abstract = {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.}, added-at = {2007-08-18T13:22:24.000+0200}, author = {Biham, Eli and Brassard, Gilles and Kenigsberg, Dan and Mor, Tal}, biburl = {https://www.bibsonomy.org/bibtex/2843651c87bdae0c608964f52bf0ba728/a_olympia}, citeulike-article-id = {1165318}, description = {citeulike}, eprint = {quant-ph/0306182}, interhash = {c1930d6cee7a6d53be65b091e6cb0055}, intrahash = {843651c87bdae0c608964f52bf0ba728}, keywords = {computing entanglement quantum without}, month = Jun, priority = {2}, timestamp = {2007-08-18T13:22:30.000+0200}, title = {Quantum Computing Without Entanglement}, url = {http://arxiv.org/abs/quant-ph/0306182}, year = 2003 }