Grover search with smaller oracles

Abstract

Grover search is one of the most important quantum algorithms. In this paper, we consider a kind of search that the conditions of satisfaction $T$ can be rewritten as $T=T_1\bigcap T_2$. Then we present a new Grover search with smaller oracles. The time complexity of this algorithm $O(\frac{\pi }{4}\sqrt{\frac{N}{b\lambda }}+\frac{\pi }{4}\sqrt{\frac{b}{\tau }})$, which is smaller than the time complexity of original Grover search, i.e. $O(\frac{\pi }{4}\sqrt{\frac{N}{M}})$.