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

Abstract

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. Thus, an algorithm for these problems which runs in time polynomial in N (exponential in the input size) would imply that EXP = NEXP or BQEXP = QMA_EXP, 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.

67 pages, approximately 6 gazillion figures. v2 has new results proving hardness for reflection-invariant quantum and classical systems and a discussion of the infinite quantum chain

References in corpus (6)

• The power of quantum systems on a line
• N-representability is QMA-complete
• Hamiltonian Quantum Cellular Automata in 1D
• Ground State Entanglement in One Dimensional Translationally Invariant Quantum Systems
• The Computational Power of Symmetric Hamiltonians
• A single-shot measurement of the energy of product states in a translation invariant spin chain can replace any quantum computation

Cited by in corpus (12)

• Undecidability of the Spectral Gap (short version)
• Quantum computing and the entanglement frontier
• Quantum Hamiltonian Complexity
• Universal Quantum Hamiltonians
• The Quantum PCP Conjecture
• Condensed Matter Applications of Entanglement Theory
• Universal Hamiltonians for Exponentially Long Simulation
• A multiprover interactive proof system for the local Hamiltonian problem
• Quantum Lovász Local Lemma: Shearer's Bound is Tight
• The Complexity of Approximating Critical Points of Quantum Phase Transitions
• On polynomially many queries to NP or QMA oracles
• Gapped and gapless phases of frustration-free spin-1/2 chains