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 > Complexity classification of local Hamiltonian problems

## Complexity classification of local Hamiltonian problemsAdd to your list(s) Download to your calendar using vCal - Montanaro, A (University of Bristol)
- Wednesday 27 November 2013, 16:00-17:00
- Seminar Room 1, Newton Institute.
If you have a question about this talk, please contact Mustapha Amrani. Mathematical Challenges in Quantum Information Co-author: Toby Cubitt (University of Cambridge) The calculation of ground-state energies of physical systems can be formalised as the k-local Hamiltonian problem, which is the natural quantum analogue of classical constraint satisfaction problems. One way of making the problem more physically meaningful is to restrict the Hamiltonian in question by picking its terms from a fixed set S. Examples of such special cases are the Heisenberg and Ising models from condensed-matter physics. In this talk I will discuss work which characterises the complexity of this problem for all 2-local qubit Hamiltonians. Depending on the subset S, the problem falls into one of the following categories: in P; NP-complete; polynomial-time equivalent to the Ising model with transverse magnetic fields; or QMA -complete. The third of these classes contains NP and is contained within StoqMA. The characterisation holds even if S does not contain any 1-local terms; for example, we prove for the first time QMA -completeness of the Heisenberg and XY interactions in this setting. If S is assumed to contain all 1-local terms, which is the setting considered by previous work, we have a characterisation that goes beyond 2-local interactions: for any constant k, all k-local qubit Hamiltonians whose terms are picked from a fixed set S correspond to problems either in P; polynomial-time equivalent to the Ising model with transverse magnetic fields; or QMA -complete. These results are a quantum analogue of Schaefer’s dichotomy theorem for boolean constraint satisfaction problems. 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
- bld31
Note that ex-directory lists are not shown. |
## Other liststalks Film screening - Salaam Bombay! Cambridge Centre for Political Thought Biotech Talks- Dept of Biochemistry Clare Hall Talks CRASSH## Other talks70th Anniversary Celebration Arriva Trains Wales by Tom Joyner Kiwi Scientific Acceleration on FPGA Cancer and Metbolism 2018 Berndt Hauptkorn: 'The Business of Luxury' Building intuition about coherence 'Honouring Giulio Regeni: a plea for research in risky environments' Speculations about homological mirror symmetry for affine hypersurfaces 'Ways of Reading, Looking, and Imagining: Contemporary Fiction and Its Optics' Single Cell Seminars (August) LARMOR LECTURE - Exoplanets, on the hunt of Universal life Cosmology from the Kilo-Degree Survey |