Random quantum circuits and quantum supremacySpeaker: Chi-Ning
Title: Random quantum circuits and quantum supremacy
Date: 13 Apr 2020 12:00pm-1:00pm
Zoom link: https://harvard.zoom.us/j/92874210982
Abstract: Quantum computational supremacy refers to experimental violations of the extended Church Turing Hypothesis using quantum computers. Recently, Google announced achieving quantum supremacy through the random circuit sampling task. Namely, they constructed a quantum computer that can efficiently execute a quantum circuit and sample outputs that follow the marginal distribution of the circuit. In the meantime, sampling the marginal distribution of a random quantum circuit is conjectured to be a hard task for classical computers.
In this talk, we will see the theoretical setting of sampling based quantum supremacy. Then, as a classical theoretical computer scientist, I will discuss several best known classical algorithms as well as our new classical algorithm (joint work with Boaz Barak and Xun Gao) that attack the sampling based quantum supremacy. If time allowed, I’ll introduce some elementary tensor networks which might be of independent interest for the audience.