Theory courses

This course is an introduction to quantum information and computation aimed at graduate students. The goal of the course is to understand and familiarize with the fundamentals from an abstract point of view, while exploring several key applications. This will be almost entirely a theory course, with a small programming component (running algorithms on quantum devices in the cloud). Topics covered include: Qubits, quantum gates, and measurements. Entanglement and non-locality. Density matrix formalism. Quantum algorithms: Simon’s, Grover search, Shor’s factoring, and Hamiltonian Simulation. Quantum error-correction.

Consider a function \(f : \mathbb{R}^n \to \mathbb{R}_+\) that can be written as a sum of a large number of functions \(f = f_1 + f_2 + \cdots\) from some class. When can this sum be sparsified in the sense that f can be approximated by a (nonnegative) weighted combination of a small number of the \(\{f_i\}\)? For many classes of functions, the answer is that, surprisingly, only about \(O(n)\) summands suffice (up to logarithmic factors). When this is possible, one can address the algorithmic questions: How to efficiently construct the sparsifier, and how to use sparse representations to optimize \(f\) efficiently.

This simple question has a wealth of applications in CS (especially in big data analysis), as well as in many areas of mathematics (especially in functional analysis and convex geometry). The course will focus on the (often deep) mathematical structures underlying sparsification problems, covering things like: Leverage scores, Lewis weights, generalized linear regression, spectral sparsification of graphs, matrix concentration, generic chaining theory, subspace embeddings and dimension reduction, submodularity, and low-rank approximation in numerical linear algebra.

This is an advanced graduate-level theory course about tools from analysis and geometry that have interesting applications in algorithms, complexity theory, and ML theory. Evaluation will be based on scribe notes and (possibly) student presentations. One topic per week, choice of topics will be guided by class interest.

• Generic chaining and extrema of random processes
• The KLS conjecture and stochastic localization
• Topological methods
• High-dimensional expanders
• Noise stability on the hypercube via Brownian motion
• The edge of stability in training deep NNs

A lattice is discrete subgroup of \(\mathbb{R}^n\). Lattices are fundamental objects in discrete math with a rich set of applications to theoretical computer science, optimization and cryptography. We will see the following in this course:

• Introduction to lattices (Minkowski’s Theorems, the LLL algorithm, Knapsack cryptosystems, dual lattices, Hermite normal form, KZ-reduced basis)
• Algorithms for the Closest Vector problem (Babai’s algorithm, the Voronoi cell algorithm by Micciancio and Voulgaris)
• The Transference Theorems of Banaszczyk (Fourier analysis, the discrete Gaussian, transference theorem for Euclidean norm, transference theorem for arbitrary norms)
• Khintchine’s Flatness Theorem
• Lenstra’s algorithm for Integer programming in fixed dimension
• Lattice problems in NP intersect coNP
• Lattice-based cryptography and Learning with Errors

An introduction to the field of quantum computing from the perspective of computer science theory.

Quantum computing leverages the revolutionary potential of computers that exploit the parallelism of the quantum mechanical laws of the universe. Topics covered include:

• The axioms of quantum mechanics
• Quantum cryptography (quantum money, quantum key distribution)
• Quantum algorithms (Grover search, Shor’s algorithm)
• Quantum information theory (mixed states, measurements, and quantum channels)
• Quantum state tomography (learning and distinguishing quantum states)
• Quantum complexity theory
• Quantum error correction
• Quantum “supremacy”

Point Lattices over the reals are remarkably useful in cryptography. Among many others, the Learning With Errors (LWE) assumption has changed the landscape of cryptography in recent years. Nearly every known cryptographic objective, from signatures, non-interactive zero-knowledge, fully homomorphic encryption, to attribute based encryption, can be based on LWE. Lattices is also one of the most widely used bases for developing post-quantum and quantum cryptography, and it is a unique source of computational hardness with worst-case to average-case connections. In this course, we will delve into lattices and lattice-based cryptography. Topics covered, depending on time and interests, may include:

• basic properties of lattices,
• basic algorithms for attacking lattice problems and LWE,
• worst-case to average-case, decision to search, reduction,
• basic cryptographic constructions: pseudo-random functions, signatures, chosen-ciphertext secure encryption, etc,
• powerful cryptographic constructions: fully homomorphic encryption, attribute-based encryption, constraint pseudo-random function etc,
• lattices and quantum computation.