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

DOI10.1109/FOCS.2009.22MaRDI QIDQ5171167zbMATH OpenFDO

Authors 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)

Full work available at URL https://doi.org/10.1109/FOCS.2009.22

Mathematics Subject Classification ID

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

Cited in

(8)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5171167)