It’s a highly technical problem that doesn’t have much practical use. Essentially it says that a weak (polynomial time) classical computer (called the “verifier”) with the ability to query (polynomial number of times) a small number of all-powerful computers (called the “provers”) with unknown/unbounded computing power is able to be convinced that the prover is indeed all powerful (convinces the verifier that it knows the answer to some problem that is known to be difficult). These specific provers can not communicate with each other (collude) but can share some entangled bits (the quantum part). The result here is (basically) that the verifier can be convinced that the prover knows the answer to the halting problem.

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.

This is where I always wish they demonstrated some of the mathematical notation with some variant of quantum Lisp (even if it couldn't be executed in any practical way). The Regetti guys are always around here, so maybe one of them can chime in.

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.

I don't know what it means, but there was a blog post posted about this paper here yesterday: https://news.ycombinator.com/item?id=22077591