pdf files of
Programme Booklet >>
and
Abstracts of all Talks >>

You will receive a hard copy of these files at the registration desk.

Sponsors

Pauli Center for Theoretical Studies

The Swiss National Science Foundation

ETH Zurich (Computer Science and Physics Department)

Quantum Science and Technology

CQT Singapore

QAP European Project

Sandia National Laboratories

Institute for Quantum Computing

id Quantique

The quantum and classical complexity of translationally invariant tiling and Hamiltonian problems

Daniel Gottesman, Perimeter Institute

joint work with Sandy Irani

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 x N) 2-dimensional grid and the problem of 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 that runs in time polynomial in N (exponential in the input size) would imply 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.