https://www.seas.harvard.edu/calendar/event/113676
title: "Quantum Supremacy" and the Complexity of Random Circuit Sampling
Theory of Computation Seminar
Bill Fefferman, University of California at Berkeley
Monday, May 14, 2018
1:15pm to 2:15pm
Maxwell Dworkin 119
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
_______________________________________________
qip mailing list
qip(a)mit.edu
http://mailman.mit.edu/mailman/listinfo/qip