In complexity theory, gap-preserving reductions play a crucial role in studying hardness of approximation and in analyzing the relative complexity of multiprover interactive proof systems. In the quantum setting, multiprover interactive proof systems with entangled provers correspond to gapped promise problems for nonlocal games, and the recent result MIP*=RE [1] shows that these are in general undecidable. However, the relative complexity of problems within MIP* is still not well-understood, as establishing gap-preserving reductions in the quantum setting presents new challenges. In this paper, we introduce a framework to study such reductions and use it to establish MIP*-completeness of the gapped promise problem for the natural class of independent set games. In such a game, the goal is to determine whether a given graph contains an independent set of a specified size. We construct families of independent set games with constant question size for which the gapped promise problem is undecidable. In contrast, the same problem is decidable in polynomial time in the classical setting. To carry out our reduction, we establish a new stability theorem, which could be of independent interest, allowing us to perturb families of aThis is a striking phenomenlmost PVMs to genuine PVMs.

Quantum thermodynamics is a research field that aims at fleshing out the ultimate limits of thermodynamic processes in the deep quantum regime. A complete picture of thermodynamical processes naturally allows for auxiliary systems dubbed 'catalysts', i.e., any physical systems facilitating state transformations while remaining essentially intact in their state, like an auxiliary system, a clock, or an actual catalyst. In this work, we present a comprehensive analysis of the power and limitation of such thermal catalysis. Specifically, we provide a family of optimal catalysts that can be returned with minimal trace distance error after facilitating a state transformation process. To incorporate the genuine physical role of a catalyst, we identify very significant restrictions on arbitrary state transformations under dimension or mean energy bounds, using methods of convex relaxations. We discuss the implication of these findings on possible thermodynamic state transformations in the quantum regime.