#### Important Notice:

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 **seminars-cs@gssi.infn.it**, with subject “Quantum Computing Course Registration”. Reservations will be accepted until all seats are taken, on a first come first served basis.

**Speaker:** Luca Trevisan (U.C. Berkeley, Simons Institute for the Theory of Computing)

**Title:** Quantum Computing

**Place:** GSSI (Room D)

**Schedule:**

Monday 23rd May, 2016, 11:00 – 13:00

Tuesday 24th May, 2016, 14:30 – 16:30

Wednesday 25th May, 2016, 14:30 – 16:30

Thursday 26th May, 2016, 11:00 – 13:00

Friday 27th May, 2016, 11:00 – 13:00

**Abstract:**

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.

**Prerequisites:**

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).