  Quantum catalysis is an intricate feature of quantum entanglement. It
demonstrates that in certain situations the very presence of entanglement can
improve one's abilities of manipulating other entangled states. At the same
time, however, it is not clear if using entanglement catalytically can provide
additional power for any of the existing quantum protocols. Here we show, for
the first time, that catalysis of entanglement can provide a genuine advantage
in the task of quantum teleportation. More specifically, we show that extending
the standard teleportation protocol by giving Alice and Bob the ability to use
entanglement catalytically, allows them to achieve fidelity of teleportation at
least as large as the regularisation of the standard teleportation quantifier,
the so-called average fidelity of teleportation. Consequently, we show that
this regularised quantifier surpasses the standard benchmark for a variety of
quantum states, therefore demonstrating that there are quantum states whose
ability to teleport can be further improved when assisted with entanglement in
a catalytic way. This hints that entanglement catalysis can be a promising new
avenue for exploring novel advantages in the quantum domain.
