Quantum Computing Without Entanglement
| dc.creator | Biham, Eli | |
| dc.creator | Brassard, Gilles | |
| dc.creator | Kenigsberg, Dan | |
| dc.creator | Mor, Tal | |
| dc.date | 2003-06-26 | |
| dc.date.accessioned | 2026-07-07T07:51:31Z | |
| dc.date.available | 2026-07-07T07:51:31Z | |
| dc.description | 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. | |
| dc.description | 18 pages. Presented at FoCM'02 (Aug 2002, see http://www.cs.technion.ac.il/~danken/pub/QCnoEnt.pdf), QIP'03 (Dec 2002, see http://www.msri.org/publications/ln/msri/2002/qip/brassard/1/), Qubit'03 (Apr 2003, see http://www.cs.technion.ac.il/~talmo/Qubitconf/QUBIT-2003/program/) | |
| dc.identifier | https://arxiv.org/abs/quant-ph/0306182 | |
| dc.identifier | http://arxiv.org/abs/quant-ph/0306182 | |
| dc.identifier | Theoretical Computer Science, Volume 320, Issue 1, Pages 15 - 33, June 2004. | |
| dc.identifier | doi:10.1016/j.tcs.2004.03.041 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/125538 | |
| dc.subject | Quantum Physics | |
| dc.subject | Computational Complexity | |
| dc.title | Quantum Computing Without Entanglement | |
| dc.type | text |