Portal de Periódicos da CAPES

An entanglement monotone derived from Grover's algorithm

2002; American Physical Society; Volume: 65; Issue: 6 Linguagem: Inglês

10.1103/physreva.65.062312

1538-4446

Ofer Biham, Michael A. Nielsen, Tobias J. Osborne,

Computability, Logic, AI Algorithms

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 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 P_max that the search algorithm succeeds. We prove that, for pure states, P_max is an entanglement monotone, in the sense that P_max can never be decreased by local operations and classical communication.