Quantum algorithms for Uhlmann transformation

Uhlmann's theorem is a central result in quantum information theory, which associates the closeness of two quantum states with that of their purifications. The theorem also well characterizes a fundamental task: how close a pure quantum state can be transformed into another state via local operations acting only on its subsystem. The optimal transformation for this task is called the Uhlmann transformation, which has broad applications in various information-processing tasks. However, its quantum circuit implementation and computational cost have remained unclear, limiting the utility of the transformation. In this work, we fill this gap by proposing quantum algorithms that realize the Uhlmann transformation in query and sample access models. Notably, our Uhlmann transformation algorithms can be polynomial-time for low-rank states, exhibiting an exponential improvement over the previous approach and other naive approaches based on quantum state tomography. In addition, we derive a lower bound on the query and sample complexities of the Uhlmann transformation for a deeper understanding of its algorithmic features. We apply our Uhlmann transformation algorithms to fidelity estimation between two states, and substantially improve the previous best query and sample complexities. We further discuss other applications to several information-theoretic tasks, including entanglement transmission, quantum state merging, and the algorithmic implementation of the Petz recovery map, providing a comprehensive evaluation of their computational costs. These results, hence, contribute to the practical realization of such widely recognized and useful protocols.