[talks] Colloquium Speaker-Umesh Vazirani, Monday, April 23

[Emily Lawrence]

Umesh Vazirani from UC Berkeley

Monday, April 23, 2018 - 12:30pm

Computer Science - Room 105

Host: Sanjeev Arora 

 

"Quantum Supremacy" and the Complexity of Random Circuit Sampling

 

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).

 

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.

 

Based on joint work with Adam Bouland, Bill Fefferman and Chinmay Nirkhe.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.cs.princeton.edu/pipermail/talks/attachments/20180419/c4f79944/attachment.html>