The University of Illinois at Chicago

Department of Computer Science

2004-2005 Distinguished Lecturer Seminar Series

Quantum Complexity: How Fast Can Quantum Computers Sort?

Andrew C. Yao

A.M. Turing Award Recipient

Tsinghua University, Beijing, China

Wednesday, April 13, 2005
11:00 a.m., Room 1000 SEO

Abstract

In recent years remarkable progress has been made toward understanding the potential of quantum computers. For many computational problems, novel algorithms based on quantum principles have been discovered. Complementarily, certain limitations on the power of quantum computers have also been found. In this talk we examine the quantum complexity question for the basic operation of sorting numbers. As will be seen, surprisingly rich connections exist between this problem and classical mathematics. No prior knowledge of quantum computing is necessary for understanding this talk.

Brief Bio:

Professor Yao was born in Shanghai, China. He received a BS in Physics from National Taiwan University, PhD in Physics from Harvard University, and PhD in Computer Science from University of Illinois. His research interests include analysis of algorithms, computational complexity, cryptography and quantum computing. Professor Yao has been on the faculty at MIT, Stanford, UC Berkeley, and Princeton University. In 2004, he left Princeton to become a Professor of Computer Science at Tsinghua Univeristy in Beijing. He is also a Distinguished Professor-at-Large from the Chinese University of Hong Kong.

Professor Yao was recipient of the prestigious A.M. Turing Award in year 2000 for his contributions to the Theory of Computation, including Communication Complexity and Pseudorandom Number Generation. He has received numerous other honors and awards, including the George Polya Prize from SIAM, the Donald E. Knuth Prize from ACM/IEEE, and many honorary degrees. He is a member of the US National Academy of Sciences, the American Academy of Arts and Sciences, and the Chinese Academy of Sciences.

Host: Professor Jeffrey Tsai