Computer Science Lecture Series

Pseudo-Randomness, Complex Zeros of Polynomials, and Hardness of Sampling from Small Quantum Devices

Saeed Mehraban, Postdoctoral Scholar, California Institute of Technology

Apr 1, 2021

Please register here to join us for the CS Colloquium Series 2020-21 via Zoom. Once you register, you will receive a recurring Zoom link. You only need to register once to be able to attend any of the seminars. 


A crucial milestone before achieving full-scale quantum computing is to utilize the more restricted quantum hardware accessible in the near future. As a part of this step, it is desirable to design intermediate-scale quantum com putations with robust theoretical guarantees for surpassing classical computers. To accomplish this, research over the past decade has established the hardness of sampling from elementary quantum experiments on plausible assumptions. 

In this talk, I will illustrate several connections between these assumptions and two other paradigms in physics and mathematics. First, I will focus on quantum pseudo-randomness and explain my joint contribution (with Aram Harrow QIP 2019) to this area. We settle a conjecture of Brand˜ao-Harrow Horodecki, which states that random low-depth quantum circuits on several fundamental architectures are pseudo-random. These pseudo-random construc tions, known as t-designs, have significant applications in quantum information theory and also appear in the study of chaotic quantum systems. Notably, one of the baseline assumptions pertinent to the hardness of the random circuit sampling experiment, implemented recently by the Google AI Quantum team, follows from our result. Next, I will proceed to a different paradigm, known as the geometry of analytic functions, and outline its interfaces with statistical physics and computer science. I will specifically describe the implications of this evolving field to the average-case complexity of the permanent polynomial. One of the basic assumptions of BosongSampling (recently conducted on scales remarkably larger than previous realizations) is that the permanent of Gaussian matrices with zero mean is hard to approximate. Despite this widely-accepted conjecture, in joint work with Lior Eldar (FOCS 2018), we use recent approaches in the geometry of the zeros of polynomials to design a quasi-polynomial time approximation algorithm for the permanent of complex Gaussian matrices with unit variance and asymptotically vanishing mean.

Speaker Bio

Saeed Mehraban is an IQIM postdoctoral scholar at California Institute of Tech nology. During Spring 2020, he was a research fellow for the Quantum Wave in Computing Program at the Simons Institute for the Theory of Computing. His research interests include quantum computation and information, and their connections with computer science and physics. He obtained his Ph.D. degree in Electrical Engineering and Computer Science from MIT, where he was advised by Scott Aaronson and Aram Harrow. Before MIT, he completed B.Sc. degrees in Electrical Engineering and Physics from Sharif University of Technology, Iran.



CS Colloquium


Jessica Brenn