On the role of entanglement in quantum-computational speed-up

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 efficiently simulated classically to within a prescribed tolerance 77 even if a suitably small amount of global entanglement is present. We explicitly identify the occurrence of increasing multi-partite entanglement in Sher'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.