Colloquium

MIP* denotes the class of problems that admit interactive proofs with quantum entangled provers. It has been an outstanding question to characterize the complexity of this class. Most notably, there was no known computable upper bound on MIP*.

We show that MIP* is equal to the class RE, the set of recursively enumerable languages. In particular, this shows that MIP* contains uncomputable problems. Through a series of known connections, this also yields a negative answer to Connes’ Embedding Problem from the theory of operator algebras. In this talk, I will explain the connection between Connes' Embedding Problem, quantum information theory, and complexity theory. I will then give an overview of our approach, which involves reducing the Halting Problem to the problem of approximating the entangled value of nonlocal games.

Joint work with Zhengfeng Ji, Anand Natarajan, Thomas Vidick, and John Wright.

Cooling atomic gases to ultracold temperatures revolutionized the field of atomic physics, connecting with and impacting many other areas in physics. Advances in producing ultracold molecules suggest similarly dramatic discoveries are on the horizon. First, I will review the physics of ultracold molecules, including our work bringing a new class of molecules to nanokelvin temperatures. Chemistry at these temperatures has a very different character than at room temperature. One striking effect is our recent result using spin states of reactants to control chemical reaction pathways. I will also describe how the strong electric dipole moments of ultracold molecules present an exciting new tool for quantum information and quantum computing.

While it is considered to be one of the most promising hints of new physics beyond the Standard Model, dark matter is as-yet known only through its gravitational influence on astronomical and cosmological observables. I will discuss our current best evidence for dark matter's existence as well as the constraints that astrophysical probes can place on its properties, while highlighting some tantalizing anomalies that could indicate non-gravitational dark matter interactions. Future observations, along with synergies between astrophysical and experimental searches, have the potential to illuminate dark matter's fundamental nature and its influence on the evolution of matter in the cosmos from the first stars and galaxies to today.

There has been tremendous progress in the many layers needed to realize large-scale quantum computing, from the hardware layers to the high level software. There has also been vastly increased exploration into the potentially useful applications of quantum computers, which will drive the desire to build quantum computers and make them available to users. I will describe some of my research in quantum algorithmics and quantum compiling.

The knowledge and tools developed for these positive applications give us insight into the cost of implementing quantum cryptanalysis of today's cryptographic algorithms, which is a key factor in estimating when quantum computers will be cryptographically relevant (the "collapse time"). In addition to my own estimates, I will summarize the estimates of 22 other thought leaders in quantum computing.

What quantum cryptanalysis means to an organization or a sector depends not only on the collapse time, but also on the time to migrate to quantum-safe algorithms as well as the shelf-life of information assets being protected. In recent years, we have gained increasing insight into the challenges of a wide-scale migration of existing systems. We must also be proactive as we deploy new systems. Open-source platforms, like OpenQuantumSafe and OpenQKDNetwork, are valuable resources in helping meet many of these challenges.

While awareness of the challenges and the path forward has increased immensely, there is still a long road ahead as we work together with additional stakeholders not only to prepare our digital economy to be resilient to quantum attacks, but also to make us more resilient to other threats that emerge.

As of late March 2020, Covid-19 has already secured its status among the most expansive pandemics of the last century. Covid-19 is caused by a coronavirus--SARS-CoV-2--that causes a severe respiratory disease in a fraction of those infected, and is typified by several important features: ability to infect cells of various kinds, contagiousness prior to the onset of symptoms, and a widely varying experience with disease across patient demographics.

In this seminar, I discuss the many lessons that the scientific community has learned from Covid-19, including insight from molecular evolution, cell biology, and epidemiology. I discuss the role of mathematical and computational modeling efforts in understanding the trajectory of the epidemic, and highlight modern findings and potential research questions at the interface of virology and materials science. I will also introduce areas of inquiry that might be of interest to the physics community.

Historically, new particles and forces in the Standard Model have most often revealed themselves at high-energy particle colliders. Certain phenomena beyond the Standard Model, however, are best studied by using carefully designed low-energy precision measurements, or via their imprints on astrophysical and cosmological observables. In this talk, I will provide a concise overview of some of the new experiments and searches devised to look for new physics beyond the Standard Model. In particular, I will discuss recent developments in the new experimental and theoretical program of cosmological collider physics and how we can use the cosmological collider as a tool to study the structure of the Higgs potential at very high energies.

As our understanding of the universe and its fundamental building blocks extends to shorter and shorter distances, experiments capable of probing these scales are becoming increasingly difficult to construct. Fundamental particle physics faces a potential crisis: an absence of data at the shortest possible scales. Yet remarkably, even in the absence of experimental data, the requirement of theoretical consistency puts stringent constraints on viable models of fundamental particles and their interactions. In this talk I’ll discuss a variety of criteria that constrain theories of particles in flat spacetime and de Sitter. Such criteria have the possibility to address questions such as: What low energy theories admit consistent UV completions? Which massive particles are allowed in an interacting theory? Is string theory the unique weakly coupled UV completion of General Relativity?

In our four-dimensional world supersymmetry is the only extension of the classical Poincaré invariance which laid the foundation of modern physics in the beginning of the 20th century. Supersymmetry, a new geometric symmetry extending Poincaré, was discovered in 1970 –– it was overlooked for decades because of its quantum nature. In the next 10 years or so supersymmetry 

assumed the role of a universal framework in which new models for natural phenomena and regularities (e.g. the concept of naturalness) have been developed. It gave rise to a powerful stream of theoretical phenomenology.

The fact that LHC at CERN produced no evidence for low-energy supersymmetry (and naturalness as well) was a powerful blow. However, despite its absence in experiments the less known second mission of supersymmetry is highly successful, with remarkable advances occurring on a regular basis. Supersymmetry proved its power and uniqueness for those who address hard questions in strongly coupled field theories, including Yang-Mills. Some supersymmetry-based exact results obtained in four dimensions are the main topics of my talk. In the past one could hardly dream that such results are possible.

Theories beyond the Standard Model of particle physics often predict new, light, feebly interacting particles whose discovery requires novel search strategies. A light particle, the QCD axion, elegantly solves the outstanding strong-CP problem of the Standard Model; cousins of the QCD axion can also appear, and are natural dark matter candidates.  First, I will discuss my experimental proposal based on thin films, in which dark matter can efficiently convert to detectable single photons. A prototype experiment is underway, and current techniques promise to reach significant new dark matter parameter space.

Second, I will show how rotating black holes turn into axionic and gravitational wave beacons, creating nature's laboratories for ultralight bosons. When an axion's Compton wavelength is comparable to a black hole size, energy and angular momentum from the black hole source exponentially-growing bound states of particles, forming `gravitational atoms'.  These `gravitational atoms' emit monochromatic gravitational wave signals, enabling current searches at gravitational wave observatories to discover ultralight axions. If the axions interact with one another, instead of gravitational waves, black holes populate the universe with axion waves.

Stacking two graphene layers twisted by the ‘magic angle’ 1.1º generates flat energy bands, which in turn catalyzes various strongly correlated phenomena depending on filling and sample details. While this system is most famous for the superconducting and insulating states observed at fractional fillings, I argue that charge neutrality presents an interesting interplay of disorder and interactions.

In scanning tunnelling microscopy (STM), the most striking signature of interactions occurs close to charge neutrality, where the splitting between the flat bands increases dramatically. In analogy with quantum Hall ferromagnetism, I show that this effect may be qualitatively understood as the result of an exchange energy gain. A low-energy manifold of gapped, symmetry-breaking states is identified, one of which possesses quantum valley Hall order. Transport measurements yield ostensibly conflicting information at charge neutrality: while some samples reveal semimetallicity (as expected when correlations are weak), yet others exhibit robust insulation. I reconcile these observations and those of STM by arguing that strong interactions supplemented by weak, smooth disorder stabilize a network of locally gapped quantum valley Hall domains with spatially varying Chern numbers determined by the disorder landscape—--even when an entirely different order is favored in the clean limit. I conclude with a discussion of experimental tests of this proposal via local probes and transport.

The average entanglement entropy of subsystems of random pure states is (nearly) maximal. In this talk, we discuss the average entanglement entropy of subsystems of highly excited eigenstates of integrable and nonintegrable many-body lattice Hamiltonians. For translationally invariant quadratic models (or spin models mappable to them) we prove that, when the subsystem size is not a vanishing fraction of the entire system, the average eigenstate entanglement entropy exhibits a leading volume-law term that is different from that of random pure states. We argue that such a leading term is likely universal for translationally invariant (noninteracting and interacting) integrable models. For random pure states with a fixed particle number (random canonical states) away from half filling and normally distributed real coefficients, we prove that the deviation from the maximal value grows with the square root of the system's volume when the size of the subsystem is one half of that of the system. We then show that the average entanglement entropy of highly excited eigenstates of a particle number conserving quantum chaotic model is the same as that of random canonical states.

A scientific understanding of modern deep learning is still in its early stages. As a first step towards understanding the learning dynamics of neural networks, one can simplify the problem by studying limits that might have theoretical tractability and practical relevance. I’ll begin with a brief survey of our earlier body of work that has investigated the infinite width limit of deep networks, a topic of active study recently. With these results in hand, it nonetheless appears there is still a gap towards theoretically describing neural networks at finite width. I’ll argue that the choice of learning rate is one crucial factor in dynamics away from the infinite width limit and naturally classifies deep networks into two classes separated by a sharp transition. This is elucidated in a class of solvable simple models we present, which give quantitative predictions for the two classes. Quite remarkably, we test these predictions empirically in practical settings and find excellent agreement. 

Yasaman Bahri is a research scientist on the Google Brain team. Her current research program is to build a scientific understanding of deep learning using a combination of theoretical analysis and empirical investigation. Prior to Google, she was at the University of California, Berkeley, where she received her Ph.D. in physics in 2017, specializing in theoretical quantum condensed matter.