CQuIC Seminars
Adiabatic Quantum Computing vs. Diffusion Monte Carlo
Presented by Stephen Jordan, NIST
Adiabatic quantum algorithms for optimization have generated a lot of excitement and substantial investment, but their scaling remains poorly understood. In particular, while adiabatic quantum computation using general Hamiltonians has been proven to be universal for quantum computation, almost all research so far, both experimental and theoretical, focuses on so-called stoquastic Hamiltonians, which have ground states expressible using only real positive amplitudes. There is complexity-theoretic evidence that ground state computation with stoquastic Hamiltonians may be less powerful than universal quantum computation. On the other hand, no efficient classical algorithm for simulating all stoquastic adiabatic processes has been found. Furthermore, Hastings has recently constructed a class of counterexamples in which path integral Monte Carlo will fail to simulate stoquastic adiabatic dynamics due to topological obstructions. Here, we investigate classical simulation methods related to diffusion Monte Carlo, which should not be affected by the topological obstructions identified by Hastings. We are able to construct a counterexample in which a non-topological obstruction prevents diffusion Monte Carlo from efficiently simulating a stoquastic adiabatic process. Nevertheless, we obtain analytical and computational evidence that on typical instances the simulation is reasonably efficient. This is joint work with Brad Lackey and Michael Jarret.
3:30 pm, Thursday, March 24, 2016
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