Abstract
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 + \lfloor \frac{n}{3} \rfloor)(3 \times 2^{2n-3}-2^{n+2})\) and \(4n(n + \lfloor \frac{n}{3} \rfloor)2^n\), respectively. A provable constructive synthesis algorithm is derived. The time complexity of the algorithm is \(\frac{10}{3}n^2 \cdot 2^n\). Our algorithm is exponentially lower than breadth-first search based synthesis algorithms with respect to space and time complexities.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Nielsen, M.A., Isaac, L.: Chuang: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000)
Iwama, K., Kambayashi, Y., Yamashita, S.: Transformation rules for designing CNOT-based quantum circuits. In: Proc. DAC, New Orleans, Louisiana 28.4 (2002)
Landauer, R.: Irreversibility and heat generation in the computational process. IBM Journal of Research and Development 5, 183–191 (1961)
Bennett, C.: Logical reversibility of computation. IBM Journal of Research and Development 17, 525–532 (1973)
Fredkin, E., Toffoli, T.: Conservative logic. Int. Journal of Theoretical Physics. 21, 219–253 (1982)
Deutsch, D.: Quantum computational networks. Royal Society of London Series A 425, 73–90 (1989)
Khlopotine, A., Perkowski, M., Kerntopf, P.: Reversible logic synthesis by gate composition. In: Proc. IEEE/ACM Int. Workshop on Logic Synthesis, pp. 261–266 (2002)
Toffoli, T.: Bicontinuous extensions of invertible combinatorial functions. Mathematical Systems Theory 14, 13–23 (1981)
Yang, G., Hung, W.N.N., Song, X., Perkowski, M.: Majority-Based Reversible Logic Gates. Theoretical Computer Science 334, 274–295 (2005)
Yang, G., Song, X., Hung, W.N.N., Perkowski, M.: Fast Synthesis of Exact Minimal Reversible Circuits using Group Theory. In: ACM/IEEE Asia and South Pacific Design Automation Conference (ASP-DAC), pp. 1002–1005 (2005)
Dixon, J.D., Mortimer, B.: Permutation Groups. Springer, New York (1996)
De. Vos, A.: Reversible computing. Qutantum Electronics 23, 1–49 (1999)
Storme, L., De. Vos, A., Jacobs, G.: Group theoretical aspects of reversible logic gates. Journal of Universal Computer Science 5, 307–321 (1999)
Michael Miller, D., Maslov, D., Dueck, G.W.: A Transformation Based Algorithm for Reversible Logic Synthesis. In: Proc. DAC, pp. 318–323 (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Yang, G., Song, X., Hung, W.N.N., Xie, F., Perkowski, M.A. (2006). Group Theory Based Synthesis of Binary Reversible Circuits. In: Cai, JY., Cooper, S.B., Li, A. (eds) Theory and Applications of Models of Computation. TAMC 2006. Lecture Notes in Computer Science, vol 3959. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11750321_35
Download citation
DOI: https://doi.org/10.1007/11750321_35
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-34021-8
Online ISBN: 978-3-540-34022-5
eBook Packages: Computer ScienceComputer Science (R0)