Complexity 3

Abstract: We show that it is undecidable to determine whether the commuting operator value of a nonlocal game is strictly greater than 1/2. As a corollary, there is a boolean constraint system (BCS) nonlocal game for which the value of the Navascués, Pironio, and Acín (NPA) hierarchy does not attain the commuting operator value at any finite level. Our contribution involves establishing a computable mapping from Turing machines to BCS nonlocal games in which the halting property of the machine is encoded as a decision problem for the commuting operator value of the game. Our techniques are algebraic and distinct from those used to establish MIP*=RE. As a first step, we construct a mapping from Turing machines to elements of the tensor product of free algebras, showing that deciding positivity of those elements is coRE-hard. As a second step, we extend this mapping to further realize these elements as game polynomials for BCS games.

Abstract: We introduce the \emph{magic hierarchy}, a quantum circuit model that alternates between arbitrary-sized Clifford circuits and constant-depth circuits with two-qubit gates ($\textsf{QNC}^0$). This model unifies existing circuit models, such as $\QACZF$ and models with adaptive intermediate measurements. Despite its generality, we are able to prove nontrivial lower bounds. We prove new lower bounds in the first level of the hierarchy, showing that certain explicit quantum states cannot be approximately prepared by circuits consisting of a Clifford circuit followed by $\textsf{QNC}^0$. These states include ground states of some topologically ordered Hamiltonians and nonstabilizer quantum codes. Our techniques exploit the rigid structure of stabilizer codes and introduce an infectiousness property: if even a single state in a high distance code can be approximately prepared by one of these circuits, then the entire subspace must lie close to a perturbed stabilizer code. We also show that proving state preparation lower bounds beyond a certain level of the hierarchy would imply \emph{classical} circuit lower bounds beyond the reach of current techniques in complexity theory. More broadly, our techniques go beyond lightcone-based methods and highlight how the magic hierarchy provides a natural framework for connecting circuit complexity, condensed matter, and Hamiltonian complexity.

Abstract: Haar-random unitaries are fundamental mathematical tools for understanding quantum many-body dynamics, yet they fail to obey basic physical constraints imposed by Hamiltonians. In this work, we explore how to reconcile random unitary models with physical constraints imposed by Hamiltonians, addressing the central question: Can we efficiently generate random unitaries while obeying Hamiltonian constraints? First, we consider the role of energy conservation in the setting where the Hamiltonian $H$ is completely known. There, we show that energy-conserving pseudorandom unitaries (PRUs) exist for random local commuting Hamiltonians, assuming quantum-secure one-way functions exist. However, we also prove that energy-conserving PRUs do not exist for some local translation-invariant Hamiltonians, even in one-dimensional systems. Furthermore, we show that determining whether energy-conserving PRUs exist for a family of Hamiltonians is undecidable. Second, we consider Hamiltonian time dynamics itself when there is incomplete knowledge of $H$. In this setting, we prove that random unitaries $e^{-iHt}$ generated from any ensemble of constant-local Hamiltonians $H$ cannot form approximate unitary designs or PRUs. This barrier vanishes when we relax locality: we construct an ensemble of polylog-local Hamiltonians $H$ that generates short-time dynamics which form both a unitary design and a PRU. Our results reveal fundamental computational barriers emerging from energy conservation constraints, highlighting the tension between common models of ergodicity and the structure of physical dynamics.