Quantum Computing

  • Date May 23-27, 2016
  • Room GSSI Room D
  • Speaker Luca Trevisan (U.C. Berkeley, Simons Institute for the Theory of Computing)
  • Area Computer Science


Due to the limited availability of seats, anyone willing to attend the course (with the exception of 1st Year students of the GSSI-CS Phd Program) is kindly invited to send an email, containing First Name, Last Name and Institution of the participant(s), to This email address is being protected from spambots. You need JavaScript enabled to view it., with subject “Quantum Computing Course Registration”. Reservations will be accepted until all seats are taken, on a first come first served basis.


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