Comment by isaacg | Hacker News Reader

Comment by isaacg | Hacker News Reader

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.

> series of questions, carefully chosen to expose any lie

I don't understand, how this is possible. Is it assumed that every lie is necessarily a Bernoulli trial with a known probability? Because if not, what prevents a single oracle from telling consistently false story, taking into account all lies he told you before?

The solution is very careful construction of the questions. A working protocol puts a low upper bound on the prover’s probability of successful cheating.

"Very careful" doesn't really explain much. If lie is not necessarily probabilistic (so we cannot figure it our based on frequency of some contradictory answers), and if we need an oracle at all (that is, there is some piece of knowledge we cannot possibly verify ourselves), why cannot oracle just always lie about that piece of knowledge and take this lie into consideration in all the other answers, to make story consistent?

I'm pretty sure there must be some additional constraints, otherwise I don't see how you could possibly detect a lie that you cannot verify yourself with a single oracle.

Here's an example of such a protocol, for the problem of graph (non)isomorphism.

Verifier: Here are two graphs, A and B. Are they isomorphic? (Same except for relabeling vertices)

Prover: No, they're different.

Verifier: Here's one of the graphs, with the vertices relabeled uniformly randomly. Which one was it?

Prover: It was A.

(Repeat 100 times)

Verifier: Ok, you got them all right. I believe you.

Here, we've forced the prover into a situation where if it's lying, and graphs A and B are in fact isomorphic, it can't know which graph we started with, before permuting. As a result, it can only guess which graph we started with and hope to get lucky, and we'll catch it with very high probability.

In contrast, if the verifier was telling the truth, it could figure out which graph we started with, and always answer correctly.

Here it is impossible for the prover to make its lie, "the graphs are not isomorphic" consistent with its later inability to tell them apart, after random permutation.

This kind of 'catching in a lie' is how interactive proofs typically work.

The first two intuitively make sense to me. But I don't get why the intuition behind why the quantum version behaves the way it does...

Unintuitivity is the defining feature of quantum mechanics.

perhaps i am talking out of my ass here, but structured like this, it feels like there is a violation of gödel’s incompleteness theorem somewhere..?

No, the key point is that these systems are still polynomial.

You cannot ask a question that would require a non-polynomial computation to provide an answer and expect it to be answered correctly.

Most importantly, recursive enumerable already means semidecidable. (Because it consists of primitive recursive functions, which are bounded.) Which means by Godel's theorems it is stronger than Peano arithmetics. (See Tennenbaum's theorem, Presburger arithmetics is fine.)

In what real-world situation could you be convinced that supposedly-two provers really actually can't communicate?

Reply on news.ycombinator.com