2023 Graduate Summer School Course Descriptions
Week 1 (July 17 - July 21)
Andras: Quantum Fourier transform beyond Shor's algorithm
Omar: Quantum information theory
Srinivasan: Overview of quantum learning theory
Week 2 (July 24 - July 28)
Ewin: Quantum and quantum-inspired linear algebra
Nicolas: Quantum LDPC codes
Yassine: Quantum query complexity
Week 3 (July 31 - Aug 4)
Bill: Computational complexity of near-term quantum experiments
Jeongwan: Topological aspects of quantum codes
Sandy: Quantum Hamiltonian complexity
Srinivasan Arunachalam (IBM T.J. Watson Research Center)
Title: Overview of quantum learning theory
In recent times, there have been several exciting results in the field of quantum learning. In these lectures, I'll focus on three flavors of results in this field:
(i) Learning Boolean functions. Here there is an unknown class of Boolean functions, what are the strengths and weaknesses of quantum examples for learning these concept classes?
(ii) Learning quantum states. Here there is an unknown class of quantum states, and the goal is to learn the unknown state given copies of the state. There have also been results for learning structured classes of quantum states, reducing the sample and time complexity of learning.
(iii) More recently, there has been few works on learning distributions obtained from quantum circuits and separations for learning tasks given access to entangled and separable measurements.
The goal of these lectures is to introduce these directions of research, give an overview of the main results in these areas and discuss the main proof techniques used towards proving them. I will not be assuming any prior knowledge of quantum learning.
Nicolas Delfosse (Microsoft Research)
Title: Quantum LDPC codes
The surface code is the most popular quantum error code for the design of a large-scale fault-tolerant quantum computer but it leads to a huge overhead because each logical qubit is encoded into thousands of physical qubits. This course is about quantum Low-Density Parity-Check (LDPC) codes which is a class of quantum error correction codes that promises to reduce the overhead for fault-tolerant quantum computation. We will first review the necessary background on quantum error correction. Then, we will discuss different constructions of quantum LDPC codes, their decoding algorithms and their syndrome extraction circuits.
Omar Fawzi (Ecole Normale Superieure de Lyon)
Title: Quantum information theory
Shannon laid the foundations of information theory in 1948 by formulating a mathematical theory for studying information storage and transmission. In particular, his noisy channel coding theorem characterizes the fundamental limits of information transmission in the presence of noise. The guiding question for this course will be to explore the analogous quantum problem: information transmission in the presence of quantum noise. In order to be able to formulate and provide answers to this question, we will introduce many fundamental notions about state discrimination, quantum channels and quantum entropy measures.
Bill Fefferman (The University of Chicago)
Title: Computational complexity of near-term quantum experiments
A critical goal for the field of quantum computation is experimental quantum advantage -- a demonstration of any quantum computation that is prohibitively hard for classical computers. Quantum advantage is both a necessary milestone on the path to useful, fault-tolerant quantum computers as well as a test of quantum theory in the realm of
high complexity. In these lectures I will discuss the theory of near-term experimental quantum advantage. I will highlight the current evidence for believing that near-term quantum experiments can solve problems that are classically intractable as well as give an overview of the state of classical simulation algorithms for these experiments.
Andras Gilyén (Renyi Institute)
Title: Quantum Fourier transform beyond Shor's algorithm
The efficiency of Quantum Fourier transform (QFT) is the key ingredient in the exponential speed-up provided by Shor's algorithm and its generalization -- the hidden subgroup problem. In recent years several new applications of QFT were found that do not hinge upon uncovering some hidden algebraic structure, and we will explore those directions. Jordan's gradient computation algorithm, which is a common generalization of phase estimation an the Bernstein-Vazirani algorithm, is behind many such new applications, ranging from convex optimization to distribution learning and quantum tomography. We will also explore recent improvements over vanilla phase estimation, such as the removal of "bias" and a coherent way of boosting, which are important for some of the new applications. Finally, we will look at QFT in the Heisenberg picture, discuss operator Fourier transform, and its relevance to quantum computing.
Jeongwan Haah (Microsoft Research)
Title: Topological aspects of quantum codes
Perhaps the most important quantum code of all is the surface code for expected practical reasons and for its connection to topological phases of matter. In various aspects the two-dimensional surface code is extreme, which I plan to discuss in these lectures. Specifically, I will explain that (i) local codes in one-dimension cannot achieve large code distance, (ii) two-dimensional local codes can only achieve code distance that is linear in the linear system size L, (iii) the number of logical qubits in d-dimensional local codes can only be O(L^{d-2}), and (iv) two-dimensional translation invariant codes are always surface codes. In the last lecture, I will change the theme and discuss triorthogonal codes that are useful for magic state distillation.
Yassine Hamoudi (University of California, Berkeley)
Title: Quantum query complexity
Quantum query complexity offers one of the most fruitful models of computation for the study of quantum algorithms. It has featured many significant quantum speedups, from the Bernstein-Vazirani algorithm to the recent Yamakawa-Zhandry supremacy breakthrough. The limits of quantum queries have been questioned since the early days of quantum computing. This led to the development of two fundamental lower bound techniques: the polynomial and the adversary methods. The focus of this course will be to introduce these methods and to present some of their new variants, such as the compressed oracle technique. We will also consider the role of duals in these methods and how they can lead to tight bounds or even new algorithms.
Sandy Irani (University of California, Irvine)
Title: Quantum Hamiltonian complexity
One of the goals of quantum information theory is to understand quantum systems from the standpoint of computational complexity. How difficult is it to compute fundamental properties of a quantum system or simulate a particular system over time? Physicists have been using computers for decades to understand various aspects of quantum systems, but these methods are typically heuristic and achieve success on only limited classes of systems. In this course, we will approach these problems from a formal, complexity-theoretic point of view. In particular, one of the most basic properties of a system is its lowest energy state or ground state. We will focus on the complexity of ground states of finite and infinite systems and the computational resources required to compute them.
Ewin Tang (University of Washington)
Title: Quantum and quantum-inspired linear algebra
An exciting recent line of work unifies many interesting quantum algorithms under a powerful linear algebraic framework known as "quantum singular value transformation" (QSVT). We'll introduce this framework, build some tools in polynomial approximation that are helpful for applying it, and investigate what kinds of results it can achieve. Our goal will be to understand how and when to use QSVT in quantum algorithm design, and ultimately, whether it can reveal new quantum speedups for interesting problems in data analysis, machine learning, or quantum simulation.