  We investigate the space complexity of two graph streaming problems: Max-Cut
and its quantum analogue, Quantum Max-Cut. Previous work by Kapralov and
Krachun [STOC `19] resolved the classical complexity of the \emph{classical}
problem, showing that any $(2 - \varepsilon)$-approximation requires
$\Omega(n)$ space (a $2$-approximation is trivial with $\textrm{O}(\log n)$
space). We generalize both of these qualifiers, demonstrating $\Omega(n)$ space
lower bounds for $(2 - \varepsilon)$-approximating Max-Cut and Quantum Max-Cut,
even if the algorithm is allowed to maintain a quantum state. As the trivial
approximation algorithm for Quantum Max-Cut only gives a $4$-approximation, we
show tightness with an algorithm that returns a $(2 +
\varepsilon)$-approximation to the Quantum Max-Cut value of a graph in
$\textrm{O}(\log n)$ space. Our work resolves the quantum and classical
approximability of quantum and classical Max-Cut using $\textrm{o}(n)$ space.
  We prove our lower bounds through the techniques of Boolean Fourier analysis.
We give the first application of these methods to sequential one-way quantum
communication, in which each player receives a quantum message from the
previous player, and can then perform arbitrary quantum operations on it before
sending it to the next. To this end, we show how Fourier-analytic techniques
may be used to understand the application of a quantum channel.
