Please note: This seminar will take place in DC 1304.
Luke
Schaeffer,
QuICS
Hartree
Postdoctoral
Fellow
Joint
Center
for
Quantum
Information
and
Computer
Science,
University
of
Maryland
We explore the provable advantages and limitations of quantum computers in three contexts. First, we consider learning a quantum state from samples in the setting of observable estimation, and the potential advantage of assuming pure samples and using optimal joint measurements. We analyze how the performance degrades when the samples are noisy and discuss improved algorithms for purification and eigenvalue estimation. Second, we discuss unconditional quantum advantage with shallow circuits. We give separations with relation problems and interactive problems, as well as examine the possibility of a separation in time. Finally, we present a trichotomy result for the regular languages, and survey the implications for quantum search and algorithm design.
Bio: Luke Schaeffer is a QuICS Hartree Postdoctoral Fellow at University of Maryland, College Park. His interests include quantum algorithms and complexity, quantum state tomography, and theoretical computer science in general. He received a doctorate in computer science from MIT, and was a postdoc at IQC in Waterloo before joining QuICS.