Speed-up and entanglement in quantum searching
Samuel L. Braunstein, Arun Kumar Pati · CERN Document Server (European Organization for Nuclear Research) · 2002
Grover's algorithm on pure states naturally generates entanglement during computation. For pseudo-pure state implementations we show that not only is entanglement necessary to achieve a speed-up, but it must be present throughout the computation. Despite the non-asymptotic character of this result we find that it only unambiguously applies to ensemble implementations, such as in liquid-state NMR, for asymptotically large search spaces. This ambiguity and its implications for interpreting a claimed speed-up in existing NMR based quantum searches is discussed.