  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 \approx 0.4444$ requires
$\Omega(\sqrt{n})$ space for any classical streaming algorithm. Our result is
based on a recent $\widetilde{\text{O}}(\sqrt{n})$ 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].
