25 October 2022, 2pm London time - Video of talk

Bill Fefferman (University of Chicago)

Title: Quantum pseudoentanglement

Abstract: Quantum pseudorandom states are efficiently preparable states that are indistinguishable from truly Haar random states to an efficient observer. First defined by Ji, Liu and Song, such states have found a wide variety of applications in areas such as cryptography and quantum gravity. A fundamental question is exactly how much entanglement is required to create such states. Haar-random states, as well as t-designs, exhibit near-maximal entanglement. Here we provide the first construction of pseudorandom states with only polylogarithmic entanglement entropy across an equipartition of the qubits, which is the minimum possible. Our construction can be based on any one-way function secure against quantum attack. We additionally show that the entanglement in our construction is fully "tunable". More fundamentally, our work calls into question to what extent entanglement is a "feelable" quantity of quantum systems. Inspired by recent work of Gheorghiu and Hoban, we define a new notion which we call "pseudoentanglement", which are ensembles of efficiently constructable quantum states which hide their entanglement entropy. We show such states exist in the strongest form possible while simultaneously being pseudorandom states.
Based on joint work with Adam Bouland, Soumik Ghosh, Umesh Vazirani and Zixin Zhou.

19 August 2022, 2pm London time - Video of talk

Ryan O'Donnell (CMU)

Title: Mean Estimation When You Have The Source Code; or, Quantum Monte Carlo Methods

Abstract: Suppose y is a real random variable, and one is given access to "the code" that generates it (for example, a randomized or quantum circuit whose output is y). We give a quantum procedure that runs the code O(n) times and returns an estimate for E[y] with optimal dependence on n for quantum algorithms. The central subroutine for our result is essentially Grover's algorithm but with complex phases.
Joint work with Robin Kothari (Microsoft).

1 July 2022, 2pm London time - Video of talk

Ronald de Wolf (QuSoft, CWI)

Title: Quantum machine learning from a theoretical perspective

Abstract: Machine learning can be enhanced by quantum computing, both by allowing quantum data and by having quantum speedups for the optimization process that finds a good model for given data. This talk will examine both aspects, from the perspective of theoretical computer science.