Speaker:

Uma Girish

Talk Title:

What makes quantum algorithms powerful?

Date and Location:

Thursday, February 20, 2025

Bahen Centre for Information Technology, BA 3200

This lecture is open to the public. No registration is required, but space is limited.

Abstract:

Quantum algorithms promise great speedups over classical algorithms, yet the principles behind these speedups remain elusive. When and why do quantum algorithms outperform classical ones? How do different models of quantum computing compare? These challenging questions lie at the core of quantum computing, where theoretical insights can shape the field’s future. This talk addresses these foundational questions.

First, I will introduce the Forrelation problem, a central problem that encapsulates many quantum speedups and show how it highlights the need for quantum resources like adaptivity and entanglement. I will then explore quantum speedups beyond Forrelation, particularly in the setting of quantum algorithms with highly noisy qubits. These works draw on connections with theoretical computer science, mathematics, and physics.

About Uma Girish:

Uma Girish is a postdoc at Columbia University. She graduated from Princeton University in 2024, advised by Prof. Ran Raz. She is broadly interested in quantum computing and theoretical computer science, with a focus on foundations of quantum algorithms and speedups, quantum complexity theory, Fourier analysis and pseudorandomness.