Is this just another result along the lines of “If we had quantum computers it would be awesome”?
No, such complexity results are of supreme importance. So are the constructions used to get such reductions. But who said anything about quantum computers? Anyway quantum computers do not magically solve any halting problem, unless there is something I’m missing.
References are made to entangled quantum provers. Are these not some sort of quantum computer?
Correct, this result concerns multiple quantum interactive provers. However, an interactive prover is not a (classical or quantum) “computer”. It is not computationally bounded in any way, rather you, the classical polynomial-time verifier are.
Could anyone dumb this down as to what the big deal is ? There was a link to a CNBC 15 minute piece on quantum computing in the link which was cool , so I assume this has either something to do with quantum computing or a wizard has figured out how to cast a fireball.
To add to this question: do we have (or might we soon have) the technology to build a quantum prover or whatever else is required to make practical use of this result? I don’t mean to diminish purely theoretical stuff, just curious about the practical implications.
The interactive prover is like a magic quantum wizard, but you are not and it still has to be able to formally convince you that a given Turing machine halts or not in a way that you can verify.
You can’t even theoretically build one, that’s the point, it is by definition a magic black box.
This by no means means that the constructions that appear in the paper have no practical uses in quantum optics or whatever (they have practical mathematical implications), but maybe some of the physicists reading this board have more to say about that.
Ok, so I think I can now dumb this down a bit.
The just of it is that even if you know the answer to a difficult problem, it is not always easy to prove that you have the correct answer. For example “does some program halt?”.
This paper says that 2 god like entities who can answer such questions that are unanswerable for non god like entities, can prove (to said non god like entities) that they have the correct answer, by playing some sort of interactive game.
Awesome thanks, my wizard reference was supposed to be along the the lines of ‘any sufficiently advanced technology will look like magic’ as this all was way above my head and looked like magic to me, I had no idea the point was how to prove something incomprehensible to someone who would not understand it.