## November 13, Fall Quarter 2009: Thoery Seminar

### 1:00pm in 1423 Bren Hall

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

## Sandy Irani, UC Irvine

## Joint work with Daniel Gottesman

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 (NxN) 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, to our knowledge, all
previous reductions 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.