Theory of Computing
-------------------
Title : The Quantum and Classical Complexity of Translationally Invariant Tiling and Hamiltonian Problems
Authors : Daniel Gottesman and Sandy Irani
Volume : 9
Number : 2
Pages : 31-116
URL : https://theoryofcomputing.org/articles/v009a002
Abstract
--------
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 QMA_EXP-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 = QMA_EXP, 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.