Stack Exchange network consists of 183 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.
I asked a similar question before here. The answer I accepted was mainly about mixed states, but I don't think much is known about the pure state case.
@TristanNemoz Oh, I miscalculated a little bit. We have to call the the original algorithm $\Omega \left ( \frac{log(1)-log(3)}{log \left ( 2^{2x} - 1 \right ) - log \left ( 2^{2x} \right )} \right )$ where $x$ is the number of qubits in each state. I think this is super exponential. Thus I retract my previous statement; we can use copies of the two states.
@TristanNemoz Oh, I haven’t considered that. I believe that we could simply run the algorithm a quasipolynomial number of times (some term that’s a bit long to write here) and watch out for a nonzero output value. I think it may be more interesting to assume only one copy of each term.
