Exponential Quantum Space Advantage for Approximating Maximum Directed Cut in the Streaming Model

While the search for quantum advantage typically focuses on speedups in execution time, quantum algorithms also offer the potential for advantage in space complexity. Previous work has shown such advantages for data stream problems, in which elements arrive and must be processed sequentially without random access, but these have been restricted to specially-constructed problems [Le Gall, SPAA `06] or polynomial advantage [Kallaugher, FOCS `21]. We show an exponential quantum space advantage for the maximum directed cut problem. This is the first known exponential quantum space advantage for any natural streaming problem. This also constitutes the first unconditional exponential quantum resource advantage for approximating a discrete optimization problem in any setting.

Our quantum streaming algorithm 0.4844-approximates the value of the largest directed cut in a graph stream with n vertices using polylog(n) space, while previous work by Chou, Golovnev, and Velusamy [FOCS '20] implies that obtaining an approximation ratio better than 4/9≈0.4444 requires Ω(√n) space for any classical streaming algorithm. Our result is based on a recent space classical streaming approach by Saxena, Singer, Sudan, and Velusamy [FOCS '23], with an additional improvement in the approximation ratio due to recent work by Singer [APPROX '23].

Additionally, our work introduces a simple quantum sketch that encompasses several results [GKK+08, Kal21, KPV24] on asymptotic quantum advantages in space complexity in the streaming model, allowing them to be derived from entirely classical algorithms using our quantum sketch as a black box.

The talk is based on joint works with John Kallaugher and Ojas Parekh:
- "Exponential Quantum Space Advantage for Approximating Maximum Directed Cut in the Streaming Model", https://arxiv.org/abs/2311.14123
- "How to Design a Quantum Streaming Algorithm Without Knowing Anything About Quantum Computing", in submission

*We strongly encourage attendees to use their full name (and if possible, their UMD credentials) to join the zoom session.*