Bridging complexity theory and quantum mechanics with local Hamiltonians

Though initially emerging as an off-shoot of quantum mechanics, quantum computing, and its evolution into quantum complexity theory has deviated significantly from its early connection to actual quantum mechanical systems.  In fact, some argue that the ability to "abstract-away" the physics from QC is one of the main successes of the mathematical formulation of quantum mechanics.

 

In this talk, however, I'll survey a subfield of quantum complexity theory called local-Hamiltonian complexity,  that seeks to retain that connection in earnest - namely characterize the behavior of actual quantum mechanical systems.  The results of this field from the last 20 years, some emerging directly from computer science proof techniques, shed light on physical questions as diverse as tensor-network representations, quantum error correcting codes, and even stability of entanglement against thermal noise, the latter which is a critical stepping stone toward building a quantum computer.