Before revision:  In this paper, we propose two techniques for reducing the number of CNOT gates in the circuit which are independent of the hardware architecture. For a graph with n vertices, we first propose a technique based on edge coloring that can reduce upto \lfloor n{2} \rfloor CNOT gates in the circuit .
After revision:  In this paper, we propose two techniques for reducing the number of CNOT gates in the circuit . First, we present a method based on Edge Coloring of the input graph that minimizes the the number of cycles (termed as depth of the circuit), and reduces upto \lfloor n{2} \rfloor CNOT gates in the circuit .