When a local Hamiltonian must be frustration-free
Abstract
Quantum computers promise computational power qualitatively superior to that achievable classically. This power will not be unlimited: Beyond much-touted applications, such as breaking encryption schemes, entire classes of problems are known to be intractable even for quantum computers. This work addresses a question of great practical relevance: In between these two extremes of certain (in)tractability, how can one efficiently diagnose the nature and properties of a given problem instance? To achieve this, we adopt a strategy of transferring insights from statistical physics and classical computing into the quantum realm. This provides a new perspective on the complexity of quantum problems and allows us to analyze a canonical class of quantum optimization problems in unprecedented explicit detail.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- May 19, 2016
- Source ID
- 10.1073/pnas.1519833113
Entities
People
- Chris R. Laumann
- Or Sattath
- Roderich Moessner
- Siddhardh C. Morampudi
Organizations
- Army Research Office
- German Research Foundation
- National Science Foundation
- University of Washington