Consider a quantum state $\lvert \psi \rangle$, we know from the no cloning theorem, that it cannot be perfectly cloned. Also, loosely speaking, that it can be imperfectly cloned s.t. one can produce a qubit with reduced density matrix of $\rho$, where $\langle \psi \vert \rho \vert \psi \rangle = 5/6$. (for references see Robin Kothari's answer)
Suppose we call any two states $\lvert \psi \rangle$ and $\lvert \phi \rangle$ Similar, if $\langle \psi \vert \phi \rangle \langle \phi \vert \psi \rangle > 5/6 + \epsilon$, where $\epsilon$ is some small fraction
So, given a state $\lvert \psi \rangle$, is finding another 'Similar' state computationally hard, or information theoretically?