Is there an updated version? It would be nice to see the same rigour applied to SaaS.

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.