11
$\begingroup$

I have been looking around for an answer to this question but can't really come up with anything. Given some oracle, $U$, that maps $| 0 \rangle$ to $| \psi \rangle$, is there some algorithm that determines whether $| \psi \rangle$ is entangled or separable?

I think there must be an algorithm for this, but is it in BQP? ($O(poly(N))$ where $N$ is the number of qubits), or is it hard?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ That's a very good question. One way to upperbound the query complexity is to do tomography of $|\psi\rangle$ and then use some classical method. This will be obviously exponential in $N$. There must be much better methods of doing it, though. $\endgroup$
    – Mateus Araújo
    Commented Mar 29, 2023 at 8:52
  • 4
    $\begingroup$ arXiv:1308.5788 studies various forms of this problem and may be relevant. $\endgroup$
    – John Watrous
    Commented Mar 29, 2023 at 12:47

2 Answers 2

Reset to default
7
$\begingroup$

At least when the state that you're testing is a mixed state (rather than known to be a pure state), there's been quite a bit of work on this. In 2003, Gurvits showed that the problem is NP hard. There's a more recent result that strengthens the statement. It perhaps doesn't directly answer your question about the quantum complexity, especially as these start from a matrix description of the state rather than just a copy of the state, but is certainly suggestive.

In practice, there are algorithms that work pretty well, such as this one.

You might also like to check out the body of work that Lawrence Ioannou produced during his PhD. It's available on the arxiv.

Improve this answer
$\endgroup$
3
$\begingroup$

This question requires a careful modification, so that one would be able to speak about the complexity of a solution.

Suppose you have an algorithm that guaranties to run in time $<f(n)$, i.e. makes no more than $f(n)$ queries to the oracle $U$. And it's required it should output an answer with the error probability no more than $1/3$.

It doesn't matter how big $f(n)$ is, there is always a state $|\psi\rangle$ which is very close to the boundary of the set of entangled states. For such a state your algorithm won't be able to decide with the error less than 1/3.

In other words, the time bound $f(n)$ can't be independent of $|\psi\rangle$.

A natural modification would be to consider a weak membership problem. That is, if $|\psi\rangle$ is within the Euclidean distance $\beta > 0$ from the boundary of the set of entangled states. See e.g. https://arxiv.org/abs/0810.4507.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ I don't see the problem with the weak membership formulation. We can do tomography on $|\psi\rangle$, so we know that with probability $p$ it is within $\epsilon$ of the reconstructed state. We then apply a deterministic method to the reconstructed state, and then we can decided whether it is within $\beta$ of the boundary of the separable states. $\endgroup$
    – Mateus Araújo
    Commented Mar 29, 2023 at 12:49
  • $\begingroup$ Right, we can simply discard failed tomography cases, if their probability is small. $\endgroup$
    – Danylo Y
    Commented Mar 29, 2023 at 13:02
  • $\begingroup$ how is "run time" defined here? In terms of the number of states consumed, or something else? Of do you assume you already have a classical description of the quantum state, and then you just mean computational time required to determine separability from the classical description? $\endgroup$
    – glS ♦
    Commented Mar 29, 2023 at 13:34
  • $\begingroup$ @glS I assume we want to minimize the number of queries to the oracle $U$. But apparently the complexity of a classical part is also important, since we don't know how to solve it efficiently given a classical description (for mixed states). $\endgroup$
    – Danylo Y
    Commented Mar 29, 2023 at 13:39
  • $\begingroup$ Apparently OP is asking about the query complexity for pure states only. They should clarify. $\endgroup$
    – Mateus Araújo
    Commented Mar 29, 2023 at 14:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.