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 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 and we discuss the suggestion that an exponential…