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

Recent results have shown that the problem of computing ground energies for one-dimensional quantum systems is likely to be computationally difficult in general, even for a quantum computer. These results establish hardness by showing that the solution to a 1D ground energy problem can encode the solution to an arbitrary problem in the class quantum NP. The particular Hamiltonians that result from these reductions, however, are highly non-physical in that each local term depends on its position in the one-dimensional chain. By contrast, many systems of physical interest are translationally-invariant. In this talk, we will show that computing the ground energy of translationally-invariant quantum systems is likely to be computationally intractable as well, even for quantum computers. The classical counterpart to the quantum ground energy problem is a tiling problem which has been studied in the computer science literature. Hardness results were known for tiling but not in the translationally-invariant case. We establish the hardness of classical two-dimensional translationally-invariant tiling. Joint work with Daniel Gottesman