Title: Quantum Computing: What’s It Good For?

Speaker: Mario Szegedy, Rutgers Computer Science Department

Abstract: In recent years we hear more and more often about a mysterious new computing paradigm, in which factoring large numbers, and hence breaking cryptosystems, is possible in polynomial time. We also hear that an algorithm in this model can search for a key in a data of size N in time, which is only square root of N.

How much knowledge of quantum mechanics is needed to understand this model? What is quantum computing? How are quantum computers faster than classical ones?

What are their limitations?

In this introductory talk we define quantum circuits, show how they operate, introduce the notion of quantum black box, give some open problems, say some words about the future of quantum computing.