\section{Ensemble-based memory implementation}  
Memory experiments were driven at a repetition rate of 66 Hz, each cycle including a stage dedicated to MOT preparation and a period for memory operations (Fig. \ref{setup}c). The MOT preparation started with 11.5 ms of MOT loading followed by further cooling by optical molasses during 650 $\mu$s while the MOT magnetic field gradient was switched off. The optical depth decays then in a typical time constant of 2 ms and the memory efficiency stays thus almost constant over the memory period. Memory sequences were repeated 50 or 100 times during the memory operation part of the cycle (depending on the storage time), for a total number of acquisition of $150000$ for each projection. Temporal shaping of the pulses to be stored was obtained by applying a radio-frequency exponentially rising voltage on an acousto-optic modulator and photons were finally detected by a single avalanche photodiode (SPCM-AQR-14FC). In order to avoid inhomogeneous broadening, three pairs of coils were used to compensate any residual magnetic fields, down to 5 mG. The retrieval efficiency decays with storage time due to the decoherence of the collective atomic spin. Motional dephasing was the principal decoherence here. Due to the  $3 ^{\circ}$ angle between the signal and the control beams, the expected coherence time is around 7 $\mu$s, which is consistent with the experimental measurement.

\section{Assessing the quantum character of the memory} 
In order to assess the quantum character of the demonstrated memory, the measured fidelities have to be compared with the maximum fidelities achievable in a classical memory protocol, known for instance as the intercept-resend attack in quantum cryptography scenario. In the case of a N-photon state the maximal classical fidelity is given by $\alpha=(N+1)/(N+2)$, which leads to the well-known 2/3 limit for a single-photon state.
In the case of a coherent beam, as used here, the N-photon value $\alpha$ has to be averaged by taking into account the photon-number Poissonian distribution and the achievable fidelity can then be written as:
\begin{equation}
\sum_{N\geq 1}\frac{(N+1)}{(N+2)}\frac{P(\overline{n},N)}{1-P(\overline{n},0)}
\end{equation}
where $P(\overline{n},N)=e^{-\overline{n}} \overline{n}^{N}/N! $. The non-unity retrieval efficiency has also to be taken into account. A classical memory in an intercept-resend strategy could indeed simulate non-unity efficiencies to increase the achievable fidelity by giving an output only when the entering photon-number is above a certain threshold and inducing losses otherwise. Explicit expression for given mean-photon number and efficiency of the process are detailed in Refs. \cite{Specht11,Gundogan12}. The maximal classical fidelities have been reported in Fig. \ref{tom}b and \ref{fid}b 
where the blue and orange solid lines, which take into account  the Poissonian statistics and non-unity efficiency respectively, are extrapolated by calculating the best classical fidelity with the measured values of mean-photon number and
retrieval efficiency for every data set.
 
\section*{Acknowledgements}
\noindent The authors thank A. Nicolas, D. Maxein, E. Giacobino, L. Giner and L. Veissier for their contributions in the early stage of the experiment. The authors also acknowledge interesting discussions within the CAPES-COFECUB project Ph 740-12. This work was supported by the ERA-Net CHIST-ERA (QScale) and by the European Research Council (ERC Starting Grant HybridNet, grant agreement no. 307450  and ERC Starting Grant 3D-QUEST, grant agreement no. 307783, http://www.3dquest.eu.). J.Laurat is a member of the Institut Universitaire de France.\\


