Quantum adiabatic algorithm for the Ising model on a Bethe lattice

We investigate the average-case complexity of the quantum adiabatic algorithm (QAA) for the Ising model on the Bethe lattice by studying the asymptotic scaling of the minimum gap. For $N < 30$, this is done using direct diagonalization of the quantum Ising Hamiltonian with randomly chosen Gaussian exchange couplings. We use the Mezard-Parisi definition of the Bethe lattice for finite $N$ with the connectivity graph chosen uniformly at random among all $k$-regular graphs. The results of the direct diagonalization are compared to those from the parallel tempering version of quantum Monte Carlo (QMC) algorithm, and we use the QMC to study larger values of $N$.