Quantum circuit design and analysis for database search applications

In this paper, we show how quantum Boolean circuits can be used to implement the oracle and the inversion-about-average function in Grover's search algorithm. Before illustrating how this can be done, we present the circuit design principle using the satisfiability (SAT) problem as an example. Then, based on this principle, we show the quantum circuits for two different kinds of applications. The first one is searching a phone book. Although this is a typical example of Grover's algorithm, we show that it is impractical as a real-world application. As the second application, we give the quantum circuits for a more practical application-breaking a symmetric cryptosystem. Although these two applications have quite different types of search criteria, they are both one-way functions and the proposed circuits can actually be generalized to any such problems. In this perspective, we conclude this paper by proposing a template of quantum circuits that is capable of searching the solution of a certain class of one-way functions.