Events Calendar
Adiabatic Quantum Computing vs. Diffusion Monte Carlo
Thursday March 24, 2016
| 3:30 pm
Tweet |
Presenter: | Stephen Jordan, NIST |
|---|---|---|
| Series: | CQuIC Seminars | |
| Abstract: | 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. | |
| Location: | PAIS-2540, PAIS | |
If you need an auxiliary aid or service to attend any Department of Physics and Astronomy event, please contact the department (phone: 505 277-2616; email: