  Cumulative memory -- the sum of space used per step over the duration of a
computation -- is a fine-grained measure of time-space complexity that was
introduced to analyze cryptographic applications like password hashing. It is a
more accurate cost measure for algorithms that have infrequent spikes in memory
usage and are run in environments such as cloud computing that allow dynamic
allocation and de-allocation of resources during execution, or when many
multiple instances of an algorithm are interleaved in parallel.
  We prove the first lower bounds on cumulative memory complexity for both
sequential classical computation and quantum circuits. Moreover, we develop
general paradigms for bounding cumulative memory complexity inspired by the
standard paradigms for proving time-space tradeoff lower bounds that can only
lower bound the maximum space used during an execution. The resulting lower
bounds on cumulative memory that we obtain are just as strong as the best
time-space tradeoff lower bounds, which are very often known to be tight.
  Although previous results for pebbling and random oracle models have yielded
time-space tradeoff lower bounds larger than the cumulative memory complexity,
our results show that in general computational models such separations cannot
follow from known lower bound techniques and are not true for many functions.
  Among many possible applications of our general methods, we show that any
classical sorting algorithm with success probability at least
$1/\text{poly}(n)$ requires cumulative memory $\tilde \Omega(n^2)$, any
classical matrix multiplication algorithm requires cumulative memory
$\Omega(n^6/T)$, any quantum sorting circuit requires cumulative memory
$\Omega(n^3/T)$, and any quantum circuit that finds $k$ disjoint collisions in
a random function requires cumulative memory $\Omega(k^3n/T^2)$.
