THE FREDKIN GATE IN REVERSIBLE AND QUANTUM ENVIRONMENTS

Claudio Moraga, Fatima Zhora Hadjam

DOI Number
doi.org/10.2298/FUEE2302253M
First page
253
Last page
266

Abstract


Reversible Computing circuits are characterized by low power consumption and their proximity to circuits for quantum computing. The Fredkin gate was one of the earliest proposed controlled reversible circuits, which however, was soon superseded by the Toffoli gate, the NOT, and CNOT gates, which constituting a flexible functionally complete set could also realize the Fredkin gate as a building block. In quantum computing circuits, the Fredkin gate (under the name controlled SWAP) plays an important role regarding the superposition of states. The present paper studies extensions of the Fredkin gate in terms of mixed polarity in the reversible domain and an application in quantum computing.


Keywords

Fredkin gate, Reversible circuits, Quantum computing circuits

Full Text:

PDF

References


A. Barenco, C. H. Bennett, R. Cleve, D. P. Di Vincenzo, N. Margolus, P. Shor, T. Sleator, J. A. = Smolin, and H. Weinfurter, "Elementary gates for quantum computation", Phys. Rev. A, vol. 52, pp. 3457-3467, 1995.

C. Bennett, "Logical reversibility of computation", IBM J. Res. Develop., vol. 17, pp. 525-532, 1973.

H. Buhrman, R. Cleve, J. Watrous and R. De Wolf, "Quantum Fingerprinting", Phys. Rev. Lett., vol. 87, no. 16, p. 167902-1-4, 2001.

C. S. Cheng and A. K. Singh, "Heuristic Synthesis of Reversible Logic – A Comparative Study", Theoretical Appl. Electr. Eng., vol. 12, no. 3, pp. 210-225, 2014.

O. Dovhamuk and V. Deibuk, “CMOS simulation of mixed-polarity Generalized Fredkin Gates", In Proceedings of the 12th International Conference on Advanced Computer Information Technologies (ACIT), IEEE Press, 2022.

E. Fredkin and T. Toffoli, "Conservative logic", Int. Jr. Theor. Phys., vol. 21, no. 3/4, pp. 219-253, 1982.

F. Z. Hadjam and C. Moraga, "RIMEP2. Evolutionary Design of Reversible Digital Circuits", ACM J. Emerg. Technol. Comput. Syst., vol. 11, no. 3, pp. 27:1-27:23, 2014.

F. Z. Hadjam and C. Moraga, "A hierarchical distributed linear evolutionary system for the synthesis of 4-bit reversible circuits" in R. Seising and H. Allende-Cid (Eds.), Studies in Fuzziness and Soft Computing 349, pp. 233-249. Springer, 2017.

R. Landauer, "Irreversibility and heat generation in the computing process" IBM J. Res. Develop., vol. 5, pp. 183-191, 1961.

M. Lukac, M. A. Perkowski, H. Goi, M. Pivtoraiko, Ch. H. Yu, K. Chung, H. Jeech, B.-G. Kim and Y. D. Kim, "Evolutionary Approach to Quantum and Reversible Circuits Synthesis", Artif. Intell. Rev., vol. 20, no. 3-4, pp. 361-417, 2003.

D. Maslov, G. W. Dueck and D. M. Miller, "Synthesis of Fredkin-Toffoli Reversible Networks", IEEE Trans. Very Large Scale Integ. (VLSI) Syst., vol. 13, no. 6, pp. 765-769, 2005.

M. D. Miller and G. W. Dueck, "Search-Based Transformation Synthesis for 3-valued Reversible Circuits" in I. Lanese, and M. Rawski (Eds.), Reversible Computation, LNCS 12227, 218-236, Springer, 2020.

C. Moraga, "Hybrid GF(2)-Boolean Expressions for Quantum Computing Circuits", in A. De Vos and R. Wille (Eds.), RC 2011, LNCS 7165, pp. 54-63, Springer, 2012.

C. Moraga, "Using negated control signals in quantum computing circuits", FU Elec. Energ., vol. 24, no. 3, pp. 423-435, 2011.

C. Moraga, "OR-Toffoli and OR-Peres Reversible Gates", in S. Yamashita and T. Yokoyama (Eds.) Reversible Computation, LNCS 12805, pp. 266-273, Springer, 2021.

M. Nielsen and I. Chuang, Quantum Computation and Quantum Information. Cambridge Univ. Press, UK, 2000.

Ph. Niemann, L. Müller and R. Drechsler, "Finding Optimal Implementations of Non-native CNOT gates using SAT", in S. Yamashita, T. Yokoyama, (Eds.), Reversible Computation, LNCS 12805, pp. 242-255, Springer, 2021.

W. Pauli, Handbuch der Physik, Chapter 24, Springer, Berlin, 1933.

M. Rahman and G. W. Dueck, "An algorithm to find quantum Templates" In Proceedings of the IEEE Congress on Evolutionary Computing, IEEE Press, 2012, pp. 623-629.

I. Rahul, B. Loff and I. C. Oliveira, "NP-hardness of circuit minimization for multi-output functions", In Proceedings of the 35th Computational Complexity Conference (CCC), 2020, pp. 22:1–22:36.

M. Saeedi and I. L. Markov, "Synthesis and optimization of reversible circuits – A survey", ACM Comput. Surveys, vol. 45, no. 2, pp. 1-34, 2013.

Z. Sasanian and D. M. Miller, "NCV Realization of MCT Gates with Mixed Control", In Proceedings of the IEEE Pacific Rim Conference on Communications, Computers and Signal Processing (PACRIM), 2011, pp. 567-571.

M. Soeken and M. K. Thomsen, "White Dots do Matter: Rewriting Reversible Logic Circuits", in G. W. Dueck and D. M. Miller (Eds.), Reversible Computation, LNCS 7948, pp. 196-208, Springer, 2013.

M. Soeken, G. W. Dueck and M. D. Miller, "A fast symbolic transformation-based algorithm for reversible logic synthesis", in S. Devitt and I. Lanese I. (Eds.), Reversible Computation, LNCS 9720, pp. 307-321, Springer, 2016.

S. Stojković, M. M. Stanković and C. Moraga, "Complexity reduction of Toffoli networks based on FDD", FU: Elec. Energ., vol. 28, no. 2, pp. 251-262, 2015.

T. Toffoli, "Reversible Computing", in J. W. Baker and J. Van Leeuwen (Eds.), ALP 1980, LNCS 84, pp. 632-644, Springer, 1980.

R. Wille, M. Saeedi and R. Drechsler, "Synthesis of Reversible Functions beyond Gate Count and Quantum Cost", 2010, pp. 1-7.

A. Zulehner and R. Wille, "Simulation and Design of Quantum Circuits", in I. Ulidowski, I. Lanese, U. P. Schulz and C. Ferreira, (Eds.), Reversible Computation: Extending Horizons of Computing, LNCS 12070, pp. 60-82, Springer Open, 2020.


Refbacks

  • There are currently no refbacks.


ISSN: 0353-3670 (Print)

ISSN: 2217-5997 (Online)

COBISS.SR-ID 12826626