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. This talk is based on joint work with Natalie Parham, arxiv:2301.00995.
*We strongly encourage attendees to use their full name (and if possible, their UMD credentials) to join the zoom session.*