Physics – Quantum Physics
Scientific paper
2002-01-30
Physics
Quantum Physics
Main proofs simplified. A few further explanatory remarks added. 22 pages, plain latex
Scientific paper
10.1098/rspa.2002.1097
For any quantum algorithm operating on pure states we prove that the presence of multi-partite entanglement, with a number of parties that increases unboundedly with input size, is necessary if the quantum algorithm is to offer an exponential speed-up over classical computation. Furthermore we prove that the algorithm can be classically efficiently simulated to within a prescribed tolerance \eta even if a suitably small amount of global entanglement (depending on \eta) is present. We explicitly identify the occurrence of increasing multi-partite entanglement in Shor's algorithm. Our results do not apply to quantum algorithms operating on mixed states in general and we discuss the suggestion that an exponential computational speed-up might be possible with mixed states in the total absence of entanglement. Finally, despite the essential role of entanglement for pure state algorithms, we argue that it is nevertheless misleading to view entanglement as a key resource for quantum computational power.
Jozsa Richard
Linden Noah
No associations
LandOfFree
On the role of entanglement in quantum computational speed-up 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 On the role of entanglement in quantum computational speed-up, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the role of entanglement in quantum computational speed-up will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-584130