This study presents an automated circuit generation method for a quantum oracle that maps each and every computational basis state (CBS) |x⟩n in a superposed quantum qubit register to the corresponding signed CBS of an arbitrary input function, ±|f(x)⟩n, in the other qubit register [Figure 1]. The oracle of this type is algebraically represented by a block diagonal matrix with each block being a signed permutation matrix. Our goal is to develop a method to generate a quantum oracle circuit directly from an input function f(x) without the explicit consideration of the intermediary oracle matrix. The proposed method implicitly utilizes the structure of the oracle matrix associated with the input function.
We show that the oracle matrix of the quantum oracle circuit can be build up of a set of basic circuit modules, each of which maps an input CBS to the signed CBS corresponding function value f(x). We also show that the basic circuit module is made of at most one generalized Toffoli gate, two Hadamard gates, and two X gates. The generalized Toffoli gate used in the basic module has multiple control qubits and multiple target quits. Once the scheme to generate the basic circuit modules directly from the input function is devised, the entire quantum circuit of the oracle can be generated directly from the input function. [Figure 2] shows the case with two 2-qubit registers. In general, the circuit generated by the proposed method for two n-qubit registers consists of up to 4·2n generalized Toffoli gates, 2·2n Hadamard gates, and 2n·2n X gates.
As an example, the quantum circuit of the sign flip oracle (card hiding oracle) in the Grover’s algorithm with five qubits is generated by our method [Figure 3]. The oracle flips the sign of the marked CBS ket. Therefore, only one sign-flip circuit is needed for a marked CBS. By aggregating the sign-flip circuits for all CBS’s, we obtain a circuit for any makred CBS, even for a set of marked CBS’s, without any modification. This circuit is controlled by a set of parameters stored in classical registers.
