Monday, May 23, 2016, 11:00 - 13:00
Tuesday, May 24, 2016, 14:30 - 16:30
Wednesday, May 25, 2016, 11:00 - 13:00
Thursday, May 26, 2016, 11:00 - 13:00
Friday, May 27, 2016, 11:00 - 13:00
If they can be built, quantum computers can factor large integers and solve the discrete log problem efficiently, thus breaking all currently deployed public-key cryptosystems, and they can solve unstructured search problems faster than classical computers, although there is some evidence that they cannot solve NP-complete problems in polynomial time.
In this course we will study the mathematical model of quantum computers, we will review the two main algorithms (factoring/ discrete log and search), and, time permitting, we will see evidence against polynomial time quantum algorithms for NP-complete problems.
I am a professor of Electrical Engineering and Computer Science at U.C. Berkeley and a senior scientist at the Simons Institute for the Theory of Computing. I am from Rome, where I studied at the Sapienza University of Rome, advised by Pierluigi Crescenzi. I have also been a post-doc at MIT (with theTheory of Computing Group) and at DIMACS, an assistant professor at Columbia University and a professor at Stanford. I am interested in Theoretical Computer Science.
The basics of linear algebra (vectors, matrices, eigenvalues, eigenvectors, determinant) and discrete probability (Bayes rule, the notion of independence, random variables) and the ability to reason about the correctness and the running time of an algorithm (say, having seen that mergesort runs in time O(n log n) and that binary search runs in time O(log n).
For more information, please visit http://cs.gssi.infn.it/course-by-luca-trevisan-on-quantum-computing/