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.