Talk Titles and Abstracts

Title: Shadow Tomography of Quantum States: Progress and Prospects

Speaker: Scott Aaronson (University of Texas at Austin)

Abstract: Given an unknown quantum state rho, and a known list of two-outcome measurements E_1,...,E_M, "shadow tomography" is the task of estimating the probability that each E_i accepts rho, by carefully measuring only a few copies of rho. In 2018, I gave the first nontrivial protocol for this task. In 2019, Guy Rothblum and I exploited a new connection between gentle measurement of quantum states and the field of differential privacy, to give a protocol that requires fewer copies of rho in some cases, and has the additional advantage of being online (that is, the measurements are processed one at a time). Huge challenges remain in making shadow tomography practical with near-term devices; extremely recently Huang, Kueng, and Preskill took some promising steps in that direction. I'll survey these developments and the challenges that remain.

Papers:

https://www.scottaaronson.com/papers/batch.pdf

https://www.scottaaronson.com/papers/dpgentle.pdf

https://arxiv.org/abs/2002.08953

Title: Sample-efficient learning of quantum many-body systems

Speaker: Srinivasan Arunachalam (IBM T. J. Watson Research Center)

Abstract: We study the problem of learning the Hamiltonian of a quantum many-body system given samples from its Gibbs (thermal) state. The classical analog of this problem, known as learning graphical models or Boltzmann machines, is a well-studied question in machine learning and statistics. In this work, we give the first sample-efficient algorithm for the quantum Hamiltonian learning problem. In particular, we prove that polynomially many samples in the number of particles (qudits) are necessary and sufficient for learning the parameters of a spatially local Hamiltonian in l_2-norm. Our main contribution is in establishing the strong convexity of the log-partition function of quantum many-body systems, which along with the maximum entropy estimation yields our sample-efficient algorithm. Our work paves the way toward a more rigorous application of machine learning techniques to quantum many-body problems.

(Joint work with Anurag Anshu, Tomotaka Kuwahara, Mehdi Soleimanifar)

Title: Time Out of Joint: Reparametrization Invariant Tools for Time Series

Speaker: Yuliy Baryshnikov (University of Illinois at Urbana-Champaign)

Abstract: An overwhelming majority of tools to process time series rely on harmonic analysis, depending in turn on the structure of timeline as a homogeneous space. What reparametrization invariant tools might look like, - say, if we want to study phenomena that are cyclic but not periodic? I will describe a specific tool used to recover cyclic structures from time series, and a few of applications in economics or neurophysiology.

Title: Information, reversibility, and the thermodynamics of fault tolerance

Speaker: Charles H. Bennett (IBM T. J. Watson Research Center)

Abstract: Babbage likened information to grain, a fungible commodity kept in a "store" and processed in a "mill." This intuition was spectacularly confirmed by Shannon, but is not quite right. Quantum information, indeed even classical information, is subtly different from any material stuff. The failure of another imagined stuff, caloric, led to the invention of entropy, and the discovery of its fundamental role throughout science. Though computation is in principle reversible, costing no more than the (generally negligible) free energy difference between output and input, real computers dissipate much more free energy, chiefly because they need to operate at finite speed and correct errors caused by non-ideal hardware. Von Neumann's insight that arbitrarily large reliably computations can be performed on unreliable hardware has proved central to quantum information processing, but, like von Neumann, present day theorists and practitioners of fault tolerance care more about the possibility of correcting errors than the thermodynamic cost of doing so. I suspect that there is an elegant, and possibly useful, theory of the thermodynamics of fault-tolerance waiting to be elucidated, with the help of insights from biomolecular machines and chemical engineering processes like fractional distillation and isotope separation.

Title: Grand unification of quantum algorithms

Speaker: Isaac Chuang (Massachusetts Institute of Technology)

Abstract: Quantum search, factoring, and simulation are the three main historical branches of modern quantum algorithms. These can now all be understood as instances of one simple construction, employing signal processing methods to systematically modify the singular values of a block-encoded matrix. The intuition of single qubit dynamics plays a remarkable and central role in this construction.

Title: Randomization in Numerical Linear Algebra (RandNLA): approximating the log-determinant and the Von Neumann entropy

Speaker: Petros Drineas (Purdue University)

Abstract: The introduction of randomization in the design and analysis of algorithms for matrix computations (such as matrix multiplication, regression, the Singular Value Decomposition (SVD), etc.) over the past 20 years provided a new paradigm and a complementary perspective to traditional numerical linear algebra approaches. These novel approaches were motivated by technological developments in many areas of scientific research that permit the automatic generation of Big Data, which are often modeled as matrices. In this talk, we will primarily focus how such approaches can be used to design fast algorithms for approximating matrix quantities such as the log-determinant and the Von Neumann entropy.

Title: Indeterminism in Physics and Intuitionistic Mathematics

Speaker: Nicolas Gisin (University of Geneva)

Abstract: Physics is formulated in terms of timeless axiomatic mathematics. However, time is essential in all our stories, in particular in physics. For example, to think of an event is to think of something in time. A formulation of physics based of intuitionism, a constructive form of mathematics built on time-evolving processes, would offer a perspective that is closer to our experience of physical reality and may help bridging the gap between static relativity and quantum indeterminism.

Historically, intuitionistic mathematics was introduced by Brouwer with a very subjectivist view where an idealized mathematician continuously produces new information by solving conjectures. Here, in contrast, I’ll introduce intuitionism as an objective mathematics that incorporates a dynamical/creative time and an open future. Standard mathematics appears as the view from the “end of time” and the usual real numbers appear as the hidden variables of classical physics.

Title: The quantum information lens on optimization and many-body physics

Speaker: Aram Harrow (Massachusetts Institute of Technology)

Abstract: Quantum information theory began by developing quantum analogues of concepts from classical information theory like channel capacity, compression rates, and hypothesis testing. I will talk about how these ideas have found productive application in other areas of computer science, math and physics. One tool in particular - the conditional mutual information - has been useful for understanding applications ranging from classical optimization algorithms to topological order in many-body quantum systems.

Title: Types and capacities of bosonic Gaussian observables

Speaker: Alexander Holevo (Steklov Mathematical Institute)

Abstract: The notion of quantum channel presupposed quantumness of both the input and output systems, making necessary a separate treatment of quantum observables, which do not allow a simple reduction to quantum channels in the continuous variable (CV) case, contrary to the discrete case. Thus we are led to the study of quantum measurement channels, which map CV quantum input into CV classical output, and to computation of their information-processing and entropic characteristics. A distinguished class of the CV measurement channels is constituted by multimode bosonic Gaussian observables. The structure theorem for general quantum Gaussian observable is proved, establishing decomposition into three basic types, roughly corresponding to heterodyning, noisy and noiseless homodyning, with classical linear post-processing. The main entropic and information processing characteristics are computed depending on the type of observable.

Title: Computational complexity, mathematical, and statistical aspects of NISQ computers.

Speaker: Gil Kalai (Hebrew University of Jerusalem)

Abstract: Noisy Intermediate-Scale Quantum (NISQ) Computers hold the key for important theoretical and experimental questions regarding quantum computers. In the lecture I will describe some questions about computational complexity, mathematics, and statistics which arose in my study of NISQ systems and are related to

a) My general argument "against" quantum computer,

b) My analysis (with Yosi Rinot and Tomer Shoham) of the Google 2019 "huge quantum advantage" experiment.


Relevant papers:

Yosef Rinott, Tomer Shoham and Gil Kalai, Statistical aspects of the quantum supremacy demonstration, https://gilkalai.files.wordpress.com/2019/11/stat-quantum2.pdf

Gil Kalai, The Argument against Quantum Computers, the Quantum Laws of Nature, and Google’s Supremacy Claims, https://gilkalai.files.wordpress.com/2020/08/laws-blog2.pdf

Gil Kalai, Three puzzles on mathematics, computations, and games, https://gilkalai.files.wordpress.com/2019/09/main-pr.pdf

Title: Why Deep Learning Works: Traditional and Heavy-Tailed Implicit Self-Regularization in Deep Neural Networks

Speaker: Michael Mahoney (University of California at Berkeley)

Abstract: While deep neural networks (DNNs) have achieved remarkable success in computer vision and natural language processing, they are complex, heavily-engineered, often ad hoc systems, and progress toward understanding why they work (arguably a prerequisite for using them in consumer-sensitive and scientific applications) has been much more modest. To understand why deep learning works, Random Matrix Theory (RMT) has been applied to analyze the weight matrices of DNNs, including both production quality, pre-trained models and smaller models trained from scratch. Empirical and theoretical results clearly indicate that the DNN training process itself implicitly implements a form of self-regularization, implicitly sculpting a more regularized energy or penalty landscape. Building on results in RMT, most notably its extension to Universality classes of Heavy-Tailed matrices, and applying them to these empirical results, we develop a phenomenological theory to identify 5+1 Phases of Training, corresponding to increasing amounts of implicit self-regularization. For smaller and/or older DNNs, this implicit self-regularization is like traditional Tikhonov regularization, in that there appears to be a "size scale" separating signal from noise. For state-of-the-art DNNs, however, we identify a novel form of heavy-tailed self-regularization, similar to the self-organization seen in the statistical physics of disordered but strongly-correlated systems. We will describe validating predictions of this theory; how this can explain the so-called generalization gap; and how one can use it to develop novel metrics that predict trends in generalization accuracies for pre-trained production-scale DNNs. Coupled with work on energy landscape theory and heavy-tailed spin glasses, it also provides an explanation of why deep learning works.

Title: Using information to learn what matters

Speaker: Ilya Nemenman (Emory University)

Abstract: Information theory was formulated by Shannon as the theory of communication. However, it has become a popular tool for answering a related — but a different — set of questions: namely, which features of a system are essential for its description, and therefore, must be preserved in a model describing it? I will walk us through a series of examples in different biological systems, where information theory has been used in this way.

Title: Language and Representation in the Brain

Speaker: Christos H. Papadimitriou (Columbia University)

Abstract: How does the brain beget the mind? How do molecules, cells and synapses effect reasoning, intelligence, language? Despite dazzling progress in experimental neuroscience, as well as in cognitive science at the other extreme of scale, we do not seem to be making progress in the overarching question -- the gap is huge and a completely new approach seems to be required. As Richard Axel recently put it: "We don't have a logic for the transformation of neural activity into thought [...]."

What kind of formal system would qualify as this "logic"?

I will present a computational system whose basic data structure is the assembly (large population of neurons representing a concept, word, etc. --, and which is informed by recent progress in understanding how language happens in the brain.

Joint work with Santosh Vempala, Dan Mitropolsky, Mike Collins, and Wolfgang Maass.

Title: Quantum Mechanics and Physical Laws in a Non-deterministic World

Speaker: Sandu Popescu (University of Bristol)

Abstract: Quantum mechanics is fundamentally different from all that came before in almost every aspect. But, as far as I can see now, there is one property that stands above all when we try to understand what quantum mechanics is all about: quantum mechanics is our first theory of Nature that is non-deterministic at a fundamental level. Long considered an unpleasant aspect, non-determinism is anything but: Non-determinism enables new freedoms. Phenomena that could not occur in deterministic theories because they would violate some basic laws of nature become possible in non-deterministic theories, under the cover of randomness.

A famous example is nonlocality. In a deterministic world, if something acting in one place would instantaneously produce effects somewhere else, it would violate relativity; non-determinism allows it. Recently many more fundamental aspects of nature in which non-determinism is the key have been discovered.

Exploring the full extent of the freedoms allowed by non-determinism in quantum mechanics as well as in arbitrary theories allows on one hand to better understand quantum mechanics and, on other hand, to see what else might be beyond. In my talk I will describe some of the basic ideas of this line of research.

PS. No knowledge of Quantum Mechanics is necessary for understanding the talk.

Title: Information-theoretic computational rationality

Speaker: Chris Sims (Rensselaer Polytechnic Institute)

Abstract: Cognitive science today rests upon an uneasy tension. On the one hand, even mundane aspects of cognition, such as the motor behavior of a young child, far outstrip the capabilities of the most advanced models available in AI and machine learning. On the other hand, we know from decades of research in psychology that the human mind is also astonishingly limited. Humans minds face strict limits on attention, working memory, perception, and other basic cognitive faculties. In this talk, I will discuss an approach for resolving this tension that is gaining momentum in both AI and cognitive science, known as information-theoretic computational rationality. According to this approach, the mind utilizes computations and algorithms that maximize the expected utility of behavior while subject to constraints on the ability to store, manipulate, and process information. Using examples from research on perception, memory, decision making, and reinforcement learning, I will show that this framework leads to some counterintuitive conclusions, including the finding that constraints on information processing capacity often have adaptive value.

Title: Thermodynamic efficiency and predictive inference

Speaker: Susanne Still (University of Hawaii at Mānoa)

Abstract: Learning from data about the surrounding world is not only essential for animal survival, but also a fundamental cornerstone of science. Observers are learning, model making, entities who use empirical inference. The search for a principled physical foundation of information processing and learning has a long history, spawning many developments that have become independent disciplines, including information theory and machine learning.

There are physical limits to information processing that neither living, nor artificial systems can circumvent. Tangible, physical advantages to certain strategies for representing and encoding data exist, and therefore, so does the possibility to derive machine learning methods from physics. I will discuss how this can be done using thermodynamic limits to information processing. Energy efficiency implies predictive inference, a strategy at the heart of machine learning.

Title: Communication Amid Uncertainty

Speaker: Madhu Sudan (Harvard University)

Abstract: One of the basic goals of the theory of computing is to model behaviour of "intelligent" systems (computers or humans). Behaviour includes ability to acquire information (or knowledge), analyzing it (or reasoning) and communicating it. The theories of Turing (universal computation) and Shannon (reliable communication) offer the foundations for this study covering much of the terrain. And the remarkable progress in the technologies of computing and communication is a testament to the success of these theories. Unfortunately this success has also exposed problems in the intersection of the two fields that neither captures adequately. In our work on "communication amid uncertainty" we explore some such problems, where the ability of two communicating entities to compute allows them to acquire large *mostly* common context. The commonality of the context should enable communication to be even more efficient. On the other hand the "uncertainty" about the context (the fact the context is only mostly common) leads to novel mathematical questions that challenge the fundamental aspects of the classical theories. In this talk we will briefly describe some of the questions and our (partial) answers in this setting of communication with uncertainty.

Title: Analytic Pattern Matching: From DNA to Twitter

Speaker: Wojciech Szpankowski (Purdue University)

Abstract: Repeated patterns and related phenomena in words are known to play a central role in many facets of computer science, telecommunications, coding, intrusion detection, twitter classification, data compression, data mining, and molecular biology. We will first review several pattern matching problems (i.e., exact string matching, constrained pattern matching, generalized pattern matching, subsequence pattern matching, and joint string complexity). We also discuss some applications (i.e., deletion channel, finding biological signals. Lempel-Ziv'78 scheme, suffix trees, and twitter classification).

Title: The Information Bottleneck framework as an Information Lens

Speaker: Naftali Tishby (Hebrew University of Jerusalem)

Abstract: One of the older misconceptions about Shannon’s Information Theory is the notion that information is not about meaning and that Shannon’s Entropy lacks semantics. Shannon himself introduced meaning into information theory in his Rate-Distortion theory, where the meaning comes in through the external distortion function which captures the geometry and similarity of objects and seems completely independent from their information contents. The Information Bottleneck (IB) framework returns this task to measures of information by replacing arbitrary distortion functions with the mutual information of efficient representations on the desired task or relevant label. As such it provides a general unifying principle for extracting efficient representations in biological as well as artificial learning. It thus brings back the notions of meaning and relevance into information theory. In this talk I will describe the IB principle and illustrate its recent application in Machine and Deep Learning in particular, and its role as an information lens in neuroscience and linguistics.

Title: Byzantine Consensus Through the Lens of Information Theory

Speaker: David Tse (Stanford University)

Abstract: The study of the fundamental limits of communication in the presence of errors was initiated by Shannon in 1948. The study of the fundamental limits of distributed consensus in the presence of faults was initiated by Lamport, Pease and Shostak in the early 1980's. Both fields study the problem of designing optimal reliable systems but there has been surprisingly limited cross-fertilization of ideas in the past 40 years. In this talk, we give an example of the utility of such cross-fertilization by using an analogy from network information theory to formulate and solve a central problem in blockchains: the availability-finality dilemma. This is joint work with Joachim Neu and Nusret Tas.

Title: Thermodynamics of information processing in living systems: The energy cost of time keeping in a single cell

Speaker: Yuhai Tu (IBM T. J. Watson Research Center)

Abstract: A central problem in biology is how living systems manage to perform vital functions (e.g., replication, development, computing, etc.) accurately by using inherently stochastic biochemical components and networks to process highly noisy signals (information). What are the molecular mechanisms to control noise for accurate information processing? What is the energy cost for implementing these molecular mechanisms? In this talk, we will present some of our recent work ([1-2]) in addressing these two related general questions in the context of biochemical oscillations such as the circadian clock in Cyanobacteria.

[1] “The free-energy cost of accurate biochemical oscillations”, Y. Cao, H. Wang, Q. Ouyang, and Yuhai Tu, Nature Physics, 11, 772-778, 2015.

[2] “Nonequilibrium thermodynamics of coupled molecular oscillators: The energy cost and optimal design for synchronization”, D. Zhang, Y. Cao, Q. Ouyang, and Yuhai Tu, Nature Physics, 16, 95-100, 2020.

Title: What are the Computational Challenges for Cortex?

Speaker: Leslie Valiant (Harvard University)

Abstract: Over a lifetime the brain performs hundreds of thousands of individual cognitive acts of a variety of kinds, including the formation of new associations and other kinds of learning. Each such act depends on past experience, and, in turn, can have long lasting effects on future behavior. It is difficult to reconcile such large scale capabilities quantitatively with the known resource constraints on cortex, such as low connectivity. Here we shall describe an approach to this problem, in terms of concrete functions, representations, and algorithms, that seeks to explain these phenomena in terms that are faithful to the basic quantitative resources available. Until recently an algorithmic understanding of cognition has been regarded as an overambitious goal for experimental neuroscience. As we shall explain, with current experimental techniques this view is no longer justified, and we should expect algorithmic theories to be experimentally testable, and tested.

Title: The stochastic thermodynamics of computation

Speaker: David Wolpert (Sante Fe Institute)

Abstract: One of the major resource requirements of computers—ranging from biological cells to human brains to high-performance digital computers—is the energy used to run them. Those energy requirements of performing a computation have been a long-standing focus of research in statistical physics, going back (at least) to the early work of Landauer and colleagues.

However, one of the most prominent aspects of computers is that they are inherently non-equilibrium systems. They are also often quite small, far from the thermodynamic limit. Unfortunately, the research by Landauer and co-workers was grounded in the statistical physics of the 20th century, which could not properly address the thermodynamics of non-equilibrium, nanoscale systems.

Fortunately, recent revolutionary breakthroughs in stochastic thermodynamics have overcome the limitations of 20th century statistical physics. We can now analyze arbitrarily off-equilibrium systems, of arbitrary size. Here I show how to apply these recent breakthroughs to analyze the thermodynamics of computation. Specifically, I present formulas for the thermodynamic costs of implementing (loop-free) digital circuits, of implementing Turing machines, and of implementing multipartite processes like the interacting organelles in a cell.

Title: Fun facts about polynomials, and applications to coding theory

Speaker: Mary Wootters (Stanford University)

Abstract: Here are some (fun?) facts about polynomials you probably already know. First, given any three points, you can find a parabola through them. Second, if you look at any vertical “slice” of a paraboloid, you get a parabola. These facts, while simple, turn out to be extremely useful in applications! For example, these facts are behind the efficacy of classical Reed-Solomon and Reed-Muller codes, fundamental tools for communication and storage.

But this talk is not about those facts — it’s about a few related facts that you might not know. Given less than three points’ worth of information, what can you learn about a parabola going through those points? Are there things other than paraboloids that you can “slice” and always get parabolas? In this talk, I will tell you some (fun!) facts that answer these questions, and discuss applications to error correcting codes.


Title: Reasoning about Generalization via Conditional Mutual Information

Speaker: Lydia Zakynthinou (Northeastern University)

Abstract: We provide a framework for studying the generalization properties of machine learning algorithms, which ties together existing approaches, using the unifying language of information theory. We introduce a new notion based on Conditional Mutual Information (CMI) which quantifies how well the input (i.e., the training data) can be recognized given the output (i.e., the trained model) of the learning algorithm. Bounds on CMI can be obtained from several methods, including VC dimension, compression schemes, and differential privacy, and bounded CMI implies various forms of generalization guarantees. In this talk, I will introduce CMI, show how to obtain bounds on CMI from existing methods and generalization bounds from CMI, and discuss the capabilities of our framework. Joint work with Thomas Steinke.


Title: Rebooting Mathematics

Speaker: Doron Zeilberger (Rutgers University)

Abstract: Mathematics is what it is today due to the accidental fact that it was developed before the invention of the computer, and, with a few exceptions, continues in the same vein, by inertia. It is time to start all over, remembering that math, is, or at least should be, the math that can be handled by computers, keeping in mind that they are both discrete and finite.