Quantum computers offer power to solve some problems that goes far beyond what is possible classically. But classical computers have advantages that are likely to persist: they do not suffer from decoherence, and they can access large data sets.  I will describe algorithms for optimization and inference that combine the strengths of both platforms.

I'll survey the challenges of demonstrating quantum supremacy via BosonSampling, particularly in light of the striking announcement in late 2020 by a group in Hefei, China to have built a BosonSampling device with 50-70 detected photons. I'll discuss the advantages and disadvantages of BosonSampling compared to Random Circuit Sampling (what the Google group demonstrated in 2019) and other NISQ quantum supremacy proposals; and I'll highlight the theoretical open problems that have emerged as the most pressing.

Within the last several years there has been tremendous growth in quantum algorithms for Hamiltonian simulation which have led not only to advances for simulating the underlying dynamics in chemistry and condensed matter systems but has also led to new algorithms for solving linear systems, semidefinite programming and a host of other applications. In this talk, I will provide a high-level overview of the key strategies employed in modern Hamiltonian simulation algorithms. I will aim to not only show how modern quantum simulation algorithms work but also show how such algorithms can be applied to take advantage of different features of a problem such as commutativity or diagonal dominance of the Hamiltonian. I will then show how in practice these methods can be chosen to optimize simulations of chemistry and simulations of quantum electrodynamics in quantum systems. Finally, I will conclude by presenting open problems and new opportunities that these new paradigms create for developing new algorithms for simulation and beyond.

After the second quantum revolution, which completely undermined how we think of the notion of an algorithm, the last decade gave birth to a third quantum revolution - which has shaken the notion of a "physical experiment". Over this past decade, quantum computational notions have penetrated into the study of fundamental questions which were so far the business of experimental physicists only; and this new language offers a fresh look at those questions. In a variety of experimental settings, from sensing to precision measurements of energy, examples were discovered which demonstrate that incorporating ideas from quantum computation, such as quantum multipartite entanglement and quantum error correction, can buy us a huge amount of leverage in terms of precision and efficiently. This raises important questions:

How general is this development, and how influential? Can ideas from quantum computation significantly improve the efficiency and precision of different physical experiments? which ones, and to what extent?
What kinds of new experimental possibilities are opened, using these new ideas?
Taking it to an extreme (and to the far future), how much would it help the experimentalist to have a quantum computer in her lab? And what would be the most useful ways to use this computer?

I will describe some illuminating current and future examples (such as super resolution using entanglement, using error correction for better sensing, and achieving exponential violations of the time energy uncertainty principle based on Shor's algorithm); I will then discuss very recent work in which a universal computational model for quantum experiments is defined, in which the above questions can be studied rigorously; I will also show, for example, that determining the time-reversal symmetry in a many-body physical systems can be done exponentially more efficiently if (very limited) quantum computers are available in the lab. Many open questions are raised by this revolution. They connect experimental physics with theoretical computer science questions in quantum algorithms and quantum complexity. The talk will be based on joint works with Yosi Atia, Jordan Cotler, Xiaoliang Qi, and others.

The threshold theorem for fault tolerance tells us that it is possible to build arbitrarily large reliable quantum computers provided the error rate per physical gate or time step is below some threshold value. The leading candidate for realizing fault tolerance is the surface code, which admits a 2-dimensional layout, has a high error threshold, and has large but not ridiculous overhead (in terms of extra qubits needed). I will discuss another approach which has garnered interest in recent years since it has the potential to greatly decrease the overhead: namely, using high-rate low-density parity check codes, known as LDPC codes. We do not yet have practical protocols using LDPC codes, so I will explain the progress so far in finding interesting codes, decoding algorithms for them, and fault-tolerant operations on them.

Fault tolerance is necessary for reliable quantum computing. While there have been experimental tests of quantum error-correcting codes, testing fault-tolerance remains a major challenge, mainly due to the substantial overhead. I will describe a qubit-efficient paradigm for fault-tolerance circuit design, termed the "flag method." Traditional approaches achieve fault-tolerance by preventing errors from spreading badly. In the flag method, "flag qubits" are added to catch the faults that can lead to correlated errors on the data. Provided the flag gadgets are carefully designed, the potential correlated errors can be diagnosed by their syndromes, and accordingly be remedied. I will illustrate the flag idea with several applications and extensions, which are of general theoretical interest as well as practical importance.

With rapid progress in quantum technology, focus is shifting from demonstrations on a small number of noisy qubits towards interesting application problems, of academic or commercial interest, where a quantum computer can outperform even the best classical supercomputer. Comparing current classical computers with optimistic assumptions for future quantum computers I will present criteria for achieving such practical quantum advantage and will argue that “small data” problems with superquadratic quantum speedups are the most promising candidates. The simulation of quantum systems, with applications to condensed matter physics, materials science of chemistry is one such application area. I will present recent progress on quantum algorithms for chemistry and discuss that realizing such a quantum advantage will require more than just a quantum algorithm and quantum computer.

We will discuss quantum singular value transformation (QSVT), a simple unifying framework for quantum linear algebra algorithms developed by Gilyén et al. QSVT is often applied to try to achieve quantum speedups for machine learning problems. We will see the typical structure of such an application, the barriers to achieving super-polynomial quantum speedup, and the state of the literature that's attempting to bypass these barriers. Along the way, we'll also see an interesting connection between quantum linear algebra and classical sampling and sketching algorithms (explored in the form of "quantum-inspired" classical algorithms).

There is an inherent contradiction between the exponential complexity of quantum states and the possibility of studying quantum many-body physics. One of the important principles that makes quantum many body physics tractable is that there are large classes of physically occurring systems for which ground and low energy states are conjectured to have succinct classical descriptions. This is of course quite relevant to the issue of simulation of quantum systems. Formally this principle is encapsulated in the area-law of the entanglement entropy: the entanglement of a contiguous region with respect to the rest of the system scales like its boundary area, rather than its volume. It is conjectured that ground states of gapped spin systems -- those that have a gap between the ground energy and the first excited level -- satisfy an area-law, and might therefore be easier to simulate. So far, the conjecture has only been fully proven for one dimensional systems (Hastings' 2007). However, a sequence of improvements of Hastings' result in 1D has recently led to a breakthrough towards a possible proof of the 2D case. In this talk I will introduce this conjecture and give an overview of the research that led to the recent breakthroughs, which includes ideas that span Computer Science, Math and Physics.

Quantum many-body systems are very hard to simulate, as computational resources (time and memory) typically grow exponentially with system size. However, quantum computers or analog quantum simulators may perform that task in a much more efficient way. In this talk, I will review some of the quantum algorithms that have been proposed for this task and then explain the advantages and disadvantages of analog quantum simulators. In particular, I will describe methods to simulate the dynamics, to find ground states, or compute physical properties at finite temperatures.

Shor’s algorithms for factoring integers and finding discrete logarithms famously break much of the cryptography used today. This has led to the field of post-quantum cryptography, whose goal is to develop cryptosystems secure against quantum attacks. In this talk, I will survey some of the challenges of post-quantum cryptography. In particular, I will explain how the emergence of quantum computers requires updating the entire modern practice of cryptography, including the underlying mathematical building blocks, the formal definitions of security, and the proofs of security.

I will review an experimentally feasible procedure for converting a quantum state into a succinct classical description of the state, its classical shadow. Classical shadows can be applied to predict efficiently many properties of interest, including expectation values of local observables and few-body correlation functions. Efficient classical machine learning algorithms using classical shadows can address quantum many-body problems such as classifying quantum phases of matter.

MIP* = RE has the startling consequence that, in the entangled provers model, there is an interactive proof for the Halting problem. In other words, for all Turing machines M that halt, two separated but quantum entangled provers can convince a classical verifier that M eventually terminates --- and furthermore the complexity of the verifier does not depend on the running time of M!

What does it mean to have an interactive proof for an undecidable problem, and how does quantum entanglement enable this mind-boggling leap in complexity for multiprover interactive proofs? In this talk, I will try to shed light on these questions by highlighting the central role of proofs in MIP* = RE: at its core, the MIP* protocol for the Halting problem recursively combines proofs of both classical and quantum properties. Time permitting, I will also discuss how the techniques in MIP* = RE point to a broader set of questions about "noncommutative property testing."

Based on joint work with Zhengfeng Ji, Anand Natarajan, Thomas Vidick, and John Wright.

Faster algorithms for optimization problems are among the main potential applications for future quantum computers. There has been interesting progress in this area in the last few years, for instance improved quantum algorithms for gradient descent and for solving linear and semidefinite programs. In this talk I will survey what we know about quantum speed-ups both for discrete and for continuous optimization. I'll also discuss some issues with these algorithms, in particular that quadratic quantum speedups will only kick in for very large instance sizes and that many of these algorithms require some kind of QRAM.