[en] The Toffoli and Fredkin gates were suggested as a means to exhibit logic reversibility and thereby reduce energy dissipation associated with logic operations in dense computing circuits. We present a construction of the logically reversible Toffoli and Fredkin gates by implementing a library of predesigned Mg2+-dependent DNAzymes and their respective substrates. Although the logical reversibility, for which each set of inputs uniquely correlates to a set of outputs, is demonstrated, the systems manifest thermodynamic irreversibility originating from two quite distinct and nonrelated phenomena. (i) The physical readout of the gates is by fluorescence that depletes the population of the final state of the machine. This irreversible, heat-releasing process is needed for the generation of the output. (ii) The DNAzyme-powered logic gates are made to operate at a finite rate by invoking downhill energy-releasing processes. Even though the three bits of Toffoli’s and Fredkin’s logically reversible gates manifest thermodynamic irreversibility, we suggest that these gates could have important practical implication in future nanomedicine.
Disciplines :
Physical, chemical, mathematical & earth Sciences: Multidisciplinary, general & others
Author, co-author :
Orbach, Ron
Remacle, Françoise ; Université de Liège - ULiège > Département de chimie (sciences) > Laboratoire de chimie physique théorique
Levine, Raphaël David
Willner, Itamar
Language :
English
Title :
Logic reversibility and thermodynamic irreversibility demonstrated by DNAzyme-based Toffoli and Fredkin logic gates
Publication date :
2012
Journal title :
Proceedings of the National Academy of Sciences of the United States of America
ISSN :
0027-8424
eISSN :
1091-6490
Publisher :
National Academy of Sciences, Washington, United States - District of Columbia
Landauer R (1988) Dissipation and noise immunity in computation and communication. Nature 335(6193):779-784.
Hayes B (2006) Reverse engineering. Sci Am 94(2):107-111.
Bennett CH (1973) Logical reversibility of computation. IBM J Res Develop 17(6):525-532.
Bennett CH (1982) The thermodynamics of computation - A review. Int J Theor Phys 21(12):905-940.
Landauer R (1961) Irreversibility and heat generation in the computing process. IBM J Res Develop 5(1-2):183-191.
Landauer R (1996) Minimal energy requirements in communication. Science 272(5270):1914-1918.
Toffoli T (1982) Physics and computation. Int J Theor Phys 21(3-4):165-175.
Fredkin E, Toffoli T (1982) Conservative logic. Int J Theor Phys 21(3-4):219-253.
Remón P, et al. (2011) Molecular implementation of sequential and reversible logic through photochromic energy transfer switching. Chemistry 17(23):6492-6500.
Remón P, et al. (2009) Reversible molecular logic: A photophysical example of a Feynman gate. Chemphyschem 10(12):2004-2007.
Cory DG, et al. (1998) Experimental quantum error correction. Phys Rev Lett 81(10):2152-2155. (Pubitemid 128623092)
Lanyon BP, et al. (2009) Simplifying quantum logic using higher-dimensional Hilbert spaces. Nat Phys 5(2):134-140.
Monz T, et al. (2009) Realization of the quantum Toffoli gate with trapped ions. Phys Rev Lett 102(4):040501.
Fedorov A, Steffen L, Baur M, da Silva MP, Wallraff A (2012) Implementation of a Toffoli gate with superconducting circuits. Nature 481(7380):170-172.
Reed MD, et al. (2012) Realization of three-qubit quantum error correction with superconducting circuits. Nature 482(7385):382-385.
Genot AJ, Bath J, Turberfield AJ (2011) Reversible logic circuits made of DNA. J Am Chem Soc 133(50):20080-20083.
Benenson Y (2009) Biocomputers: From test tubes to live cells. Mol Biosyst 5(7):675-685.
Stojanovic MN (2008) Molecular computing with deoxyribozymes. Prog Nucleic Acid Res Mol Biol 82:199-217.
Willner I, Shlyahovsky B, Zayats M, Willner B (2008) DNAzymes for sensing, nanobiotechnology and logic gate applications. Chem Soc Rev 37(6):1153-1165.
Saghatelian A, Völcker NH, Guckian KM, Lin VS, Ghadiri MR (2003) DNA-based photonic logic gates: AND, NAND, and INHIBIT. J Am Chem Soc 125(2):346-347. (Pubitemid 36077851)
Stojanovic MN, Stefanovic D (2003) A deoxyribozyme-based molecular automaton. Nat Biotechnol 21(9):1069-1074. (Pubitemid 37064737)
Stojanovic MN, et al. (2005) Deoxyribozyme-based ligase logic gates and their initial circuits. J Am Chem Soc 127(19):6914-6915. (Pubitemid 40676695)
Voelcker NH, Guckian KM, Saghatelian A, Ghadiri MR (2008) Sequence-addressable DNA logic. Small 4(4):427-431. (Pubitemid 351641617)
Rothemund PWK, Papadakis N, Winfree E (2004) Algorithmic self-assembly of DNA Sierpinski triangles. PLoS Biol 2(12):e424.
Seelig G, Yurke B, Winfree E (2006) Catalyzed relaxation of a metastable DNA fuel. J Am Chem Soc 128(37):12211-12220. (Pubitemid 44413852)
Qian L, Winfree E (2011) Scaling up digital circuit computation with DNA strand displacement cascades. Science 332(6034):1196-1201.
Benenson Y, Gil B, Ben-Dor U, Adar R, Shapiro E (2004) An autonomous molecular computer for logical control of gene expression. Nature 429(6990):423-429. (Pubitemid 38715134)
Benenson Y, Adar R, Paz-Elizur T, Livneh Z, Shapiro E (2003) DNA molecule provides a computing machine with both data and fuel. Proc Natl Acad Sci USA 100(5):2191-2196. (Pubitemid 36297475)
Elbaz J, et al. (2010) DNA computing circuits using libraries of DNAzyme subunits. Nat Nanotechnol 5(6):417-422.
Breaker RR, Joyce GF (1995) A DNA enzyme with Mg(2+)-dependent RNA phosphoesterase activity. Chem Biol 2(10):655-660.
von Neumann J (1955) Mathematical Foundations of Quantum Mechanics (Princeton Univ Press, Princeton, NJ).
Elbaz J, Wang F, Remacle F, Willner I (2012) pH-Programmable DNA logic arrays powered by modular DNAzyme libraries. Nano Lett, 10.1021/nl300051g.
Klein JP, Leete TH, Rubin H (1999) A biomolecular implementation of logically reversible computation with minimal energy dissipation. Biosystems 52(1-3):15-23. (Pubitemid 29518345)
Kasinski AL, Slack FJ (2011) Epigenetics and genetics. MicroRNAs en route to the clinic: Progress in validating and targeting microRNAs for cancer therapy. Nat Rev Cancer 11(12):849-864.
Lujambio A, Lowe SW (2012) The microcosmos of cancer. Nature 482(7385):347-355.
Dirks RM, Bois JS, Schaeffer JM, Winfree E, Pierce NA (2007) Thermodynamic analysis of interacting nucleic acid strands. SIAM Rev 49(1):65-88. (Pubitemid 46351352)
