Hardness of RCS by DesignSpeaker: Juspreet and Emil
Title: Hardness of RCS by Design
Date: 04 Mar 2019 5:30pm-7:00pm
Location: Maxwell-Dworkin 221
Abstract: An outstanding challenge in quantum computation is performing some task that cannot be done efficiently classically. One proposal is Random Circuit Sampling (RCS), where sampling from the output distribution of a short-depth quantum circuit of random, local 2-qubit gates was conjectured to be $\ShP$-hard. We explain the proof  of this conjecture in the average case, using a worst-to-average case reduction and show that RCS satisfies an anti-concentration property. Circuits that form approximate unitary 2-designs satisfy anti-concentration; we show that a depth $\sqrt(n)$ random circuit on a $2d$ lattice is such a design . As a result, such instances of RCS are a theoretically sound proposal of quantum supremacy. References:
 Bouland et al.
 Harrow & Mehraban.