Abstract
This paper demonstrates that how well a state performs as an input to Grover’s search algorithm depends critically upon the entanglement present in that state; the more the entanglement, the less well the algorithm performs. More precisely, suppose we take a pure state input, and prior to running the algorithm apply local unitary operations to each qubit in order to maximize the probability that the search algorithm succeeds. We prove that, for pure states, is an entanglement monotone, in the sense that can never be decreased by local operations and classical communication.
- Received 17 December 2001
DOI:https://doi.org/10.1103/PhysRevA.65.062312
©2002 American Physical Society