<html><body style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;"><head><meta http-equiv="Content-Type" content="text/html; charset=utf-8"></head><div class="" style="orphans: 2; widows: 2;"><span class="" style="font-size: 14px;"></span></div><div class="" style="orphans: 2; widows: 2;"><br class=""></div><div class="" style="orphans: 2; widows: 2;"><div class="" style="margin: 0in 0in 0.0001pt;"><b class=""><font size="4" class="">Bill Fefferman</font></b></div><div class="" style="margin: 0in 0in 0.0001pt;"><span style="font-size: 14px;" class=""><i class="">University of California at Berkeley/NIST<br class=""></i></span><div class=""><span style="font-size: 14px;" class=""><i class=""><span class="Apple-tab-span" style="white-space: pre;"> </span></i></span></div></div><div class="" style="margin: 0in 0in 0.0001pt;"><b class=""><font class="" style="font-size: 14px;"><br class=""></font></b></div><div class="" style="margin: 0in 0in 0.0001pt;"><span class="" style="font-size: 14px;"><b class=""><font class="">Wednesday, October 10, 2018 at 10:00 am<br class="">Crerar 390</font></b><br class=""></span></div></div><div class="" style="orphans: 2; widows: 2;"><span class="" style="font-size: 14px;"><br class=""></span></div><div class=""><br class=""></div><div class=""><div class=""><b class="" style="color: rgb(33, 33, 33); font-family: Roboto, Helvetica, Arial, sans-serif; font-size: 14px;">Title: </b><font color="#212121" face="Roboto, Helvetica, Arial, sans-serif" class=""><span class="" style="font-size: 14px;">Quantum Supremacy” and the Complexity of Random Circuit Sampling</span></font></div><div class="" style="color: rgb(33, 33, 33); font-family: Roboto, Helvetica, Arial, sans-serif; font-size: 14px;"><b class=""><br class=""></b></div><div class="" style="color: rgb(33, 33, 33); font-family: Roboto, Helvetica, Arial, sans-serif; font-size: 14px;"><b class="">Abstract:</b></div><div class=""><font class=""><span class=""><div class="" style="font-variant-ligatures: normal; background-color: rgb(255, 255, 255);"><div class=""><font color="#222222" class=""><span style="font-size: 14px;" class="">A critical goal for the field of quantum computing is quantum supremacy -- a demonstration of a quantum computation that is<br class="">prohibitively hard for classical computers. Besides dispelling any skepticism about the experimental viability of quantum computers,<br class="">quantum supremacy also provides a test of quantum theory in the realm of high complexity. A leading near-term candidate, put forth by the<br class="">Google/UCSB team, is sampling from the probability distributions of randomly chosen quantum circuits, called Random Circuit Sampling<br class="">(RCS).<br class=""><br class="">While RCS was defined with experimental realization in mind, we give complexity-theoretic evidence of classical hardness of RCS, placing it<br class="">on par with the best theoretical proposals for supremacy. Specifically, we show that RCS satisfies an average-case hardness<br class="">condition -- computing output probabilities of typical quantum circuits is as hard as computing them in the worst-case, and therefore<br class="">#P-hard. Our reduction exploits the polynomial structure in the output amplitudes of random quantum circuits, enabled by the Feynman path<br class="">integral. We also describe a new verification measure which in some formal sense maximizes the information gained from experimental<br class="">samples.<br class=""><br class="">Based on joint work with Adam Bouland, Chinmay Nirkhe and Umesh Vazirani, available <a href="https://arxiv.org/abs/1803.04402" class="">https://arxiv.org/abs/1803.04402</a>.</span><br class=""></font><span class="" style="color: rgb(33, 33, 33); font-size: 14px; font-family: Roboto, Helvetica, Arial, sans-serif;"> </span></div></div></span></font><b class="" style="color: rgb(33, 33, 33); font-family: Roboto, Helvetica, Arial, sans-serif; font-size: 14px;">Bio:</b></div><div class=""><div class="" style="font-variant-ligatures: normal; background-color: rgb(255, 255, 255);"><font color="#222222" class=""><span style="font-size: 14px;" class=""><i class="">Bill Fefferman is an Assistant Research Professor at the University of Maryland and the National Institute of Standards and Technology, as<br class="">well as a visiting scholar at the University of California at Berkeley, advised by Umesh Vazirani. Previously, he defended his PhD<br class="">in Computer Science at Caltech, advised by Chris Umans and Alexei Kitaev. He has recently been awarded the 2018 Air Force Young<br class="">Investigator Award to pursue his research interests in near term quantum computing and computational complexity theory.</i></span></font></div><div class="" style="color: rgb(34, 34, 34); font-variant-ligatures: normal; background-color: rgb(255, 255, 255);"><span class="" style="font-size: 14px;"><i class=""><br class=""></i></span></div></div><div class=""><b class="" style="color: rgb(33, 33, 33); font-family: Roboto, Helvetica, Arial, sans-serif; font-size: 14px;">Host: Fred Chong</b></div><div class=""><b class="" style="color: rgb(33, 33, 33); font-family: Roboto, Helvetica, Arial, sans-serif; font-size: 14px;"><br class=""></b></div><div class=""><b class="" style="color: rgb(33, 33, 33); font-family: Roboto, Helvetica, Arial, sans-serif; font-size: 14px;"></b></div></div></body></html>