  We revisit the task of quantum state redistribution in the one-shot setting,
and design a protocol for this task with communication cost in terms of a
measure of distance from quantum Markov chains. More precisely, the distance is
defined in terms of quantum max-relative entropy and quantum hypothesis testing
entropy.
  Our result is the first to operationally connect quantum state redistribution
and quantum Markov chains, and can be interpreted as an operational
interpretation for a possible one-shot analogue of quantum conditional mutual
information. The communication cost of our protocol is lower than all
previously known ones and asymptotically achieves the well-known rate of
quantum conditional mutual information. Thus, our work takes a step towards the
important open question of near-optimal characterization of the one-shot
quantum state redistribution.
