Course 2024-2025 a.y.

Unit 1 (Computability - introduction)

·       Course overview

·       Introduction

·       Turing Machine (TM)

Unit 2 (Computability – more on TM)

·       More on the definition of TM

·       Decidable and Recognizable languages

·       Variants of TM

·       Simulation

Unit 3 (Computability – undecidability)

·       The Church-Turing Thesis

·       Examples of decidable languages

·       The Halting problem

Unit 4 (Computability – undecidability contd.)

·       More non-decidable problems

·       Reductions

Unit 5 (Computability – Rice’s theorem)

·       Rice’s Theorem

·       Post Correspondence Problem

·       Wrap up computability

Unit 6 (Complexity - Introduction)

·       Definition of time complexity

·       Complexity of single vs Multiple Tape TM’s

·       PTIME, PATH

Unit 7 (Complexity – The class NP)

·       Non-deterministic TM

·       Poly-time verifiability

·       The classes NP and coNP

Unit 8 (Complexity – NP completeness)

·       Poly-time reducibility

·       NP completeness

·       Existence of NP-complete problems

Unit 9 (Complexity – Cook-Levin)

·       Cook-Levin Theorem

·       More NP-complete problems

·       Decision vs. Search

Unit 10 (Complexity – The class PSPACE)

·       Cook/Karp/Levin reductions

·       Coping with NP-hardness

·       Space complexity

Unit 11 (Introduction to Quantum Computing):

·       Probabilistic Computing

·       Quantum Computing

·       States and Dirac Notation

Unit 12 (Computing with Qubits):

·       Measurements and Unitaries

·       Quantum Circuits

·       Quantum Zeno Effect

Unit 13 (Entanglement):

·       Operating on General States

·       Product States and Entangled States

Unit 14 (Quantum Complexity Theory):

·       Quantum Oracles

·       Deutsch-Josza Problem

Unit 15 (Quantum Algorithms I):

·       Bernstein-Vazirani Algorithm

·       Simon’s Algorithm

Unit 16 (Quantum Algorithms II):

·       Quantum Fourier Transform

·       Shor’s Algorithm

Unit 17 (Quantum Algorithms II):

·       Unstructured Search

·       Grover’s Algorithm

Unit 18 (Non-local Games):

·       The CHSH Game

·       Tsirelson’s Theorem

Unit 19 (No-Cloning):

·       The No-Cloning Theorem

·       Quantum Mone

The most important skill that the students are expected to pick up during this course is the ability to recognize and interpret computational intractability in case it is encountered. The course aims to develop a solid conceptual understanding of notions related to computation:

·       The concept of universal models of computation (such as Turing machines), that capture our intuitive notion of computation and allow us to reason about the capabilities of computers in a technology-independent manner.

·       The existence of intrinsic limits to computation. Computational problems that cannot be solved by any algorithm whatsoever (undecidability), and problems that are solvable but require unreasonable computational resources (computational complexity).

·       The notion of nondeterminism and in particular the conceptual difference between finding a solution and verifying that a given solution is correct.

·       The representation of computational problems, and the distinction/relationships between decision and search problems.

·       The notion of a reduction between computational problems and its implications on the relative complexity of the problems.

·       How to use the laws of quantum mechanics for computation, and the difference with respect to classical probabilistic computing.

·       How to rigorously analyze quantum algorithms

• Recognize problems that are NP-complete, and be able to devise simple NP-completeness proofs
• Recognize problems that are  undecidable, and be able to devise simple undecidability proofs
• Apply the idea of a reduction among computational problems
• Recognize computational hardness/easiness, be it classical or quantum

• Lectures
• Guest speaker's talks (in class or in distance)

Biweekly homework assignments (4-5 questions each) will give you feedback on how you are doing and will help you internalize the material studied.

Assessment will be the same for attending and non-attending students. The final exam is written (90% of the grade) and consists of open-ended questions, some of which will test the student's understanding of the concepts developed during the course and some of which will test the student's ability to apply such concepts to new contexts, for example to prove the NP-completeness of a new problem, to prove the undecidability of a new problem, or to prove/assess a quantum algorithm. It will also test knowledge of complexity and computability classes and the relations between them, and the definition of languages and their interrelations.

There is no required textbook. Recommended textbooks will be communicated to the students at the start of classes. Lecture slides and notes will be provided for selected topics.