Imitating nonlocal games with encryption

Consider the problem with delegated quantum computation: A classical client wants to perform a quantum computation on a quantum server. How can the client be sure that the server is indeed a quantum device? This would require a proof of quantumness, that is, we need the server to demonstrate it can perform a task that can only be achieved with quantum resources.

One way to do this is to ask the server to solve a problem that is believed to be hard classically but is known to be easy quantumly, and one where any candidate solution is easy to verify. One such problem would be finding the prime factors of a sufficiently large number, which can be solved by the so-called Shor's algorithm much faster than any known classical algorithm.

A different way to prove quantumness is to consider a nonlocal game. In the simplest case, a nonlocal game is played between two players Alice and Bob. Each player receives a random question from a referee, and each sends back an answer. The referee then checks whether the combination of questions and answers satisfy some winning condition. If it does, then Alice and Bob wins the round; otherwise, the lose. 

During the game, Alice and Bob are not allowed to communicate: this is often enforce by placing them in distant locations, and making them reply before any potential communication can be completed. However, they are allowed to agree on a particular strategy for how to answer the questions. 

In particular, for a classical strategy, Alice and Bob are allowed to make use of a common random information. Meanwhile, for a quantum strategy for each round means Alice and Bob may share an entangled pair of quantum systems. Alice and Bob measure each system according to the questions and the outcomes determine their answers.

The standard example of a nonlocal game is the Clauser-Horne-Shimony-Holt (CHSH) game, where the questions and answers are bits: Alice receives $x$ and replies with $a$ while Bob receives $y$ and replies with $b$. The referee would check if the XOR of $a$ and $b$ is equal to the product of $x$ and $y$.  

The CHSH nonlocal game: In each round, the referee asks questions in the form of random bits $x$ and $y$ to players Alice and Bob and they reply with answer bits $a$ and $b$, respectively. The referee checks if the bits satisfy the winning condition $a \oplus b = xy$.

This is a proof of quantumness (for two quantum provers Alice and Bob) because there is a quantum strategy that is better than any classical strategy. 

To observe this, note that one of the best classical strategies that Alice and Bob can employ is to simply answer with 0 for any question. This wins 75% of the time since it only loses when $x = y =1$. It can be shown that you cannot really do better than that. Meanwhile if Alice and Bob share the entangled quantum state 

$|\psi\rangle = \cos \tfrac{\pi}{8} \left( |00\rangle - |11\rangle \right)/\sqrt{2}+ \sin \tfrac{\pi}{8} \left( |01\rangle + |10\rangle\right)/\sqrt{2}$, 

and they can measure in the computational basis when the input bit is 0 and in the Hadamard basis when the input bit is 1, then they can win with probability $\cos^{2}\tfrac{\pi}{8}\approx 85.4\%$. So when Alice and Bob are winning with sufficiently high probability, then we can be confident they are not using just classical resources.

The problem with a nonlocal game is by design it requires two or more players to make this proof. What we want is to somehow allow a single prover to imitate the strategies used when playing a nonlocal game. For example, in the CHSH game, we can have a prover play as Alice and Bob in two sequential rounds if we are able to enforce the no-communication rule. This can be be achieved by a cryptographic assumption: specifically for the earlier round that imitates Alice, we use encryption to hide the date for the second round that imitates Bob. 

For this single-prover imitation to work, we need to be able to compute functions on a message by simply performing them on the encrypted message. That is, to compute some function $f(m)$ on some message $m$, but given only the encrypted message $\mathrm{Enc}(m)$, we want that $f(\mathrm{Enc}(m)) = \mathrm{Enc}(f(m))$. If that is the case, we say that the encryption $\mathrm{Enc}$ is homomorphic.  

Compiled CHSH game: A single quantum prover can imitate both Alice and Bob in the CHSH game if the prover plays the first round as Alice and the second round as Bob. However, in order to enforce the no-communication constraint, the question and answer in the first round is encrypted: this makes the data in the first round hidden from the second round. To allow the prover to compute a proper answer while working on encrypted date, we require the encryption to have the desired homomorphic property.

By compiling a nonlocal game with Alice and Bob into a single-prover protocol where the prover plays the first round as Alice with encrypted data and the second round as Bob, it can be shown that any classical strategy cannot win more than the best classical winning probability in the original game. This is done by showing that any classical prover in the compiled game has an equivalent classical strategy in the original nonlocal game.  

By a similar token, it can be shown that any quantum prover in the compiled game can win at least as well as the best quantum winning probability. This can be shown by a quantum prover that tries to imitate the best quantum strategy in the original game as closely as possible. This would be enough to establish the quantum advantage and give us a proof of quantumness.

 However, it is much more difficult to show what the best quantum strategy can achieve, since without the encryption, it would be like Alice and Bob being allowed to communicate in the original game, which can clearly allow for better strategies for winning.

Now for certain games like the CHSH game, we can prove that as long as the encryption is secure, the quantum prover in the compiled game cannot do much better than the quantum players in the original game. This can be shown by using the notion that the quantum strategy that achieves the best winning probability in the original game has a certain "uniqueness" property, and this translates into a similar property in the compiled game. But for many other nonlocal games, it is still unknown what are the true best quantum winning probabilities.