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

Understand

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 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.