Quantum Computing Day 1: Introduction to Quantum Computing

Google Tech Talks December, 6 2007 ABSTRACT This tech talk series explores the enormous opportunities afforded by the emerging field of quantum computing. The exploitation of quantum phenomena not only offers tremendous speed-ups for important algorithms but may also prove key to achieving genuine synthetic intelligence. We argue that understanding higher brain function requires references to quantum mechanics as well. These talks look at the topic of quantum computing from mathematical, engineering and neurobiological perspectives, and we attempt to present the material so that the base concepts can be understood by listeners with no background in quantum physics. This first talk of the series introduces the basic concepts of quantum computing. We start by looking at the difference in describing a classical and a quantum mechanical system. The talk discusses the Turing machine in quantum mechanical terms and introduces the notion of a qubit. We study the gate model of quantum computing and look at the famous quantum algorithms of Deutsch, Grover and Shor. Finally we talk about decoherence and how it destroys superposition states which is the main obstacle to building large scale quantum computers. We clarify widely held misconceptions about decoherence and explain that environmental interaction tends to choose a basis in state space in which the system decoheres while leaving coherences in other coordinate systems intact. Speaker: Hartmut Neven