CDI Type-I: Quantum Diffusion and Quantum RandomWalks in Physical Systems Alexander Russell (PI), Robin C?ot´e University of Connecticut B. Project Summary A shocking theoretical discovery of the late 90?s demonstrated that a computational apparatus directly harnessing the laws of quantum mechanics could dramatically outpace any classical computer for a number of important computational problems. This instigated a broad, ongoing effort both to implement such systems and to understand their full computational power. This project focuses on quantum random walks and quantum diffusion. Quantum random walks are important algorithmic tools appearing, for example, in the the most efficient known quantum algorithms for basic problems such as element distinctness (that is, the problem of determining if an element?such as a name or a number?appears twice in a long list) and evaluation of certain logic circuits. Quantum random walks are particularly attractive from the standpoint of implementation as they are presumably simpler to faithfully implement than a general purpose quantum computer. In particular, they possess a direct connection to quantum diffusion, an area of ultracold atomic physics. Our goal is to give the first rigorous analysis of a realistic quantum random walk and, thus, a clear indication of a candidate quantum system for implementing such walks. Intellectual merit. In this proposal, we intend to join forces of two new subfields of computer science and physics, namely quantum random walks (QRW) and ultracold atomic systems. More precisely, we will explore how the tools developed to investigate quantum random walks in simple models can be adapted to more realistic situations corresponding to physical systems of interest. Conversely, we will study realistic physical systems that could be engineered to correspond to models solvable with quantum random walks. These two complementary approaches will lead to insight about the complex underlying behavior of systems where quantum diffusion is crucial. Additionally, a large class of systems in condensed matter physics and atomic, molecular, and optical physics ? such as high-temperature superconductors or quantum magnets ? are thought to be described by models, such as the Bose-Hubbard model or one of its many generalizations, where quantum diffusion plays a key role. We plan to explore how one can control such systems so that simplified experimental setups, such as ultracold Rydberg atoms or ultracold atom-ion mixtures, can be exploited to mimic the simple models where the solutions to quantum random walks (and thus quantum diffusion) are known. Broader impacts. We will continue our successful training efforts via the REU program (we have introduced dozens of students to real research topics) and graduate research guidance. Additionally, the PIs will develop and teach a multidisciplinary course entitled ?Quantum information and computation.? Within KAST (Kids Are Scientists Too), a 5-day program for 4th through 9th grade students, we will build new modules based on children?s fascination with technologies and computers. Additionally, the PIs will continue involvement in the DaVinci project, a program introducing high-school teachers to topics in engineering, mathematics, and physics that can be integrated into their high school science curricula. B-1
