Search Mailing List Archives
[theory-seminar] TCS+ talk: Wednesday, May 15th, Ewin Tang, University of Washington
Clement Louis Arthur Canonne
ccanonne at stanford.edu
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 cs.stanford.edu> 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,
Clément
-------------------------------
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 lists.stanford.edu
https://mailman.stanford.edu/mailman/listinfo/theory-seminar
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.stanford.edu/pipermail/theory-seminar/attachments/20190515/b23a8b68/attachment.html>
More information about the theory-seminar
mailing list