Complexity 2

Abstract: 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 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 almost PVMs to genuine PVMs.

Abstract: In 2020, a landmark result by Ji, Natarajan, Vidick, Wright, and Yuen showed that MIP∗, the class of languages that can be decided by a classical verifier interacting with multiple computationally unbounded provers sharing entanglement in the tensor product model, is equal to RE. We show that the class MIPco, a complexity class defined similarly to MIP∗ except with provers sharing the commuting operator model of entanglement instead, is equal to the class coRE. This shows that giving the provers two different models of entanglement leads to two completely different computational powers for interactive proof systems. Our proof builds upon the compression theorem used in the proof of MIP∗ = RE, and we use the tracially embeddable strategies framework to show that the same compression procedure in MIP∗ = RE also has the same desired property in the commuting operator setting. We also give a more streamlined proof of the compression theorem for non-local games by incorporating the synchronous framework used by Mousavi et al. [STOC 2022], as well as the improved Pauli basis test introduced by de la Salle [ArXiv:2204.07084]. We introduce a new equivalence condition for RE/coRE-complete problems, which we call the weakly compressible condition. We show that both MIP∗ and MIPco satisfy this condition through the compression theorem, and thereby establish that the uncomputability for MIP∗ and MIPco can be proved under a unified framework (despite these two complexity classes being different). Notably, this approach also gives an alternative proof of the MIP∗ = RE theorem, which does not rely on the preservation of the entanglement bound. In addition to non-local games, this new condition could also potentially be applicable to other decision problems.

Abstract: We introduce a basis-restricted variant of the Quantum-k-Sat problem, in which each term in the input Hamiltonian is required to be diagonal in either the standard or Hadamard basis. Our main result is that the Quantum-6-Sat problem with this basis restriction is already QMA1-complete, defined with respect to a natural gateset. Our construction is based on the Feynman-Kitaev circuit-to-Hamiltonian construction, with a modified clock encoding that interleaves two clocks in the standard and Hadamard bases. In light of the central role played by CSS codes and the uncertainty principle in the proof of the NLTS theorem of Anshu, Breuckmann, and Nirkhe (STOC ’23), we hope that the CSS-like structure of our Hamiltonians will make them useful for progress towards a quantum PCP theorem.

Abstract: A long-standing open problem in quantum complexity theory is whether QMA has perfect completeness, i.e. whether any QMA verifier can be made to have completeness $c=1$. Previous constructions have yielded a completeness parameter exponentially close to 1. We improve this to doubly-exponentially close to 1. Additionally, we show that QMA has perfect completeness if one allows the verifier an infinite-dimensional (witness) space. We show that this can be achieved using a gate set which is such that the ability to use an infinite-dimensional space does not increase the computational power of QMA. We also show that when using a finite-dimensional space of polynomially many qubits, a completeness doubly-exponentially close to 1 is optimal among black-box constructions. We show that the soundness can at most be made exponentially small using black-box reductions.