  To quantify non-Markovianity of tripartite quantum states from an operational
viewpoint, we introduce a class $\Omega^*$ of operations performed by three
distant parties. A tripartite quantum state is a free state under $\Omega^*$ if
and only if it is a quantum Markov chain. We introduce a function of tripartite
quantum states that we call the non-Markovianity of formation, and prove that
it is a faithful measure of non-Markovianity, which is continuous and
monotonically nonincreasing under a subclass $\Omega$ of $\Omega^*$. We
consider a task in which the three parties generate a non-Markov state from
scratch by operations in $\Omega$, assisted with quantum communication from the
third party to the others, which does not belong to $\Omega$. We prove that the
minimum cost of quantum communication required therein is asymptotically equal
to the regularized non-Markovianity of formation. Based on this result, we
provide a direct operational meaning to a measure of bipartite entanglement
called the c-squashed entanglement.
