> Yet another reason to be excited about this result—one that somehow hadn’t occurred to me—is that, as far as I know, it’s the first-ever fully convincing example of a non-relativizing computability result.
This is one of the three known barriers any proof of P vs NP must overcome. Not saying any of this applies to P vs NP but the proof technique demonstrated is important for such a proof.
The result is more interesting with some context though. One of the biggest discoveries of the 21st century is that PSPACE=IP. That’s where a single all powerful prover can convince a weak verifier of any solution in PSPACE (an extension of P that we believe to be more powerful than P). Then more recently we found MIP=NEXP which is a bunch of classic all powerful provers (with no collusion) can convince a single weak verifier of any problem in NEXP (which is like NP but with much larger proof sizes, thought to be more powerful than NP). The surprising fact is that multiple all-powerful provers can convince a verifier of harder problems. Intuitively this doesn’t make sense because we know each provers are all powerful and are permitted to do anything, even physically impossible tasks, so the fact that a single prover cannot convince a verifier of any problems harder than PSPACE is surprising. More surprising is that multiple all powerful provers can somehow prove harder problems when it feels like we’re not adding any extra power (they’re already “all powerful”).
So in that context we find the also surprising fact that if we weaken the “no collusion” requirement to “only quantum entanglement” and suddenly they can solve the halting problem (but still no more!).
This line of proving both upper and lower bounds about complexity classes is exactly what we want to see in the P vs NP world (which is in many ways less “powerful” of classes but more “practical”). But we don’t even know if P ?= NEXP.
I skimmed the PDF, and it's more than a tad heavier than my usual fodder.
What I think I understood from the document, keeping in mind that given enough time a complete Turing Machine by definition should be able to emulate anything a quantum computer can accomplish, is that a quantum computer should be able to efficiently identify whether a problem run on a classical computer will exit without achieving a complete result. Not that you'll actually get to the result itself, but whether you should expect to be able to, given enough time and compute power.
Because of the density of the paper, maybe I only picked up on a tiny piece of the puzzle. And even then I probably botched it.
