[Theory] [Theory Lunch] Nadya Voronova, Wednesday, 10/30, 12-1pm, JCL 298

[Gabe Schoenbach via Theory]

Hi all — please join us this *Wednesday at 12pm* for theory lunch! Details
below:

***
*Date: *October 30, 2024, 12pm
*Location: *JCL 298 **** note room change this week! ****

*Title: *How to Design a Quantum Streaming Algorithm Without Knowing
Anything About Quantum Computing

*Speaker: *Nadya Voronova, Boston University

*Abstract:* A series of works [GKK+08], [Kal22], [2] has shown that
asymptotic advantages in space are possible for quantum algorithms over
their classical counterparts in the streaming model. In particular, in the
recent work [2] with my collaborators John Kallaugher and Ojas Parekh, we
showed the first example of exponential quantum space advantage for a
natural problem in the streaming setting. In our new work [1], we give a
simple quantum sketch that encompasses all the results in this series,
allowing them to be derived from entirely classical algorithms using our
quantum sketch as a black box.

In this talk, I will introduce this quantum sketch and give some intuition
on how it can be used in the stream to approximate the Maximum Directed Cut
and, if time allows, how to approximate the number of triangles in the
input graph. The talk is fully accessible without any knowledge of quantum
computing.

This talk is based on the following works.
[1] "How to Design a Quantum Streaming Algorithm Without Knowing Anything
About Quantum Computing" with John Kallaugher and Ojas Parekh, to appear at
SOSA'25. https://arxiv.org/abs/2410.18922
[2] "Exponential Quantum Space Advantage for Approximating Maximum Directed
Cut in the Streaming Model" with John Kallaugher and Ojas Parekh, QIP'24,
STOC'24. https://arxiv.org/abs/2311.14123
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20241028/c7f59269/attachment.html>