CQuIC Seminars
Product-state approximations to ground states
Presented by Aram Harrow, MIT
Hamiltonians that are sums of two-body interactions between spins can be thought of as the quantum generalization of classical 2-CSPs (constraint-satisfaction problems). An important difference is that the ground state of a Hamiltonian will generally be entangled and as a result may fail to have a good short classical description. But is entanglement a property only of the ground state or can it be made to be important even for states with low extensive energy? The quantum PCP (probabilistically checkable proof) conjecture and the NLTS (no low-energy trivial state) conjecture both posit the existence of Hamiltonians where even low-energy states must be highly entangled. In this talk, I'll explain why such Hamiltonians (if they exist) must involve only a small number of interactions per system (i.e. must be defined on a low-degree graph). This will follow by showing how product states can approximate the ground-state energy of any Hamiltonian on a high-degree graph, thus putting the corresponding approximation problem in NP. This result can be thought of as removing the usual symmetry assumption from mean-field theory.
I will also prove that in many cases, low-energy product states not only exist but can be found efficiently. These cases include dense hypergraphs, planar graphs and graphs whose adjacency matrices have few large eigenvalues.
This is based on arXiv:1310.0017, which is joint work with Fernando Brandao.
3:30 pm, Thursday, April 3, 2014
PAIS-2540, PAIS
Individuals with disabilities who need an auxiliary aid or service to attend or participate in P&A events should contact the Physics Department (phone: 505-277-2616, email: physics@unm.edu) well in advance to ensure your needs are accomodated. Event handouts can be provided in alternative accessible formats upon request. Please contact the Physics front office if you need written information in an alternative format.
A schedule of talks within the Department of Physics and Astronomy is available on the P&A web site at http://physics.unm.edu/pandaweb/events/index.php