Back to TGINF

# Hardness of RCS by Design

Speaker: Juspreet and Emil
Title: Hardness of RCS by Design
Date: 04 Mar 2019 5:30pm-7:00pm
Location: Maxwell-Dworkin 221
Food: Indian
Audience background:
Talk style:

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 [1] 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 [2]. As a result, such instances of RCS are a theoretically sound proposal of quantum supremacy. References:

References: