This paper presents an important result addressing a fundamental question in synthesizing binary reversible logic circuits for quantum computation. We show that any even-reversible-circuit of n (n > 3) qubits can be realized using NOT gate and Toffoli gate ('2'-Controlled-Not gate), where the numbers of Toffoli and NOT gates required in the realization are bounded by (n+[n 3] )(3 x 2 2n-3  -2 n+2  ) and 4n(n+ [n 3] j )2, respectively. A provable constructive synthesis algorithm is derived. The time complexity of the algorithm is 10 3n 2 . 2 n . Our algorithm is exponentially lower than breadth-first search based synthesis algorithms with respect to space and time complexities.
['Guowu Yang', 'Xiaoyu Song', 'William N. N. Hung', 'Fei Xie', 'Marek A. Perkowski']
Group theory based synthesis of binary reversible circuits