Search Mailing List Archives

Limit search to: Subject & Body Subject Author
Sort by: Reverse Sort
Limit to: All This Week Last Week This Month Last Month
Select Date Range     through    

[theory-seminar] TCS+ talk: Wednesday, May 15th, Ewin Tang, University of Washington

Clément Canonne ccanonne at
Wed May 8 16:28:24 PDT 2019

Hi all,

Next Wednesday (May 15th) at 10:00 AM, Ewin Tang (University of 
Washington) will give a TCS+ on "Quantum-inspired classical linear 
algebra algorithms: why and how?" (abstract below).

I've reserved a spot in the hangouts, so that we can watch the talk live 
and ask her questions. There will be breakfast (classical, not quantum)!

See you there,


Speaker: Ewin Tang (University of Washington)
Title: Quantum-inspired classical linear algebra algorithms: why and how?

Abstract:  Over the past ten years, the field of quantum machine 
learning (QML) has produced many polylogarithmic-time procedures for 
linear algebra routines, assuming certain "state preparation" 
assumptions. Though such algorithms are formally incomparable with 
classical computing, a recent line of work uses an analogous classical 
model of computation as an effective point of comparison to reveal 
speedups (or lack thereof) gained by QML. The resulting "dequantized" 
algorithms assume sampling access to input to speed up runtimes to 
polylogarithmic in input size.

In this talk, we will discuss the motivation behind this model and its 
relation to existing randomized linear algebra literature. Then, we will 
delve into an example quantum-inspired algorithm: Gilyen, Lloyd, and 
Tang's algorithm for low-rank matrix inversion. This dequantizes a 
variant of Harrow, Hassidim, and Lloyd's matrix inversion algorithm, a 
seminal work in QML. Finally, we will consider the implications of this 
work on exponential speedups in QML. No background of quantum computing 
is assumed for this talk.

More information about the theory-seminar mailing list