© 2014 American Physical Society. Quantum technology promises revolutionary advantages in information processing and transmission compared to classical technology; however, determining which specific resources are needed to surpass the capabilities of classical machines often remains a nontrivial problem. To address such a problem, one first needs to establish the best classical solutions, which set benchmarks that must be beaten by any implementation claiming to harness quantum features for an enhanced performance. Here we introduce and develop a self-contained formalism to obtain the ultimate, generally probabilistic benchmarks for quantum information protocols including teleportation and approximate cloning, with arbitrary ensembles of i...