  Two of the fundamental no-go theorems of quantum information are the
no-cloning theorem (that it is impossible to make copies of general quantum
states) and the no-teleportation theorem (the prohibition on sending quantum
states over classical channels without pre-shared entanglement). They are known
to be equivalent, in the sense that a collection of quantum states is
teleportable without entanglement if and only if it is clonable.
  Our main result suggests that this is not the case when computational
efficiency is considered. We give a collection of quantum states and quantum
oracles relative to which these states are efficiently clonable but not
efficiently teleportable without entanglement. Given that the opposite scenario
is impossible (states that can be teleported without entanglement can always
trivially be cloned), this gives the most complete quantum oracle separation
possible between these two important no-go properties.
  We additionally study the complexity class $\mathsf{clonableQMA}$, a subset
of $\mathsf{QMA}$ whose witnesses are efficiently clonable. As a consequence of
our main result, we give a quantum oracle separation between
$\mathsf{clonableQMA}$ and the class $\mathsf{QCMA}$, whose witnesses are
restricted to classical strings. We also propose a candidate oracle-free
promise problem separating these classes. We finally demonstrate an application
of clonable-but-not-teleportable states to cryptography, by showing how such
states can be used to protect against key exfiltration.
