  In a work by Raz (J. ACM and FOCS 16), it was proved that any algorithm for
parity learning on $n$ bits requires either $\Omega(n^2)$ bits of classical
memory or an exponential number (in~$n$) of random samples. A line of recent
works continued that research direction and showed that for a large collection
of classical learning tasks, either super-linear classical memory size or
super-polynomially many samples are needed. However, these results do not
capture all physical computational models, remarkably, quantum computers and
the use of quantum memory. It leaves the possibility that a small piece of
quantum memory could significantly reduce the need for classical memory or
samples and thus completely change the nature of the classical learning task.
  In this work, we prove that any quantum algorithm with both, classical memory
and quantum memory, for parity learning on $n$ bits, requires either
$\Omega(n^2)$ bits of classical memory or $\Omega(n)$ bits of quantum memory or
an exponential number of samples. In other words, the memory-sample lower bound
for parity learning remains qualitatively the same, even if the learning
algorithm can use, in addition to the classical memory, a quantum memory of
size $c n$ (for some constant $c>0$).
  Our results refute the possibility that a small amount of quantum memory
significantly reduces the size of classical memory needed for efficient
learning on these problems. Our results also imply improved security of several
existing cryptographical protocols in the bounded-storage model (protocols that
are based on parity learning on $n$ bits), proving that security holds even in
the presence of a quantum adversary with at most $c n^2$ bits of classical
memory and $c n$ bits of quantum memory (for some constant $c>0$).
