One of the authors of this paper, Thomas Vidick, taught the Advanced Algorithms class I took at Caltech a few years ago. The dude is a genius, but the class kicked my ass. He would basically assign recently solved problems from the theory community as homework.
I'm not going to claim I understand the complexity class discussion here, but what I find most surprising is the claim that this would make the halting problem solvable. There's a fairly straightforward proof by contradiction that it's not:
https://en.wikipedia.org/wiki/Halting_problem#Proof_concept
So how would the new finding override this? Or is it just <wiggles fingers> quantum magic that's running the proof in parallel in infinite entangled multiverses or something?
Here's one intuitive way to think about what this means:
Imagine that you stumble on two infinitely powerful computers that share a bunch of entangled quantum state. Further, let's say you know how to write software for them but you need a way to check that the answers are correct. And you want to know with near certainty that your programs ran correctly, even if one of the infinitely powerful computers is evil and will use its entire intellect to convince you of something that's untrue.
Aside: this means that cryptography doesn't work---you can't use the discrete log assumption to solve this problem, you can't use collision resistant hashing, etc.
Ok, so this paper shows that, if you can figure out how to program those computers to solve the halting problem, you can then create an error detection protocol (see below) that you can check on a laptop computer and that almost perfectly (like, except with exponentially small probability) detects errors in your halting detector's execution.
You can use your laptop to ensure that your infinitely powerful, possibly evil lunatic twin Hal2^9000s aren't lying to you. Or, as BFLS91 says, "controlling a herd of supercomputers from [your iPad]" ;)
(Your error detecting protocol checker must be verified, but it's not too complicated an algorithm and we basically know how to write certified computer software for our laptops.)
(Oh, and also note that you need a perfect random number generator, and your laptop has to communicate with the supercomputers while they're executing.)
[edit for slightly more precision]
Some additional context from the always illuminating Scott Aaronson: https://www.scottaaronson.com/blog/?p=4512
Perhaps a link directly to the arxiv page would be more appropriate?
The paper: https://arxiv.org/abs/2001.04383
An oracle that doesn't always tell the truth? That seems like an odd thing for an algorithm to have to deal with.
I just came to say that the first paragraph of that article is so cringe-worthy I had to post... Terrible, argh...
But amazing result.
I'm surprised this isn't getting more attention. If this holds it would imply a lot for a wide variety of fields.
An excellent comment on the halting problem: https://news.ycombinator.com/item?id=21561031
The the linked Scott Aaronson blog and associated video are fascinating.
Would be nice to have a writeup with some details on how this disproves Connes embedding conjecture understandable for operator algebraists with little (quantum) computing background
Can anyone here provide more detail on the implications (particularly for physics) of the Connes embedding conjecture being shown to be false?
I wonder what the physics implications are they mentioned?
quantum entangled oracles which don't always tell the truth. science :'D
Here's a (relatively) concise explanation of the result for people without a background in the area:
Suppose a person comes to me, claiming some fact is true. How can I check whether they're telling the truth? I could ask them a series of questions, carefully chosen to expose any lie. Such a procedure is called an "Interactive Proof" (IP). It turns out, there is an upper limit to how 'complicated' the statement being proved can be, before I, a 'simple' verifier, can't possibly tell the difference between a true claim and a false claim. The limit is called PSPACE. Note that in order for the prover to prove such 'complicated' claims, the prover must be very 'complicated' itself - at least as complicated as the statements being proved.
How can we take things farther? Suppose that instead two people come to me, claiming some fact is true. Then, those two people are separated - they are not allowed to communicate. Then, I ask them both questions, again trying to ferret out lies. This procedure is called a "Multi-prover Interactive Proof" (MIP). Again, there is a limit to how 'complicated' the statement being proved can be before I, a 'simple' verifier, can't possibly tell the difference between a true claim and a false claim. This time, the limit is NEXP - thought to be significantly more 'complicated' than PSPACE. Again, note that the prover must be capable of very 'complicated' computations to reach this point, but the only limit based on my ability to verify the proofs is NEXP.
Now for the new result:
How can we take things further? Suppose that again two people come to me, claiming a fact is true. This time, before the two people are separated, they divvy up some entagled quantum states. Then they're separated, and not allowed to communicate. Then, I ask them both questions, again trying to ferret out lies. This procedure is called a "Quantum Multi-prover Interactive Proof" (MIP*). This time, things are different: There is (basically) no limit on how 'complicated' the statement being proved can be before I, a 'simple' verifier, would not be able to distinguish true and false claims. (Basically) The only limit on the ability of the provers to prove things to me is their ability to discover the claims, not my ability to verify those proofs. That's roughly what saying that the limit is RE is saying - there's no limit.