HQI Special Seminar – Uma Girish (Princeton) Monday, April 10, 2023 4:00 – 4:45 PM Pierce 209 Title: Space-Bounded Quantum Computation & Quantum versus Classical Separations The study of space-bounded quantum computation is important, as quantum computers in the near future are likely to have limited memory. We present space-efficient methods for eliminating intermediate measurements in quantum algorithms and establish fascinating connections of this problem to matrix powering and derandomization. Understanding the relative advantages of quantum over classical computation is a fascinating problem. While quantum algorithms are widely believed to outperform classical ones, there are very few settings in which this has been proved without assumptions. Query and communication complexity are striking examples of such settings. We study the advantages of quantum over classical in these settings and show improved quantum versus classical separations. If you would like to meet with Uma Girish during her visit on April 10-11, please contact cploucha@fas.harvard.edu<mailto:cploucha@fas.harvard.edu>