Events Calendar
Monte carlo simulation of stoquastic hamiltonians
Thursday February 13, 2014
3:30 pm
Tweet |
Presenter: | Sergey Bravyi, IBM |
---|---|---|
Series: | CQuIC Seminars | |
Abstract: |
Hamiltonians avoiding the sign problem aka stoquastic are
characterized by the property that their off-diagonal matrix elements in the standard basis are real and non-positive. Many interesting quantum models fall into this class including Hamiltonians describing quantum annealing algorithms, the transverse field Ising model (TIM), the Heisenberg model on bipartite graphs, and the bosonic Hubbard model. I will consider the problem of estimating the ground state energy of a local stoquastic Hamiltonian and describe two special cases of this problem amenable to classical randomized algorithms: (1) Ferromagnetic TIM and (2) Guided Stoquastic Hamiltonian. The second problem includes an extra promise that the ground state has a non-negligible overlap with a sufficiently simple "guiding" state whose amplitudes can be efficiently computed. I will show that Ferromagnetic TIM can be solved in polynomial time on a classical probabilistic computer whereas Guided Stoquastic Hamiltonian is contained in the complexity class MA (probabilistic analogue of NP). |
|
Host: | Akimasa Miyake | |
Location: | PAIS-2540, PAIS | |