Correlation measure detecting almost all non-Markovian evolutions

We investigate the ability of correlation measures to witness non-Markovian open quantum system dynamics. It is shown that the mutual information and any entanglement measure between the system and an ancilla do not witness all non-Markovian dynamics. A new correlation measure is introduced, and it is proven that, in an enlarged setting with two ancillary systems, this measure detects almost all non-Markovian dynamics, except possibly a zero-measure set of dynamics that is non-bijective in finite time-intervals. Our proof is constructive and provides different initial states detecting the non-Markovian evolutions. These states are all separable and some are arbitrarily close to a product state.