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

DOI10.1109/FOCS.2009.22zbMath1292.68067MaRDI QIDQ5171167

Sandy Irani, Daniel Gottesman

Publication date: 25 July 2014

Published in: 2009 50th Annual IEEE Symposium on Foundations of Computer Science (Search for Journal in Brave)

Mathematics Subject Classification ID

Quantum computation (81P68) Quantum algorithms and complexity in the theory of computing (68Q12)

Related Items (7)

Two-dimensional local Hamiltonian problem with area laws is \textsf{QMA}-complete ⋮ Undecidability of the Spectral Gap ⋮ The commuting local Hamiltonian problem on locally expanding graphs is approximable in \(\mathsf{NP}\) ⋮ Product-state approximations to quantum states ⋮ Exponential decay of correlations implies area law ⋮ Translationally invariant universal classical Hamiltonians ⋮ Gapped and gapless phases of frustration-free spin-12 chains

This page was built for publication: The Quantum and Classical Complexity of Translationally Invariant Tiling and Hamiltonian Problems