Events Calendar

Quantum Computers: Algorithms and Implementations

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 fault-tolerant 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 error-correction method to reduce its overhead by at least a factor of four. We also introduce a family of quantum error-correcting 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