@article {2047, title = {Diffusion Monte Carlo Versus Adiabatic Computation for Local Hamiltonians}, journal = {Physical Review A}, volume = {97}, year = {2018}, month = {2018/02/15}, pages = {022323}, abstract = {

Most research regarding quantum adiabatic optimization has focused on stoquastic Hamiltonians, whose ground states can be expressed with only real, nonnegative amplitudes. This raises the question of whether classical Monte Carlo algorithms can efficiently simulate quantum adiabatic optimization with stoquastic Hamiltonians. Recent results have given counterexamples in which path integral and diffusion Monte Carlo fail to do so. However, most adiabatic optimization algorithms, such as for solving MAX-k-SAT problems, use k-local Hamiltonians, whereas our previous counterexample for diffusion Monte Carlo involved n-body interactions. Here we present a new 6-local counterexample which demonstrates that even for these local Hamiltonians there are cases where diffusion Monte Carlo cannot efficiently simulate quantum adiabatic optimization. Furthermore, we perform empirical testing of diffusion Monte Carlo on a standard well-studied class of permutation-symmetric tunneling problems and similarly find large advantages for quantum optimization over diffusion Monte Carlo.

}, doi = {10.1103/PhysRevA.97.022323}, url = {https://journals.aps.org/pra/abstract/10.1103/PhysRevA.97.022323}, author = {Jacob Bringewatt and William Dorland and Stephen P. Jordan and Alan Mink} } @article {1385, title = {On the degeneracy of SU(3)k topological phases}, year = {2010}, month = {2010/09/01}, abstract = {

The ground state degeneracy of an $SU(N)_k$ topological phase with $n$ quasiparticle excitations is relevant quantity for quantum computation, condensed matter physics, and knot theory. It is an open question to find a closed formula for this degeneracy for any $N \> 2$. Here we present the problem in an explicit combinatorial way and analyze the case N=3. While not finding a complete closed-form solution, we obtain generating functions and solve some special cases.

}, url = {http://arxiv.org/abs/1009.0114v1}, author = {Stephen P. Jordan and Toufik Mansour and Simone Severini} } @article {1254, title = {Discrete-query quantum algorithm for NAND trees}, journal = {Theory of Computing}, volume = {5}, year = {2009}, month = {2009/07/01}, pages = {119 - 123}, abstract = { Recently, Farhi, Goldstone, and Gutmann gave a quantum algorithm for evaluating NAND trees that runs in time O(sqrt(N log N)) in the Hamiltonian query model. In this note, we point out that their algorithm can be converted into an algorithm using O(N^{1/2 + epsilon}) queries in the conventional quantum query model, for any fixed epsilon > 0. }, doi = {10.4086/toc.2009.v005a005}, url = {http://arxiv.org/abs/quant-ph/0702160v1}, author = {Andrew M. Childs and Richard Cleve and Stephen P. Jordan and David Yeung} }