What exactly are Quantum XOR Games?

Question

I have done some research & found a few different papers that discuss xor games (classic & quantum). I am curious if someone could give a concise introductory explanation as to what exactly xor games are & how they are or could be used/useful in quantum computing.

Answer 1

Quantum xor games are a method of greatly simplifying the ideas behind Bell's theorem, which states that no physical theory of local hidden variables can ever reproduce all of the predictions of quantum mechanics.

Basically, when two qubits are entangled, measurements on them appear correlated even if they are vastly far apart. The question then is whether the qubits decided how they would collapse at time of entanglement (thus carrying "local hidden variables" with them) or decided how they would collapse at time of measurement (thus requiring some kind of instantaneous "spooky action at a distance"). Bell's theorem, and xor games, come down firmly on the side of the latter.

Xor games generally have the format of two people (Alice and Bob) given some random bits, and without communication outputting some other bits with the goal of making true a logical formula.

For example with the original xor game, the CHSH game, Alice is given random bit $X$ and Bob random bit $Y$. Alice then outputs a chosen bit $a$ and Bob outputs a chosen bit $b$. They want to satisfy the equation $X \cdot Y = a \oplus b$. Of course, since they cannot communicate, they can only win some of the time; they want to choose a strategy to maximize the probability of winning. The best possible classical strategy is for Alice and Bob to both always output $0$, which will result in a win 75% of the time. However if Alice and Bob share an entangled qubit pair, they can come up with a strategy to win 85% of the time! The conclusion is this disproves the existence of local hidden variables, because if the qubits contained a local hidden variable (some string of bits) then Alice and Bob could have pre-shared that same string of bits to employ in their classical strategy to also get an 85% chance of winning; since no string of bits enables them to do this, that means the entangled qubits cannot be relying on a shared string of bits (local hidden variable) and something spookier is happening. You can see an implementation of the CHSH game in Microsoft's Q# samples (with expanded explanation) here.

The best explanation of the CHSH game is from Professor Vazirani in this video. He claims something interesting (possibly rhetorically), which is that if Einstein had had access to the simplified presentation of xor games, he'd have avoided wasting the last three decades of his life searching for a hidden variable-based theory of quantum mechanics!

I have also written a blog post detailing the CHSH game here.

One application of xor games is self-testing: when running algorithms on an untrusted quantum computer, you can use xor games to verify that the computer isn't corrupted by an adversary trying to steal your secrets! This is useful in device-independent quantum cryptography.