Quantum free games

Abstract

The complexity of free games with two or more classical players was essentially settled by Aaronson, Impagliazzo, and Moshkovitz [AIM14]. In the quantum world, there are two complexity classes that can be considered quantum analogues of classical free games: (1) AM⇤, the multiprover interactive proof class corresponding to free games with entangled players, and, somewhat less obviously, (2) BellQMA(2), the class of quantum Merlin-Arthur proof systems with two unentangled Merlins, whose proof states are separately measured by Arthur. In this work, we make significant progress towards a tight characterization of both of these classes. 1. We show a BellQMA(2) protocol for 3SAT on n variables, where the total amount of communication is Õ(√n). This answers an open question of Chen and Drucker [CD10] and also shows, conditional on ETH, that the algorithm of Brandao, Christandl and Yard [BCY10] for optimizing ˜ over separable states is tight up to logarithmic factors. 2. We show that AM*[ⁿprovers = 2, q = O(1), a = poly log(n)] = RE, i.e. that free entangled games with constant-sized questions are as powerful as general entangled games. (In contrast, [AIM14] shows that classical free games are much weaker than general classical games.) We show this using a question “hyper-compression” theorem that iteratively applies the introspection technique of Ji et al. [JNV⁺20]. Our result is a significant improvement over the headline result of Ji et al., whose MIP⇤ protocol for the halting problem has poly(n)-sized questions and answers. 3. By the same techniques, we obtain a zero-gap AM* protocol for a P2 complete language with constant-size questions and almost logarithmically (O(log n · log* n)) large answers, improving on the headline result of Mousavi, Nezhadi and Yuen [MNY21]. 4. Using a connection to the nonuniform complexity of the halting problem we show that any MIP* protocol for RE requires W(log n) bits of communication. It follows that our results in item 3 are optimal up to an O(log* n) factor, and that the gapless compression theorems of [MNY21] are asymptotically optimal. We conjecture that these bounds can be saturated in the gapped case as well.