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

Clement Louis Arthur Canonne ccanonne at
Tue May 14 20:26:11 PDT 2019

Reminder: this is tomorrow!

-- Clément

On May 8, 2019 4:28 PM, Clément Canonne <ccanonne at> wrote:
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.

theory-seminar mailing list
theory-seminar at
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the theory-seminar mailing list