×

Minimal universal library for \(n\times n\) reversible circuits. (English) Zbl 1145.94482

Summary: Reversible logic plays an important role in quantum computing. Several papers have been recently published on universality of sets of reversible gates. However, a fundamental unsolved problem remains: “what is the minimum set of gates that are universal for \(n\)-qubit circuits without ancillae bits”. We present a library of 2 gates which is sufficient to realize all reversible circuits of n variables. It is a minimal library of gates for binary reversible logic circuits. We also analyze the complexity of the syntheses.

MSC:

94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
81P68 Quantum computation
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Shende, V. V.; Prasad, A. K.; Markov, I. L.; Hayes, J. P., Synthesis of reversible logic circuits, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 22, 6, 710-722 (2003)
[2] Bennett, C., Logical reversibility of computation, IBM Journal of Research and Development, 17, 525-532 (1973) · Zbl 0267.68024
[3] Storme, L.; De Vos, A.; Jacobs, G., Group theoretical aspects of reversible logic gates, Journal of Universal Computer Science, 5, 307-321 (1999) · Zbl 0961.68008
[4] Song, X.; Yang, G.; Perkowski, M.; Wang, Yuke, Algebraic characterization of reversible logic gates, Theory of Computing Systems, (Mathematical Systems Theory), 39, 2, 311-319 (2006) · Zbl 1101.68032
[5] A. Khlopotine, M. Perkowski, P. Kerntopf, Reversible logic synthesis by gate composition, in: Proc. IEEE/ACM International Workshop on Logic Synthesis, 2002, pp. 261-266; A. Khlopotine, M. Perkowski, P. Kerntopf, Reversible logic synthesis by gate composition, in: Proc. IEEE/ACM International Workshop on Logic Synthesis, 2002, pp. 261-266
[6] Toffoli, T., Bicontinuous extensions of invertible combinatorial functions, Mathematical Systems Theory, 14, 13-23 (1981) · Zbl 0469.94020
[7] Fredkin, E.; Toffoli, T., Conservative logic, International Journal of Theoretical Physics, 21, 219-253 (1982) · Zbl 0496.94015
[8] Kargapolov, M. I.; Merzljakov, Ju. I., Fundamentals of the Theory of Groups (1979), Springer-Verlag: Springer-Verlag New York · Zbl 0549.20001
[9] Smolin, J. A.; DiVincenzo, D. P., Five two-bit quantum gates are sufficient to implement the quantum Fredkin gate, Physical Review A, 53, 2855-2856 (1996)
[10] Dixon, J. D.; Mortimer, B., Permutation Groups (1996), Springer: Springer New York · Zbl 0951.20001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.