# Hardness of finding similar (quantum) states

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?

• If you don't have to preserve your input then isn't it trivial since you can just return $|\psi\rangle$? If you have to preserve your input and also provide an output then isn't it impossible according to the upper bounds in Robin Kothari's answer? Since otherwise your output of $|\phi\rangle\langle\phi|$ would violate the bound. Did you maybe mean $5/6 - \epsilon$? In that case, what is the complexity of Bužek & Hillery's procedure? You should include that in your question to show what you thought about already. – Artem Kaznatcheev Mar 17 '15 at 1:52
• thanks @ArtemKaznatcheev, and yes ofcourse the input state must be preserved. A result i know due to Buhrman et. al. is for a set of states satisfying $|<\psi^n | \phi^n>|<=0.9$, there can be a set of size $2^{O(2^n)}$. But what if one is allowed to guess the state? – Subhayan Mar 17 '15 at 4:27