3 ms·

One thing I've always found fascinating is the relationship between quantum computing and complexity classes. With the promise of quantum computers solving cert

One thing I've always found fascinating is the relationship between quantum computing and complexity classes. With the promise of quantum computers solving certain problems exponentially faster, it'll be interesting to see how they fit into our established P vs. NP paradigm. On a side note, the term "limits of knowledge" in the title feels a bit hyperbolic. I always appreciate how Quanta conveys the intricacies of deeply technical topics to a wider audience.

l33t7332273 3y ago
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.
bawolff 3y ago
> With the promise of quantum computers solving certain problems exponentially faster, it'll be interesting to see how they fit into our established P vs. NP paradigm. Its been studied for a while now. One of the most interesting things, is there may be problems in BQP that are not in NP.
- canvascritic 3y ago
  Yes indeed. it's intriguing to consider problems in BQP that may not fall into NP. this opens up a world of possibilities and challenges our current understanding of computational complexity. It suggests there are problems solvable by quantum computers that classical ones can't even verify the results of. This could lead to fascinating developments in fields like cryptography, where solutions could be found but not easily checked. on the other, it raises questions about the practicality of quantum computing. if we can't verify a solution, how do we trust it? Maybe we need to rethink our definitions of 'solving' and 'verifying'. after all, these concepts were developed with classical computing in mind. But maybe this this is just a limitation or topological property of our current theoretical framework? Like we're trying to fit quantum computing into a model that just isn't equipped to handle it. either way, it feels like we are on the cusp of a paradigm shift. Pretty exciting Anyway interested to hear more thoughts on this
  - heavenlyblue 3y ago
    You can verify solutions given by quantum computers
    - bawolff 3y ago
      I don't think that is known to be true (in polynomial time) for all problems solvable by a quantum computer (e.g. Fourier Sampling)

l33t7332273 3y ago

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.

bawolff 3y ago

> With the promise of quantum computers solving certain problems exponentially faster, it'll be interesting to see how they fit into our established P vs. NP paradigm. Its been studied for a while now. One of the most interesting things, is there may be problems in BQP that are not in NP.

canvascritic 3y ago
Yes indeed. it's intriguing to consider problems in BQP that may not fall into NP. this opens up a world of possibilities and challenges our current understanding of computational complexity. It suggests there are problems solvable by quantum computers that classical ones can't even verify the results of. This could lead to fascinating developments in fields like cryptography, where solutions could be found but not easily checked. on the other, it raises questions about the practicality of quantum computing. if we can't verify a solution, how do we trust it? Maybe we need to rethink our definitions of 'solving' and 'verifying'. after all, these concepts were developed with classical computing in mind. But maybe this this is just a limitation or topological property of our current theoretical framework? Like we're trying to fit quantum computing into a model that just isn't equipped to handle it. either way, it feels like we are on the cusp of a paradigm shift. Pretty exciting Anyway interested to hear more thoughts on this
- heavenlyblue 3y ago
  You can verify solutions given by quantum computers
  - bawolff 3y ago
    I don't think that is known to be true (in polynomial time) for all problems solvable by a quantum computer (e.g. Fourier Sampling)