  Quantum computing has noteworthy speedup over classical computing by taking
advantage of quantum parallelism, i.e., the superposition of states. In
particular, quantum search is widely used in various computationally hard
problems. Grover's search algorithm finds the target element in an unsorted
database with quadratic speedup than classical search and has been proved to be
optimal in terms of the number of queries to the database. The challenge,
however, is that Grover's search algorithm leads to high numbers of quantum
gates, which make it infeasible for the Noise-Intermediate-Scale-Quantum (NISQ)
computers.
  In this paper, we propose a novel hardware efficient quantum search algorithm
to overcome this challenge. Our key idea is to replace the global diffusion
operation with low-cost local diffusions. Our analysis shows that our algorithm
has similar oracle complexity to the original Grover's search algorithm while
significantly reduces the circuit depth and gate count. The circuit cost
reduction leads to a remarkable improvement in the system success rates, paving
the way for quantum search on NISQ machines.
