<p>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 <a href="https://cstheory.stackexchange.com/a/30783/17325,">answer</a>)</p>

<p>Suppose we call any two states $\lvert \psi \rangle$ and $\lvert \phi \rangle$ <strong>Similar</strong>, if $\langle \psi \vert \phi \rangle \langle \phi \vert \psi \rangle &gt; 5/6 + \epsilon$, where $\epsilon$ is some small fraction</p>

<p>So, given a state $\lvert \psi \rangle$, is finding another 'Similar' state computationally hard, or information theoretically?</p>

CC BY-SA 3.0
2015-03-17T01:52:27.033Z
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
CC BY-SA 3.0
2015-03-17T04:27:43.887Z
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
<quantum-computing><quantum-information>
Hardness of finding similar (quantum) states
Subhayan
# Hardness of finding similar (quantum) states

(Asked by: username_0 on 2015-03-16)

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](https://cstheory.stackexchange.com/a/30783/17325,))

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?

**Tags:** quantum-computing, quantum-information
> **Comments:**
> **username_1**: 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.  
> **username_0**: 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?  

---

## 0 answers

