3 ms·

It’s interesting to think about, but the complexity classes are actually equal[1]. This sort of makes sense if you think of quantum computers as simulatable by

It’s interesting to think about, but the complexity classes are actually equal[1]. This sort of makes sense if you think of quantum computers as simulatable by a classical computer. [1] https://arxiv.org/abs/2001.04383 https://arxiv.org/abs/2001.04383

drdeca 3y ago
Huh? Assuming I understand your comment correctly, that is, not what that paper is showing. That paper is showing that if the verifier has polynomial time computational power, with two provers who each have unlimited computational power, and who have some shared quantum entanglement, are communicating individually with the prover, and the prover also has access to randomness and such, then there is a protocol that can allow the provers to, for any recursively enumerable language, demonstrate to the verifier, for any string, whether that string is in that language. RE is a WAY bigger class than what the verifier can compute alone. And, is also way bigger than the without-entanglement version, MIP. That paper is showing that adding quantum entanglement to the setup for MIP, allows for way more problems to be in the class.
- l33t7332273 3y ago
  >RE is a WAY bigger class than what the verifier can compute alone I always think of the RE(CE) sets as those that are possible to compute. I’m aware that RE sets are not computable, but since RE sets are those accepted by a turing machine, I still consider that set to be the “main” one when speaking informally. Maybe this is misguided
  - drdeca 3y ago
    the verifier in the MIP* setup/definition is assumed to be limited to a polynomial amount of computation.
bawolff 3y ago
That's not really what that paper is saying. The class of problems computable by a quantum computer is equal to that of a classical computer. That does not neccesarily imply anything about the relationship between BQP and P or BQP and NP.
- l33t7332273 3y ago
  You’re completely right. I somehow got my wires crossed as to what was possible to compute and the running time.

drdeca 3y ago

Huh? Assuming I understand your comment correctly, that is, not what that paper is showing. That paper is showing that if the verifier has polynomial time computational power, with two provers who each have unlimited computational power, and who have some shared quantum entanglement, are communicating individually with the prover, and the prover also has access to randomness and such, then there is a protocol that can allow the provers to, for any recursively enumerable language, demonstrate to the verifier, for any string, whether that string is in that language. RE is a WAY bigger class than what the verifier can compute alone. And, is also way bigger than the without-entanglement version, MIP. That paper is showing that adding quantum entanglement to the setup for MIP, allows for way more problems to be in the class.

l33t7332273 3y ago
>RE is a WAY bigger class than what the verifier can compute alone I always think of the RE(CE) sets as those that are possible to compute. I’m aware that RE sets are not computable, but since RE sets are those accepted by a turing machine, I still consider that set to be the “main” one when speaking informally. Maybe this is misguided
- drdeca 3y ago
  the verifier in the MIP* setup/definition is assumed to be limited to a polynomial amount of computation.

bawolff 3y ago

That's not really what that paper is saying. The class of problems computable by a quantum computer is equal to that of a classical computer. That does not neccesarily imply anything about the relationship between BQP and P or BQP and NP.

l33t7332273 3y ago
You’re completely right. I somehow got my wires crossed as to what was possible to compute and the running time.