[Colloquium] CS Seminar Oct 10: Bill Fefferman, UC Berkeley/NIST

[Sandra Wallace via Colloquium]

UNIVERSITY OF CHICAGO
DEPARTMENT OF COMPUTER SCIENCE
PRESENTS



Bill Fefferman
University of California at Berkeley/NIST
	

Wednesday, October 10, 2018 at 10:00 am
Crerar 390


Title:  Quantum Supremacy” and the Complexity of Random Circuit Sampling

Abstract:
A critical goal for the field of quantum computing is quantum supremacy -- a demonstration of a quantum computation that is
prohibitively hard for classical computers. Besides dispelling any skepticism about the experimental 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).

While RCS was defined with experimental realization in mind, we give 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.

Based on joint work with Adam Bouland, Chinmay Nirkhe and Umesh Vazirani, available https://arxiv.org/abs/1803.04402.
 
Bio:
Bill Fefferman is an Assistant Research Professor at the University of Maryland and the National Institute of Standards and Technology, as
well as a visiting scholar at the University of California at Berkeley, advised by Umesh Vazirani.  Previously, he defended his PhD
in Computer Science at Caltech, advised by Chris Umans and Alexei Kitaev.  He has recently been awarded the 2018 Air Force Young
Investigator Award to pursue his research interests in near term quantum computing and computational complexity theory.

Host:  Fred Chong



-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20180926/e69fe693/attachment-0003.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: PastedGraphic-1.tiff
Type: image/tiff
Size: 26892 bytes
Desc: not available
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20180926/e69fe693/attachment-0001.tiff>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20180926/e69fe693/attachment-0004.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Fefferman talk.pdf
Type: application/pdf
Size: 1198464 bytes
Desc: not available
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20180926/e69fe693/attachment-0001.pdf>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20180926/e69fe693/attachment-0005.html>