Talks

In this work we study the quantum learnability of constant-depth classical circuits under the uniform distribution and in the distribution-independent framework of PAC learning. In order to attain our results, we establish connections between quantum learning and quantum-secure cryptosystems. We then achieve the following results. 1) Hardness of learning AC0 and TC0 under the uniform distribution. Our first result concerns the concept class TC0 (resp. AC0), the class of constant-depth and polynomial-sized circuits with unbounded fan-in majority gates (resp. AND, OR, NOT gates). We show that if there exists no quantum polynomial-time (resp. strong sub-exponential time) algorithm to solve the Ring Learning with Errors (RLWE) problem, then there exists no polynomial-time quantum learning algorithm for TC0 (resp. AC0) under the uniform distribution (even with access to quantum membership queries). The main technique in this result uses explicit pseudo-random functions that are believed to be quantum-secure to construct concept classes that are hard to learn quantumly under the uniform distribution. 2) Hardness of learning TC02 in the PAC setting. Our second result shows that if there exists no quantum polynomial time algorithm for the LWE problem, then there exists no polynomial time quantum PAC learning algorithm for the class TC02, i.e., depth-2 TC0 circuits. The main technique in this result is to establish a connection between the quantum security of public-key cryptosystems and the learnability of a concept class that consists of decryption functions of the cryptosystem. This gives a strong (conditional) negative answer to one of the "Ten Semi-Grand Challenges for Quantum Computing Theory" raised by Aaronson [Aar05], who asked if AC0 and TC0 can be PAC-learned in quantum polynomial time.

Recently, Bravyi, Gosset, and König (Science, 2018) exhibited a search problem called the 2D Hidden Linear Function (2D HLF) problem that can be solved exactly by a constant-depth quantum circuit using bounded fan-in gates (or QNC^0 circuits), but cannot be solved by any constant-depth classical circuit using bounded fan-in AND, OR, and NOT gates (or NC^0 circuits). In other words, they exhibited a search problem in QNC^0 that is not in NC^0. We strengthen their result by proving that the 2D HLF problem is not contained in AC^0, the class of classical, polynomial-size, constant-depth circuits over the gate set of unbounded fan-in AND and OR gates, and NOT gates. We also supplement this worst-case lower bound with an average-case result: There exists a simple distribution under which any AC^0 circuit (even of nearly exponential size) has exponentially small correlation with the 2D HLF problem. Our results are shown by constructing a new problem in QNC^0, which we call the Relaxed Parity Halving Problem, which is easier to work with. We prove our AC^0 lower bounds for this problem, and then show that it reduces to the 2D HLF problem.  https://arxiv.org/abs/1906.08890

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.

In the past few years there have been a number of major advances for quantum simulation.  I will be reviewing a number of them in this talk including the interaction picture simulation method, the QDRIFT algorithm, well conditioned multi-product formulas and new commutator bounds for high-order Trotter Suzuki methods which show that those algorithms are much more efficient than previously thought.  Finally I will discuss applications of these algorithms to problems in chemistry and simulation of the Schwinger model in 1+1D.

This talk aims at providing an overview of some of the major ideas and techniques that were developed for Hamiltonian simulation, including Trotterization, linear combination of unitaries, oblivious amplitude amplification and quantum signal processing. The adaptation and clever combination of these techniques led to a flurry of new results in different variants of Hamiltonian simulation problems, as well as in other important quantum algorithmic tasks.

Noisy quantum computers can outperform classical computers on certain sampling tasks, but it's unclear whether NISQ machines can outperform classical computers on a commercially relevant task. If NISQ machines can't do this, then it will be necessary to build fault tolerant quantum computers before a "quantum information age" could truly begin. The goal of this talk is to contextualize the expected overhead of fault tolerant quantum computation using superconducting qubits and the surface code. We will cover the cost of performing the simplest possible classically intractable task (random circuit sampling) in a fault tolerant fashion.

The subject of this talk will be quantum distributed computing, i.e., distributed computing when the processors of the network can exchange quantum information. After describing the basics of distributed computing, I will explain a result obtained with Frédéric Magniez (arXiv:1804.02917) on quantum algorithms computing the diameter of the network. I will then present others results (arXiv:1810.10838 and arXiv:1908.11488) that show separations between the computational powers of quantum and classical distributed algorithms in several fundamental models of distributed computing. I will conclude my talk by mentioning interesting and important open questions in quantum distributed computing.