IntroductionProblems and ResultsHardness of TILINGThe Quantum CaseVariants of TILING and 1-DIM TIHConclusionReferencesThe Quantum and Classical Complexity of Translationally Invariant Tiling andHamiltonian ProblemsDaniel GottesmanPerimeter Institute for Theoretical PhysicsWaterloo, Ontario, [email protected] IraniComputer Science DepartmentUniversity of California, IrvineIrvine, CA, [email protected]— We study the complexity of a class of problemsinvolving satisfying constraints which remain the same undertranslations in one or more spatial directions. In this paper, we showhardness of a classical tiling problem on an N × N 2-dimensionalgrid and a quantum problem involving finding the ground stateenergy of a 1-dimensional quantum system of N particles. In bothcases, the only input is N, provided in binary. We show that theclassical problem is NEXP-complete and the quantum problem isQMAEXP-complete. Thus, an algorithm for these problems whichruns in time polynomial in N (exponential in the input size) wouldimply 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 setof tiles and their constraints or some varying boundary conditionsbe given as part of the input. In the problem considered here, theseare fixed, constant-sized parameters of the problem. Instead, theproblem instance is encoded solely in the size of the system.1. INTRODUCTIONOne perennial difficulty with practical applications ofhardness results is that the practically interesting instancesof a hard language may not themselves form a hard class.One approach to solving this problem is the difficult theoryof average-case complexity [14], [2], in which one can showthat “typical” cases of some language are hard. In this paperwe take a different approach. In many cases, practicallyinteresting instances possess some shared property, such asa symmetry, that distinguish them from the general instanceand might, in principle, make those instances easier. We willstudy such an example and show that, even in a systempossessing a great deal of symmetry, it is still possible toprove a hardness result.Specifically, we consider the related problems of deter-mining whether there is a possible tiling of an r-dimensionalgrid with some fixed set of classical tiles and of finding thelowest energy state (or ground state) of a quantum systeminvolving interactions only between neighboring particleson an r-dimensional grid. The ground state energy of asystem is considered one of the basic properties of a physicalsystem, and over the last few decades, physicists havedeveloped a number of heuristics that have been successfulin finding the ground state energy in many special cases. Onthe other hand, in earlier work [1], we have shown that in themost general case, even in a 1-dimensional quantum system,finding the ground state is a computationally difficult prob-lem (modulo the usual complexity-theoretic assumptions).However, the construction presented in [1] involves a systemwhich is completely unnatural from a physical point of view.The most interesting physical systems frequently possess anadditional symmetry: translational invariance. In this paper,we will show that even a 1-dimensional translationally-invariant system can be hard.One interesting feature of our proof which may havemore general applicability is that the only free parameterfor the language we consider is the size of the system.This is frequently the case for interesting systems: thereis a basic set of rules of constant size, and we wish tostudy the effect of those rules when the system to which therules apply becomes large. In practice, many such systemsseem difficult to solve, but it is hard to see how to provea complexity-theoretic hardness result, since that requiresreducing a general problem in some complexity class tothe language under consideration, and there doesn’t seemto be room in this language to fit all the needed instances.Usually, this difficulty is circumvented by modifying theproblem slightly, to add additional parameters in whichwe can encode the description of the instance we wish tosimulate.To illustrate, let us present the classical tiling problem westudy in this paper: We are given a set of square tiles whichcome in a variety of colors. The area to be tiled is a squarearea whose size is an integer multiple of the length of atile. We are given horizontal constraints indicating whichpairs of colors can be placed next to each other in thehorizontal direction and another set of constraints in thevertical direction. We specify a particular color which mustgo in the four corners of the grid. The description of thetile colors, placement constraints and boundary conditionsare fixed for all inputs of the problems. The input is just anumber N written in binary and we wish to know whetheran N × N grid can be properly tiled given these constraints.We show that this problem is NEXP-complete. Note thatthe input in this case is size log N, so an algorithm to solveour tiling problem that runs in time polynomial in N wouldimply that NEXP = EXP. While it is possible that P 6= NPand yet NEXP = EXP, this seems unlikely to be the case.This version of tiling is equivalent to the more commonWang Tiles [21] in that any set of tiles can be transformedinto a set of Wang Tiles (and vice versa) such that thereis a one-to-one correspondence between valid tilings on anN ×N grid. For an infinite grid, the problem is undecidable.Intuitively, it makes sense that it is also hard (for somesets of tiles) for a finite grid, since there are exponentiallymany possible tilings, and it is impossible to tell locallywhether a given partial tiling can be extended indefinitely.Indeed, there are prior results showing that related tilingproblems are NEXP-complete, but to our knowledge, allprevious reductions require that either the set of tiles andtheir constraints or some varying boundary conditions begiven as part of the input [7], [15], [5]. For instance, onemay specify the placement of some number of tiles and askwhether it is possible to extend that partial tiling to a tiling ofthe full square. Even though that problem had been provenhard, the more natural problem of whether it is possible toefficiently find a tiling of the empty grid remained open.Many NEXP-complete problems are succinct versions offamiliar combinatorial