<div dir="ltr"><div dir="ltr">Hi all — please join us this <b>Wednesday at 12pm</b> for theory lunch! Details below:<div><br></div><div>***<br><b>Date: </b>October 30, 2024, 12pm<br><b>Location: </b>JCL 298 <b>*** note room change this week! ***</b><br><br><b>Title: </b>How to Design a Quantum Streaming Algorithm Without Knowing Anything About Quantum Computing<br><br><b>Speaker: </b>Nadya Voronova, Boston University<br><br><b>Abstract:</b> 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.</div><br>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.<br><br>This talk is based on the following works.<br>[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. <a href="https://arxiv.org/abs/2410.18922">https://arxiv.org/abs/2410.18922</a><br>[2] "Exponential Quantum Space Advantage for Approximating Maximum Directed Cut in the Streaming Model" with John Kallaugher and Ojas Parekh, QIP'24, STOC'24. <a href="https://arxiv.org/abs/2311.14123">https://arxiv.org/abs/2311.14123</a></div></div>