QnTM: Quantum Channel Capacities and Quantum Complexity

点击翻译按钮获取中文摘要

Recent years have seen the advent of DNA-based computation, as well as the development of aDNA nanotechnology that produces objects, robust devices and periodic arrays. We propose tocombine these areas, by using a robust 2-state DNA device and DNA array assembly techniquesto prototype a programmable finite state machine capable of performing simple computations.The goal is to produce a system that is programmable, produces an output and is reusable.We exploit connections between Wang tiles, finite state machines (transducers) and com-putable functions. The main idea uses DNA TX molecules to represent transducer transitionsand a sequence of 2-state DNA devices to program the input. Once the input is programmed,the computation of the transducer is obtained solely by DNA self-assembly. Further more, iter-ations and composition of transducers is also possible and hence all computable functions canbe obtained.The project is composed of two major tasks,1. To simulate computation by a finite state machine with output by a single assembly ofinput molecules and TX transition molecules.2. To obtain transducer computation with a programmale input by DNA 2-state devices andTX molecules.Intelectual Merit. The project prototypes a nanomachine that is potentially programmableand produces an output that can serve as an input in a new device or as a template for orga-nization and growth of nanostructures used in nanoelectronics. The proposed machine has apotential for an algorithmic control of this growth. Theoretically, the design of the machine andthe need for encoding (locally and globally) that is error correcting will lead to development ofnew techniques in algorithmic pattern design.Broader Impact. Research in DNA-based computation relies on many disciplines, such ascomputer science, DNA chemistry, nucleic acid enzymology, thermodynamics and molecularphysics. Few individuals enter in to it with adequate preparation. We will attempt to providesome remedy for this problem during the course of this project. The graduate, undergraduateand high school students who participate in this work will be uniquely trained and will beprepared as unique interdisciplinary research scientists. Three graduate students (two at NewYork University and one at the University of South Florida) will receive graduate trainingthrough this award. They will meet with each other, and become familiar with the thinking andmethodologies of their opposite colleagues in the other university. In addition, we will includean undergraduate in the project, to gain experience in combining computer science with DNAnanotechnology. We aim to include a high school student in the parts of the work for whichthey are eligible (e.g., computation and experiments not entailing the use of radiation).Besides their own nanotechnological and mathematical disciplines, the PI and the co-PI areprominent members of the DNA-based computation community. Both facets of this commu-nity recognize that it is converging with structural DNA nanotechnology. In recognition ofthis interdisciplinary phenomenon, the PI and the co-PI are involved in founding (as presidentand treasurer, respectively) the \International Society for Nanoscale Science, Computation andEngineering" with a goal to facilitate communication among the members of the participatingcommunities, and to recognize and promote the careers of the younger members, by offeringthem recognition and a forum for their ideas.