Quantum free games

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.

Name thesis:degree_name

Master

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2024

Author dc:creator

• Zhang, Tina

Advisor dc:contributor.advisor

• Natarajan, Anand

Statement dc:rights

• In Copyright - Educational Use Permitted
• Copyright retained by author(s)

Licence dc:rights.uri

• https://rightsstatements.org/page/InC-EDU/1.0/

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/158516

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/158516