QnTM: Quantum Channel Capacities and Quantum Complexity

QnTM：量子通道容量和量子复杂性

• 批准号: 0431787
• 负责人: Peter Shor
• 金额: $ 45万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2004
• 资助国家: 美国
• 起止时间: 2004-09-01 至 2007-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0431787&HistoricalAwards=false
• 关键词: QnTM; Quantum; Channel; Capacities; 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.

近年来，基于dna的计算的出现，以及用于制造物体、鲁棒装置和周期阵列的dna纳米技术的发展。我们建议结合这些领域，通过使用一个强大的双态DNA器件和DNA阵列组装技术原型可编程有限状态机能够执行简单的计算。目标是产生一个可编程的系统，产生输出并可重用。我们利用Wang tiles，有限状态机（换能器）和可计算函数之间的联系。其主要思想是使用DNA TX分子来表示换能器转换，并使用一系列双态DNA器件来编程输入。一旦输入被编程，换能器的计算仅通过DNA自组装获得。此外，换能器的迭代和组合也是可能的，因此可以获得所有可计算的函数。该项目由两项主要任务组成：1。模拟有限状态机的计算，输出由输入分子和TX跃迁分子组成。通过DNA双态器件和tx分子的程序输入获得换能器计算。Intelectual优点。该项目是一个纳米机器的原型，它具有潜在的可编程性，并产生的输出可以作为新设备的输入，或者作为纳米电子学中使用的纳米结构的组织和生长的模板。所提出的机器有可能通过算法控制这种增长。从理论上讲，机器的设计和编码（局部和全局）纠错的需要将导致算法模式设计中新技术的发展。更广泛的影响。基于DNA的计算研究依赖于许多学科，如计算机科学、DNA化学、核酸酶学、热力学和分子物理学。很少有人在准备充分的情况下进入。在这个项目的过程中，我们将尝试为这个问题提供一些补救措施。参与这项工作的研究生、本科生和高中生将受到独特的训练，并将成为独特的跨学科研究科学家。三名研究生（两名在纽约大学，一名在南佛罗里达大学）将通过该奖项接受研究生培训。他们会见面，熟悉对方大学同事的思维和方法论。此外，我们将在项目中包括本科生，以获得将计算机科学与DNAnanotechnology相结合的经验。我们的目标是让高中生参与他们有资格参与的部分工作（例如，不需要使用辐射的计算和实验）。除了他们自己的纳米技术和数学学科，PI和co-PI是基于dna的计算社区的杰出成员。这个社区的两个方面都认识到它正在与结构DNA纳米技术融合。为了认识到这一跨学科现象，PI和联合PI参与创立了“国际纳米尺度科学、计算和工程学会”（分别担任主席和财务主管），目的是促进参与社区成员之间的交流，并通过为年轻成员提供认可和思想论坛来表彰和促进他们的职业发展。