Abstract
We explore in a rigorous manner the intuitive connection between the non-Markovianity of the evolution of an open quantum system and the performance of the system as a quantum memory. Using the paradigmatic case of a two-level open quantum system coupled to a bosonic bath, we compute the recovery fidelity, which measures the best possible performance of the system to store a qubit of information. We deduce that this quantity is connected, but not uniquely determined, by the non-Markovianity, for which we adopt the BLP measure proposed in \cite{breuer2009}. We illustrate our findings with explicit calculations for the case of a structured environment.