log in  |  register  |  feedback?  |  help  |  web accessibility
Logo
Unconditional Separations with Constant Depth Circuits
Adam Bene Watts - IQC and University of Waterloo
Wednesday, May 10, 2023, 11:00 am-12:00 pm Calendar
  • You are subscribed to this talk through .
  • You are watching this talk through .
  • You are subscribed to this talk. (unsubscribe, watch)
  • You are watching this talk. (unwatch, subscribe)
  • You are not subscribed to this talk. (watch, subscribe)
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.*

This talk is organized by Andrea F. Svejda