Cost Reduction in Nearest Neighbour Based Synthesis of Quantum Boolean Circuits

Quantum computer algorithms require an 'oracle' as an integral part. An oracle is a reversible quantum Boolean circuit, where the inputs are kept unchanged at the outputs and the functional outputs are realized along ancillary input constants (0 or 1). Recently, a nearest neighbour template based synthesis method of quantum Boolean circuits has been proposed to overcome the adjacency requirement of the input qubits of physical quantum gates. The method used SWAP gates to bring the input qubits of quantum CNOT or (CNOT)-N-2 gates adjacent. In this paper, we propose cost reduction techniques such as ancillary constant determination to reduce the number of NOT gates and variable ordering and product grouping to reduce the number of SWAP gates required in nearest neighbour template based synthesis. The proposed approach significantly reduces the quantum realization cost of the synthesized quantum Boolean circuit than that of the original nearest neighbour template based synthesis.