IQIM Postdoctoral and Graduate Student Seminar

Abstract: Over the past 6 years, a series of works have shown unconditional separations between the computational power of constant depth quantum and classical circuits. This talk will begin with a review of these circuit classes and separations. Then we'll discuss some tips and tricks -- essentially circuit identities -- which are useful when constructing constant depth quantum circuits with superclassical computational power. Finally, we'll show how to put all these ingredients together to give a constant depth, width n, quantum circuit that samples from a distribution which cannot be sampled from by any constant depth, bounded fanin and fanout classical circuit (i.e. NC^0 circuit) with access to n uniformly random input bits.

Lunch will be provided, following the talk, on the lawn north of the Bridge Arcade

Attendees joining in person must demonstrate that they comply with Caltech's vaccination requirements (present Caltech ID or AWS ID or vaccination and booster confirmation).