Seminar • Quantum Computing • Algorithms, Circuits and Learning with Quantum Computers

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.