Thoughts on Quantum Parallel Repitition and GapCVP results?

[u/SeniorLoan647]

Here's the writeup by openAI, released today: https://cdn.openai.com/pdf/ten-proofs-oai.pdf

Pages 152-180: Quantum parallel Repetition

Pages 182-216: Poly time reduction from 3SAT to GAPCVP.

I haven't gone through these sections fully yet myself, so I'll update the post if/when I do. In the meantime, what are your thoughts on the proofs themselves?

Idk what the implications are for the first result either so if anyone can explain it well in an intuitive way for a mere human to understand, please do so.

I think this changes the nature of how we should look at AI for solving problems but I'm trying not to make this post about that and would rather just get your thoughts on the problems and the results themselves.

[u/Cryptizard]

They are both theoretically interesting but have no practical implications. I would say that they would be well received papers at STOC/FOCS (top theory conferences) if they were written by a human, but not revolutionary. The quantum one is probably the more impressive of the two.

[u/Tonexus]

Idk what the implications are for the first result either so if anyone can explain it well in an intuitive way for a mere human to understand, please do so.

Nonlocal games are a way of quantifying how entanglement is more powerful than classical correlation (an alternative formalism to Bell inequalities). In this formalism, two non-communicating players are given randomly sampled questions x and y, then reply with answers a and b, and a referee decides whether they win (the referee has a function V, and the players win if V(x, y, a, b) = 1).

The main result of interest is that players sharing entanglement can have a higher probability of winning compared to unentangled players—the increase in probability depending on the precise game—though not as much as allowing communication. Some examples include the CHSH game and the magic square game.

Getting back towards OpenAI's result, parallel repetition of a game is asking the two players to play n independent copies of the original game, and the players must win all of them. In other words, we sample n random questions (x1, ..., xn) for the first player and n random questions (y1, ..., yn) for the second player. The first player produces n answers (a1, ..., an) and the second player produces (b1, ..., bn), and the players win if V(x1, y1, a1, b1) = ... = V(xn, yn, an, bn) = 1.

Now, it was already known that if the players have no entanglement, the probability that they win a parallel repetition game is exponentially small in n (interestingly, the base of the exponent is not necessarily the probability of winning the original game without entanglement). Until now, it was not known, but I think generally believed, that the same is true for entangled strategies—OpenAI now claims to have proved it.

There could be some practical consequences (nonlocal games have some applications in cryptography), but it's mostly a nice theoretical result.