COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

University of Cambridge > Talks.cam > Isaac Newton Institute Seminar Series > A polynomial-time algorithm for the ground state of 1D gapped local Hamiltonians

## A polynomial-time algorithm for the ground state of 1D gapped local HamiltoniansAdd to your list(s) Download to your calendar using vCal - Vidick, T (Massachusetts Institute of Technology)
- Thursday 28 November 2013, 15:00-16:00
- Seminar Room 1, Newton Institute.
If you have a question about this talk, please contact Mustapha Amrani. Mathematical Challenges in Quantum Information Co-authors: Zeph Landau (UC Berkeley), Umesh Vazirani (UC Berkeley) Computing ground states of local Hamiltonians is a fundamental problem in condensed matter physics. We give the first randomized polynomial-time algorithm for finding ground states of gapped one-dimensional Hamiltonians: it outputs an (inverse-polynomial) approximation, expressed as a matrix product state (MPS) of polynomial bond dimension. The algorithm combines many ingredients, including recently discovered structural features of gapped 1D systems, convex programming, insights from classical algorithms for 1D satisfiability, and new techniques for manipulating and bounding the complexity of MPS . Our result provides one of the first major classes of Hamiltonians for which computing ground states is provably tractable despite the exponential nature of the objects involved. Joint work with Zeph Landau and Umesh Vazirani. This talk is part of the Isaac Newton Institute Seminar Series series. ## This talk is included in these lists:- All CMS events
- Featured lists
- INI info aggregator
- Isaac Newton Institute Seminar Series
- School of Physical Sciences
- Seminar Room 1, Newton Institute
Note that ex-directory lists are not shown. |
## Other listsVisual rhetoric and modern South Asian history (2013) One Day Meeting - 6th Annual Symposium of the Cambridge Computational Biology Institute Type the title of a new list here## Other talksComplement and microglia mediated sensory-motor synaptic loss in Spinal Muscular Atrophy How could education systems research prompt a change to how DFIS works on education The Partition of Ukraine: A Nightmare HONORARY FELLOWS PRIZE LECTURE - Towards a silent aircraft Quotation and the Law Optimising fresh produce quality monitoring and analysis |