Gather.town opens at 10:30 a.m. Pacific Time, and after the colloquium.
This colloquium series is sponsored by the NSF Challenge Institute for Quantum Computation.
In response to the COVID-19 pandemic, all Simons Institute events are currently taking place online.
Tuesday, Jan 26, 2021, 11:00 am – 12:00 pm
Hybrid Classical-Quantum Algorithms, Aram Harrow (MIT)
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.
Tuesday, Feb 9, 2021, 11:00 am – 12:00 pm
Quantum Supremacy via Boson Sampling: Theory and Practice, Scott Aaronson (University of Texas at Austin)
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.
Tuesday, Feb 16, 2021, 11:00 am – 12:00 pm
Quantum Algorithms for Hamiltonian Simulation, Nathan Wiebe (University of Washington)
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.
Tuesday, Feb 23, 2021, 11:00 am – 12:00 pm
Quantum Algorithmic Measurements, Dorit Aharonov (Hebrew University)
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.
Tuesday, Mar 2, 2021, 11:00 am – 12:00 pm
Fault Tolerance with LDPC Codes, Daniel Gottesman (Perimeter Institute)
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.
Tuesday, Mar 30, 2021, 11:00 am – 12:00 pm
On Quantum Linear Algebra for Machine Learning, Ewin Tang (University of Washington)
Tuesday, April 13, 2021, 11:00 am – 12:00 pm
Quantum Simulation, Ignacio Cirac (Max Planck Institute, Munich)
Tuesday, April 20, 2021, 11:00 am – 12:00 pm
Postquantum Cryptography, Mark Zhandry (Princeton University)
Tuesday, April 27, 2021, 11:00 am – 12:00 pm
Classical Shadows of Quantum States, John Preskill (California Institute of Technology)
This colloquium series will feature talks by some of the foremost experts in quantum computation in the form of "an invitation to research in area X". With the explosion of interest in quantum computation, there is a dizzying flurry of results, as well as a diverse group of researchers who are drawn to this field. This colloquium series aims to target three audiences:
- Experts in quantum computation: It is increasingly difficult for even experts to keep up with the results in adjacent areas. These colloquia will aim to identify the key results and techniques in the area, as well as the most important directions for further research.
- Interested researchers in (classical) theoretical computer science: There are deep connections between ideas in quantum computation and classical complexity, algorithms, etc. These colloquia will make these connections more accessible to the broader TCS community.
- Interested mathematical and physical science (MPS) researchers: These colloquia will enable MPS researchers to cut through the clutter to make connections to CS style results in quantum computation.
Public Zoom webinar link: https://berkeley.zoom.us/j/95040632440
If you wish to receive ongoing info about talks in this series, or if you would like to be able to pose questions during the live sessions, please register to participate.
If you require accommodation for communication, please contact our Access Coordinator at simonsevents [at] berkeley.edu with as much advance notice as possible.