Our videos can also be found on YouTube.

Oct. 2021
Nathan Wiebe (University of Toronto)
Quantum Colloquium, Oct. 19th, 2021

Recently there has been substantial interest in the development of quantum machine learning protocols. However, despite this there have been a number of stumbling blocks that have emerged for quantum machine learning. Specifically, recent work showing dequantizations of quantum algorithms as well as barren plateau results have shown that new ideas are needed to build and train quantum models that have advantage over classical models. In this talk I will discuss the challenges that arise when trying to use quantum mechanical effects to train neural networks and show that entanglement, long viewed as a boon for quantum computers, is actually generically anathema for deep quantum neural networks and by drawing on lessons from the thermalization community that unchecked entanglement causes these models to be exponentially close to the maximally mixed state and that gradient descent is not capable of remedying the situation. I will then look at a partial solution to these problems, which involves switching to generative learning and show that quantum neural networks can be efficiently trained using quantum analogues of the KL-divergence, which do not suffer from barren plateau problems due to its logarithmic divergence for orthogonal states (which combats gradient decay). I will show numerical evidence that indicates that small scale quantum neural networks can be trained to generate complex quantum states and in turn suggest that generatively pre-training models may be a way to circumvent known barren plateau results for quantum machine learning.
Playlist: 37 videos
Playlist: 20 videos
Jul. 2021
Theory Shorts is a documentary web series that explores topics from the Simons Institute’s research programs.

The second short film in the series, “Until the Sun Engulfs the Earth: Lower Bounds in Computational Complexity,” explores how we know that a problem is impossible to solve.

Fruit game optimal algorithm: Hossein Jowhari, Mert Saglam, Gábor Tardos. "Tight bounds for Lp
samplers, finding duplicates in streams, and related problems." PODS 2011: 49-58.

Fruit game optimal lower bound: Michael Kapralov, Jelani Nelson, Jakub Pachocki, Zhengyu Wang, David P. Woodruff, Mobin Yahyazadeh. "Optimal Lower Bounds for Universal Relation, and for Samplers and Finding Duplicates in Streams." FOCS 2017: 475-486.

Paul Beame
Faith Ellen
Jelani Nelson
Manuel Sabin
Madhu Sudan

Anil Ananthaswamy
Kristin Kane

Shafi Goldwasser

Anil Ananthaswamy

Kristin Kane

Barry Bödeker

Caresse Haaser
Kristin Kane

Drew Mason

Kevin Hung
Bexia Shi

Preeti Aroon

Adriel Olmos

Ryan Adams
Wesley Adams
Marco Carmosino
Kani Ilangovan
Sampath Kannan
Richard Karp
David Kim
Bryan Nelson
Jeremy Perlman
Kat Quigley
Siobhan Roberts
Amelia Saul
Umesh Vazirani

Dill Pickles (Heftone Banjo Orchestra)
Flamenco Rhythm (Sunsearcher)
Place Pigalle (Uncle Skeleton)
Plastic (Purple Moons)

Courtesy of byxorna, inspectorj, janbezouska, jorickhoofd, kash15, kyster, robinhood76, smotasmr, svarvarn, and vandrandepinnen via

Becoming (Jan van IJken)
A Decade of Sun (Solar Dynamics Observatory, NASA)
Move Mountain (Kirsten Lepore)

© Simons Institute for the Theory of Computing, 2021
Mar. 2021
Ramin Hasani (MIT)
Synthesis of Models and Systems
Playlist: 22 videos
Playlist: 25 videos
Playlist: 21 videos
May. 2020
The Women of Theory of Computer Science rock to our version of I Will Survive!

I Will Survive
Lyrics: Avi Wigderson (IAS)

At first I was afraid, I was petrified
I worried I could never fit this proof on just one slide
But then I spent so many nights thinking why it is so long
And I grew strong
And learned exactly what went wrong

A problem wor-thy, of attack
Just proves its worth by vigorously fighting back
I should have used error correction, should have sampled yet again
I should have stayed the course and found there is so much that I can gain

So do come back, problems galore
I am much more ready to attack you than I was before
I’ll fight you guiltless when at work, forget you guiltless when at home
And if you’re fun then in the pastures of the TCS we’ll roam

So I’ll survive, and I will thrive,
By Nash’s equilibrium, there must be balance to my life
I’ve got all my life to live,
And I’ve got all my Math to give
So I’ll survive,
and I will thrive, hey, hey

It took all the strength I had, I was nearly spent,
Trying hard to mend, the errors, in my argument
I put each pigeon in its hole, consulted every oracle
My upper bound
Turned up below my lower bound

Then I came up, with something new
I thought outside the blackbox, found what others never knew
That polynomials with a small degree have small number of roots
That few cryptogra-phic assumptions no one’s likely to dispute

So do come back, problems galore
I am much more ready to attack you than I was before
As I have wit and I have WIT and having both is pretty neat
Indeed a convex combination that is very hard to beat

So I’ll survive, and I will thrive,
Because (in theory, at least) this is a perfect life
You pick the problems that you love
To fit your brain just like a glove
So I’ll survive,
and I will thrive, hey, hey

Dahlia Malkhi (Calibra, Facebook)
Elette Boyle (IDC, Israel)
Irit Dveer Dinur (Weizmann Institute, Israel)
Julia Chuzhoy (Toyota Technological Institute at Chicago, USA)
Katrina Ligett (Hebrew University, Israel)
Keren Censor-Hillel (Technion, Israel)
Lisa Zhang (Bell-Labs, USA)
Mary Wooters (Stanford University, USA)
Michal Feldman (Tel-Aviv University, Israel)
Nicole Immorlica (Microsoft Research, New England, USA)
Orna Kupferman (Hebrew University, Israel)
Rebecca Wright (Barnard College, USA)
Ronitt Rubinfeld (MIT, USA)
Shafi Goldwasser (Simons Institute at UC Berkeley, USA)
Shubhangi Saraf (Rutgers University, USA)
Shuchi Chawla (University of Wisconsin, Madison, USA)
Sofya Raskhodnikova (Boston University, USA)
Tal Malkin (Columbia University, USA)
Tal Rabin (Algorand Foundation, USA)
Yael Tauman Kalai (Microsoft Research, New England, USA)
Apr. 2020
Theory Shorts is a documentary web series that explores topics from the Simons Institute’s research programs.

Episode 1, “Perception as Inference: The Brain and Computation,” explores the computational processes by which the brain builds visual models of the external world, based on noisy or incomplete data from patterns of light sensed on the retinae.

Bruno Olshausen

Christoph Drösser

Michaelle McGaraghan

Kristin Kane
Michaelle McGaraghan

Shafi Goldwasser

Caresse Haaser
Christoph Drösser
Lukas Engelhardt

Barry Bödeker

Drew Mason
Omied Far
Michaelle McGaraghan
Matt Beardsley

Christine Wang
Bexia Shi
Lior Shavit

“Plastic” by Purple Moons
Courtesy of Marmoset in Portland, Oregon

Bruce Damonte
Arash Fazl
Anders Garm
Jean Lorenceau and Maggie Shiffrar
Beau Lotto
A. L. Yarbus
Bruno Olshausen
videocobra / Pond5
BlackBoxGuild / Pond5
nechaevkon / Pond5
DaveWeeks / Pond5
CinematicStockVideo / Pond5
BananaRepublic / Pond5
MicroStockTube / Pond5
shelllink / Pond5
AudioQuattro / Envato Market
HitsLab / Envato Market
FlossieWood / Envato Market
plaincask / Envato Market
MusicDog / Envato Market
Loopmaster / Envato Market
Ryokosan / Envato Market
Images used under license from

© Simons Institute for the Theory of Computing, 2019
Dec. 2019
Andrew W. Lo (Massachusetts Institute of Technology)
Theoretically Speaking Series, Fall 2019
Jul. 2019
Aleksander Madry (MIT)
Frontiers of Deep Learning
Playlist: 24 videos
Jun. 2018
Urmila Mahadev, UC Berkeley
Challenges in Quantum Computation