Computational Complexity of Translationally-Invariant Systems
| Speaker: | Daniel Gottesman |
|---|---|
| Affiliation: | Perimeter Institute |
| Room: | Mathematics & Computer Building (MC) 5158 |
Abstract:
In general, it is a computationally hard problem to determine whether a two-dimensional grid can be tiled using some set of rules on what kinds of tiles can be adjacent. A related problem, hard for a quantum complexity class, is to determine the lowest energy state of a system with interactions only for particles adjacent along a line. Of course, there are also specific systems of this type which are easy to solve. What are the key distinguishing properties between the hard systems and the easy systems? One might expect that symmetry should play a role, with very symmetric systems being easy. However, we show that even with a great deal of symmetry - translational invariance - tiling problems and spin systems remain hard to solve in general.
This is joint work with Sandy Irani.