Return to Answer

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.

But even this modification is not enough to fall into a bound error complexity class.

The problem is that we can never be completely sure about any of the properties of $|\psi\rangle$, unless we also restrict the set of possible $U$ in consideration.

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.

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. This is what is done in https://arxiv.org/abs/0810.4507.

But even this modification is not enough to fall into a bound error complexity class.

The problem is that we can never be completely sure about any of the properties of $|\psi\rangle$, unless we also restrict the set of possible $U$ in consideration.

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.

But even this modification is not enough to fall into a bound error complexity class.

The problem is that we can never be completely sure about any of the properties of $|\psi\rangle$, unless we also restrict the set of possible $U$ in consideration.

This is a different type of decision problem, it doesn't match what is usually called "bounded error complexity".

In BQP and similar classes we decide if an explicit input $x$ (that has a precise mathematical description) is in a well-defined language $L$, i.e. in some particular set of input instances.

We can give a description of $L$ that uses access to oracles, but we must be sure that oracles act like precise mathematical functions. So that a definite input $x$ leads to a definite output $y$, which then certifies if $x$ is in $L$ or not. Our task is to decide efficiently if $x$ is in $L$ or not.

For example, in Grover's algorithm the input $x$ is from a set $\{0,1,\dots,N\}$ and the output is $1$ or $0$ that we know through a quantum oracle $U_f$. The language $L$ is the preimage of $1$.

But in your case the input is the unknown oracle $U$, in essence. And we want to figure out its property, either $U|0\rangle$ is entangled or not.

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

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. This is what is done in https://arxiv.org/abs/0810.4507.

But even this modification is not enough to fall into a bound error complexity class.

The problem is that we can never be completely sure about any of the properties of $|\psi\rangle$, unless we also restrict the set of possible $U$ in consideration.