Wavelet quantum search algorithm with partial information

It is questionable that Grover algorithm may be more efficient than classical one, when partial information is given in an unstructured database. In this letter, we propose to use the Haar wavelet transformation in the Grover algorithm, to consider partial information. Given a partial information L to an unstructured database of size N, we show the improved speedup, O(N/L). The speedup originates in the preparation of the initial state W†|k〉, which provides a superposition of N/L states and L determines which state has to be chosen as ∣k〉.