The success of the abstract model of classical computation in terms of bits, logical operations, algorithms, and programming language constructs makes it easy to forget that computation is a physical process. Our cherished notions of computation and information are grounded in classical mechanics, but the physics of our universe is quantum. A natural question to ask is how computation would change if we adopted a quantum mechanical, instead of a classical mechanical, model of computation.
In the early 80s, Richard Feynman, Yuri Manin, and others recognized that certain quantum effect could not be simulated efficiently on conventional computers. This observation led researchers to speculate that some difficult computational problems could be solved efficiently using these hard-to-simulate quantum effects. Slowly, a new picture of computation arose, one that gave rise to a variety of faster algorithms, novel cryptographic mechanisms, and alternative methods of communication.
In the first part of the talk, we will introduce key concepts underlying quantum computing and describe alternative quantum computational models. In the second half of the talk, we will discuss applications of quantum computing, known advantages and limitations, and briefly touch on the current state-of-the-art in building quantum computers, quantum error correction, and fault tolerance, and the many open research questions that remain.
The Stanford EE Computer Systems Colloquium (EE380) meets on Wednesdays 4:30-5:45 throughout the academic year. Talks are given before a live audience in Room B03 in the basement of the Gates Computer Science Building on the Stanford Campus. The live talks (and the videos hosted at Stanford and on YouTube) are open to the public.
Dr. Rieffel received her PhD in mathematics from the University of California Los Angeles and served as the Busemann Assistant Professor at the University of Southern California before moving to the industrial research lab FXPAL. In September 2012 she joined NASA as part of their expanding quantum computing effort that lead to the creation of NASA's Quantum Artificial Intelligence Laboratory (QuAIL). She has served as Deputy QuAIL Lead since May 2015.
Her research spans quantum information processing, computer science, and mathematics. At FXPAL, she performed a wide variety of computer science related research in areas as diverse as applied cryptography, image-based geometric reconstruction of 3D scenes, bioinformatics, video surveillance, and automated control code generation for modular robotics. Since coming to NASA, her research has focused exclusively on quantum information processing. She developed a strong and effective collaboration with the Autonomous Systems and Robotics Planning and Scheduling group at NASA Ames to jointly explore quantum annealing approaches to challenging combinatorial optimization problems that arise in planning and scheduling. She has also developed advanced techniques for error suppression in quantum annealing and performed fundamental research in measurement-based quantum computation.
She is best known for her 2011 book Quantum Computing: A Gentle Introduction, published by MIT press, jointly authored with Wolfgang Polak.
Wolfgang Polak received his PhD in Computer Science from Stanford University in 1980 for research on formal program verification.
During 5 years as lead software architect at a start-up company (now IBM) he was responsible for the design of the Rational programming environment, probably the first practical IDE.
He returned to research and, mostly as independent consultant, dabbled in a variety of fields ranging from programming environments to automatic programming, AI, machine learning, and quantum computing. For Lockheed Martin he developed an automatic programming tool that was used to generate most of the flight software for Gravity Probe B and some of the generated code is still controlling the Ikonos imaging satellite.
His joint work with Eleanor Rieffel on quantum computing first resulted in a popular tutorial which eventually grew into a text book on the subject.