Description
We discuss the intimate connection between the quantum speedup of the (pseudo-)pure state Grover algorithm and the detection of multipartite entanglement using the Quantum Fisher Information (QFI). The quantum speedup is proportional to the maximal QFI during the algorithm, and hence proportional to the thereby detected k-partite entanglement. For small purities, speed-up still persists even though no entanglement is detected, however, the QFI still remains a quanfitier of the speed-up.
