<html><body><div style="font-family: arial, helvetica, sans-serif; font-size: 12pt; color: #000000"><div><style><!--
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;
mso-font-charset:1;
mso-generic-font-family:roman;
mso-font-pitch:variable;
mso-font-signature:-536869121 1107305727 33554432 0 415 0;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;
mso-font-charset:0;
mso-generic-font-family:swiss;
mso-font-pitch:variable;
mso-font-signature:-536859905 -1073732485 9 0 511 0;}
p.MsoNormal, li.MsoNormal, div.MsoNormal
{mso-style-unhide:no;
mso-style-qformat:yes;
mso-style-parent:"";
margin:0in;
margin-bottom:.0001pt;
mso-pagination:widow-orphan;
font-size:11.0pt;
font-family:"Calibri",sans-serif;
mso-fareast-font-family:Calibri;
mso-fareast-theme-font:minor-latin;}
a:link, span.MsoHyperlink
{mso-style-noshow:yes;
mso-style-priority:99;
color:#0563C1;
text-decoration:underline;
text-underline:single;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-noshow:yes;
mso-style-priority:99;
color:#954F72;
text-decoration:underline;
text-underline:single;}
p.msonormal0, li.msonormal0, div.msonormal0
{mso-style-name:msonormal;
mso-style-unhide:no;
mso-margin-top-alt:auto;
margin-right:0in;
mso-margin-bottom-alt:auto;
margin-left:0in;
mso-pagination:widow-orphan;
font-size:12.0pt;
font-family:"Times New Roman",serif;
mso-fareast-font-family:Calibri;
mso-fareast-theme-font:minor-latin;}
span.EmailStyle18
{mso-style-type:personal;
mso-style-noshow:yes;
mso-style-unhide:no;
font-family:"Calibri",sans-serif;
mso-ascii-font-family:Calibri;
mso-hansi-font-family:Calibri;
mso-bidi-font-family:Calibri;
color:windowtext;}
span.EmailStyle19
{mso-style-type:personal;
mso-style-noshow:yes;
mso-style-unhide:no;
mso-ansi-font-size:11.0pt;
mso-bidi-font-size:11.0pt;
font-family:"Calibri",sans-serif;
mso-ascii-font-family:Calibri;
mso-ascii-theme-font:minor-latin;
mso-fareast-font-family:Calibri;
mso-fareast-theme-font:minor-latin;
mso-hansi-font-family:Calibri;
mso-hansi-theme-font:minor-latin;
mso-bidi-font-family:"Times New Roman";
mso-bidi-theme-font:minor-bidi;
color:#1F497D;}
span.EmailStyle20
{mso-style-type:personal-compose;
mso-style-noshow:yes;
mso-style-unhide:no;
mso-ansi-font-size:11.0pt;
mso-bidi-font-size:11.0pt;
font-family:"Calibri",sans-serif;
mso-ascii-font-family:Calibri;
mso-ascii-theme-font:minor-latin;
mso-fareast-font-family:Calibri;
mso-fareast-theme-font:minor-latin;
mso-hansi-font-family:Calibri;
mso-hansi-theme-font:minor-latin;
mso-bidi-font-family:"Times New Roman";
mso-bidi-theme-font:minor-bidi;
color:windowtext;}
.MsoChpDefault
{mso-style-type:export-only;
mso-default-props:yes;
font-size:10.0pt;
mso-ansi-font-size:10.0pt;
mso-bidi-font-size:10.0pt;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;
mso-header-margin:.5in;
mso-footer-margin:.5in;
mso-paper-source:0;}
div.WordSection1
{page:WordSection1;}
--></style></div><div data-marker="__QUOTED_TEXT__"><div class="WordSection1"><p class="MsoNormal"><a name="_MailOriginal">Umesh Vazirani from UC Berkeley</a></p><p class="MsoNormal"><span style="mso-bookmark:_MailOriginal">Monday, April 23, 2018 - 12:30pm</span></p><p class="MsoNormal"><span style="mso-bookmark:_MailOriginal">Computer Science - Room 105</span></p><p class="MsoNormal"><span style="mso-bookmark:_MailOriginal">Host: Sanjeev Arora </span></p><p class="MsoNormal"><span style="mso-bookmark:_MailOriginal"> </span></p><p class="MsoNormal"><span style="mso-bookmark:_MailOriginal">“Quantum Supremacy” and the Complexity of Random Circuit Sampling</span></p><p class="MsoNormal"><span style="mso-bookmark:_MailOriginal"> </span></p><p class="MsoNormal"><span style="mso-bookmark:_MailOriginal">A critical goal for the field of quantum computation is quantum supremacy -- a demonstration of any quantum computation that is prohibitively hard for classical computers. Besides dispelling any skepticism about the viability of quantum computers, quantum supremacy also provides a test of quantum theory in the realm of high complexity. A leading near-term candidate, put forth by the Google/UCSB team, is sampling from the probability distributions of randomly chosen quantum circuits, called Random Circuit Sampling (RCS).</span></p><p class="MsoNormal"><span style="mso-bookmark:_MailOriginal"> </span></p><p class="MsoNormal"><span style="mso-bookmark:_MailOriginal">While RCS was defined with experimental realization in mind (the first results are expected later this year), we give the first complexity-theoretic evidence of classical hardness of RCS, placing it on par with the best theoretical proposals for supremacy. Specifically, we show that RCS satisfies an average-case hardness condition -- computing output probabilities of typical quantum circuits is as hard as computing them in the worst-case, and therefore #P-hard. Our reduction exploits the polynomial structure in the output amplitudes of random quantum circuits, enabled by the Feynman path integral. We also describe a new verification measure which in some formal sense maximizes the information gained from experimental samples.</span></p><p class="MsoNormal"><span style="mso-bookmark:_MailOriginal"> </span></p><p class="MsoNormal"><span style="mso-bookmark:_MailOriginal">Based on joint work with Adam Bouland, Bill Fefferman and Chinmay Nirkhe.</span></p></div><br></div></div></body></html>