Anand Natarajan

We continue the line of work initiated by Kalai et al. (STOC '23), studying "compiled" nonlocal games played between a classical verifier and a single quantum prover, with cryptography simulating the spatial separation between the players. The central open question in this area is to understand the soundness of this compiler against quantum strategies, and apart from results for specific games, all that is known is the recent "qualitative" result of Kulpe et al. (STOC '25) showing that the success probability of a quantum prover in the compiled game is bounded by the game's quantum commuting-operator value in the limit as the cryptographic security parameter goes to infinity. In this work, we make progress towards a quantitative understanding of quantum soundness for general games, by giving a concrete framework to bound the quantum value of compiled nonlocal games. Building on the result of Kulpe et al. together with the notion of "nice" sum-of-squares certificates, introduced by Natarajan and Zhang (FOCS '23) to bound the value of the compiled CHSH game, we extend the niceness framework and construct a hierarchy of semidefinite programs that searches exclusively over nice certificates. We show that this hierarchy converges to the optimal quantum value of the game. Additionally, we present a transformation to make any degree-1 sum-of-squares certificate nice. This approach provides a systematic method to reproduce all known bounds for special classes of games together with Kulpe et al.'s bound for general games from the same framework.

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.

We construct a succinct classical argument system for QMA, the quantum analogue of NP, from generic and standard cryptographic assumptions. Previously, building on the prior work of Mahadev (FOCS '18), Bartusek et al. (CRYPTO '22) also constructed a succinct classical argument system for QMA. However, their construction relied on post-quantumly secure indistinguishability obfuscation, a very strong primitive which is not known from standard cryptographic assumptions. In contrast, the primitives we use (namely, collapsing hash functions and a mild version of quantum homomorphic encryption) are much weaker and are implied by standard assumptions such as LWE. Our protocol is constructed using a general transformation which was designed by Kalai et al. (STOC '23) as a candidate method to compile any quantum nonlocal game into an argument system. Our main technical contribution is to analyze the soundness of this transformation when it is applied to a succinct self-test for Pauli measurements on maximally entangled states, the latter of which is a key component in the proof of MIP* = RE in quantum complexity.

Nonlocal games are a foundational tool for understanding entanglement and constructing quantum protocols in settings with multiple spatially separated quantum devices. In this work, we continue the study initiated by Kalai et al. (STOC '23) of compiled nonlocal games, played between a classical verifier and a single cryptographically limited quantum device. Our main result is that the compiler proposed by Kalai et al. is sound for any two-player XOR game. A celebrated theorem of Tsirelson shows that for XOR games, the quantum value is exactly given by a semidefinite program, and we obtain our result by showing that the SDP upper bound holds for the compiled game up to a negligible error arising from the compilation. This answers a question raised by Natarajan and Zhang (FOCS '23), who showed soundness for the specific case of the CHSH game. Using our techniques, we obtain several additional results, including (1) tight bounds on the compiled value of parallel-repeated XOR games, (2) operator self-testing statements for any compiled XOR game, and (3) a ``nice" sum-of-squares certificate for any XOR game, from which operator rigidity is manifest.

Abstract Boris Tsirelson in 1993 implicitly posed "Tsirelson's Problem", a question about the possible equivalence between two different ways of modeling locality, and hence entanglement, in quantum mechanics. Tsirelson's Problem gained prominence through work of Fritz, Navascues et al., and Ozawa a decade ago that establishes its equivalence to the famous "Connes' Embedding Problem" in the theory of von Neumann algebras. Recently we gave a negative answer to Tsirelson's Problem and Connes' Embedding Problem by proving a seemingly stronger result in quantum complexity theory. This result is summarized in the equation MIP* = RE between two complexity classes. In the talk I will present and motivate Tsirelson's problem, and outline its connection to Connes' Embedding Problem. I will then explain the connection to quantum complexity theory and show how ideas developed in the past two decades in the study of classical and quantum interactive proof systems led to the characterization (which I will explain) MIP* = RE and the negative resolution of Tsirelson's Problem. Based on joint work with Ji, Natarajan, Wright and Yuen available at arXiv:2001.04383.

Commuting Hamiltonians lie at the boundary between classical constraint satisfaction and quantum many-body physics, exhibiting rich quantum structure while remaining more tractable than general noncommuting models. In contrast, physical Hamiltonians are rarely exactly commuting, which naturally motivates the study of \emph{almost commuting} Hamiltonians. Despite their relevance, the implications of approximate commutation are only poorly understood. In this work, we show how to efficiently approximate any almost commuting $2$-local qubit Hamiltonian by a commuting one: we give a locality-preserving ``rounding technique'' that maps any $2$-local Hamiltonian $H=\sum_{i=1}^m h_i$ with $\|[h_i,h_j]\| \leq \eps$ to a nearby Hamiltonian $\hat{H}$ whose terms pair-wise commute, and which is within overall distance $\|H-\hat{H}\| = O(m\,\eps^{1/3})$. As a consequence, we show that $\delta$-approximations to the ground energy for $\eps$-almost commuting $2$-local qubit Hamiltonians lie in $\mathsf{NP}$ when $\delta \gg m\eps^{1/3}$, extending the classical containment well beyond the commuting setting. Finally, we present two applications of our rounding framework: Gibbs sampling and fast Hamiltonian simulation for almost commuting systems.