Pseudorandomness, average-case complexity and hardness of sampling from small quantum devices

Abstract

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 computations 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 discuss two contributions to the study of these assumptions. In the first part, I will discuss joint work with Aram Harrow (QIP 2019) on quantum pseudo-randomness. In this work, we settle a conjecture of Brand˜ao-Harrow-Horodecki, which states that low-depth random quantum circuits on several important architectures are pseudo-random. These pseudorandom constructions, 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 focus on my recent work on the average-case complexity of the permanent polynomial relevant to the BosongSampling experiment (recently conducted on scales remarkably larger than previous realizations). I will describe the Permanent-of-Gaussians conjecture due to Aaronson and Arkhipov, which states that it is hard to estimate the permanent of a matrix with independent N (0, 1) complex Gaussian entries. I will then present one of my recent results (with Lior Eldar, FOCS 2018), which suggests that this conjecture does not hold for slightly biased complex Gaussian matrices. We show a quasi-polynomial time approximation algorithm for the permanent of random matrices with unit variance and non-zero but asymptotically vanishing mean.

Bio:

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

Please join the meeting in Sococo VH 102, or Zoom.

Join Zoom Meeting: https://tufts.zoom.us/j/98610939077

Meeting ID: 986 1093 9077

Passcode: see colloquium email

Dial by your location: +1 646 558 8656 US (New York)

Meeting ID: 986 1093 9077

Passcode: see colloquium email