Department of Computer Science
Yale University
Alan J. Perlis Lecture Series

Sign up with speaker

April 7, 2005
10:30 a.m., AKW 200

SPEAKER: Andrew C. Yao, Tsinghua University, Beijing, China
TITLE: Quantum Complexity: How Fast Can Quantum Computers Sort?

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.