  The complexity of free games with two or more classical players was
essentially settled by Aaronson, Impagliazzo, and Moshkovitz (CCC'14). 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
$\tilde{O}(\sqrt{n})$. This answers an open question of Chen and Drucker (2010)
and also shows, conditional on ETH, that the algorithm of Brand\~{a}o,
Christandl and Yard (STOC'11) is tight up to logarithmic factors. 2. We show
that $\mathsf{AM}^*[n_{\text{provers}} = 2, q = O(1), a =\mathrm{poly}\log(n)]
= \mathsf{RE}$, i.e. that free entangled games with constant-sized questions
are as powerful as general entangled games. Our result is a significant
improvement over the headline result of Ji et al. (2020), whose MIP* protocol
for the halting problem has $\mathrm{poly}(n)$-sized questions and answers. 3.
We obtain a zero-gap AM* protocol for a $\Pi_2$ complete language with
constant-size questions and almost logarithmically large answers, improving on
the headline result of Mousavi, Nezhadi and Yuen (STOC'22). 4. Using a
connection to the nonuniform complexity of the halting problem we show that any
MIP* protocol for RE requires $\Omega(\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 MNY'22 are asymptotically optimal.
