An information-theoretic analysis of Grover's algorithm
Erdal Arıkan · 2003
This paper presents an information-theoretic analysis of Grover's algorithm and give a tight lower bound on the complexity of search algorithms using Grover's oracle. This paper also proposes the square-root speed-up performance gain of a quantum search algorithm and the significance of tight bounds based on Grover's oracle algorithm to identify target element.