
Quantum Computers: Algorithms and Implementations
Mon, Mar 21, 2011 @ 03:00 PM  04:00 PM
Ming Hsieh Department of Electrical and Computer Engineering
Conferences, Lectures, & Seminars
Speaker: Ben Reichardt, University of Waterloo
Talk Title: Quantum Computers: Algorithms and Implementations
Abstract: Quantum computers have the potential to deliver exponential speedups. To realize this potential, we need new quantum algorithms and new ways of implementing scalable quantum devices.
A difficulty in designing quantum algorithms is that quantum mechanics is often counterintuitive. We show that quantum computers are equivalent to a simpler model, known as span programs, that does not use quantum mechanics. Based on this equivalence, we find new algorithms, and also determine general structural properties of quantum algorithms. For example, we find a better way of composing quantum algorithms than standard classical recursion.
The main problem for implementing quantum computers is noise. We study several proposed faulttolerant quantum computer architectures in order to maximize the tolerable noise rate and minimize the overhead, while satisfying chip locality constraints. For example, by studying the propagation of errors, we modify an errorcorrection method to reduce its overhead by at least a factor of four. We also introduce a family of quantum errorcorrecting codes with useful locality and universality properties.
Biography: Ben Reichardt is an assistant professor at the Institute for Quantum Computing in the University of Waterloo. He received his Ph.D. from UC Berkeley in 2006, advised by Umesh Vazirani, and was a postdoctoral fellow at the California Institute of Technology until 2008.
Host: Todd Brun
Location: Hughes Aircraft Electrical Engineering Center (EEB)  248
Audiences: Everyone Is Invited
Contact: Gerrielyn Ramos