Volume 9 (2013) Article 2 pp. 31-116

The Quantum and Classical Complexity of Translationally Invariant Tiling and Hamiltonian Problems

by Daniel Gottesman and Sandy Irani

Received: July 25, 2011
Revised: October 1, 2012
Published: January 25, 2013

$ \newcommand{\QMAEXP}{{\sf{QMA_{EXP}}}} \newcommand{\BQEXP}{{\sf{BQEXP}}} \newcommand{\NEXP}{{\sf{NEXP}}} \newcommand{\EXP}{{\sf{EXP}}} $

We study the complexity of a class of problems involving satisfying constraints which remain the same under translations in one or more spatial directions. In this paper, we show hardness of a classical tiling problem on an $N \times N$ $2$-dimensional grid and a quantum problem involving finding the ground state energy of a $1$-dimensional quantum system of $N$ particles. In both cases, the only input is $N$, provided in binary. We show that the classical problem is $\NEXP$-complete and the quantum problem is $\QMAEXP$-complete. Thus, an algorithm for these problems which runs in time polynomial in $N$ (exponential in the input size) would imply that $\EXP = \NEXP$ or $\BQEXP = \QMAEXP$, respectively. Although tiling in general is already known to be $\NEXP$-complete, the usual approach is to require that either the set of tiles and their constraints or some varying boundary conditions be given as part of the input. In the problem considered here, these are fixed, constant-sized parameters of the problem. Instead, the problem instance is encoded solely in the size of the system.

A preliminary version of this paper was posted on the arXiv in 2009. An extended abstract appeared in FOCS'09.

DOI: 10.4086/toc.2013.v009a002

© 2013 Daniel Gottesman and Sandy Irani
Licensed under a Creative Commons Attribution License (CC-BY)