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

John Kallaugher, Ojas Parekh, Nadezhda Voronova

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…