Single photons are a vital resource for optical quantum information processing. Efficient and deterministic single photon sources do not yet exist, however. To date, experimental demonstrations of quantum processing primitives have been implemented using non-deterministic sources combined with heralding and/or postselection. Unfortunately, even for eight photons, the data rates are already so low as to make most experiments impracticable. It is well known that quantum memories, capable of storing photons until they are needed, are a potential solution to this `scaling catastrophe'. Here, we analyze in detail the benefits of quantum memories for producing multiphoton states, showing how the production rates can be enhanced by many orders of magnitude. We identify the quantity $\eta B$ as the most important figure of merit in this connection, where $\eta$ and $B$ are the efficiency and time-bandwidth product of the memories, respectively.