  Optimal transport provides a powerful mathematical framework with
applications spanning numerous fields. A cornerstone within this domain is the
$p$-Wasserstein distance, which serves to quantify the cost of transporting one
probability measure to another. While recent attempts have sought to extend
this measure to the realm of quantum states, existing definitions often present
certain limitations, such as not being faithful. In this work, we present a new
definition of quantum Wasserstein distances. This definition, leveraging the
coupling method and a metric applicable to pure states, draws inspiration from
a property characterising the classical Wasserstein distance - its
determination based on its value on point masses. Subject to certain continuity
properties, our definition exhibits numerous attributes expected of an optimal
quantum rendition of the Wasserstein distance. Notably, our approach seamlessly
integrates metrics familiar to quantum information theory, such as the trace
distance. Moreover, it provides an organic extension for metrics, like
Nielsen's complexity metric, allowing their application to mixed states with a
natural operational interpretation. Furthermore, we analyze this metric's
attributes in the context of random quantum states and unveil phase transitions
concerning the complexity of subsystems of random states.
