Quantum Computing Without Entanglement

Details Quantum Computing Without Entanglement Quantum Computing Without Entanglement

2003-06-26

arxiv.org/abs/quant-ph/0306182v1

Theoretical Computer Science, Volume 320, Issue 1, Pages 15 - 33, June 2004.

Physics

Quantum Physics

18 pages. Presented at FoCM'02 (Aug 2002, see http://www.cs.technion.ac.il/~danken/pub/QCnoEnt.pdf), QIP'03 (Dec 2002, see h

Scientific paper

10.1016/j.tcs.2004.03.041

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.

Affiliated with

Also associated with

No associations

Rating

Quantum Computing Without Entanglement does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Quantum Computing Without Entanglement, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum Computing Without Entanglement will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-187432