Quantum adiabatic optimization (QAO) is performed using a time-dependent Hamiltonian H(s) with spectral gap γ(s). Assuming the existence of an oracle Γ such that γ(s)=Θ(Γ(s)), we provide an algorithm that reliably performs QAO in time Oγ\−1minlog(γ\−1min) with Olog(γ\−1min) oracle queries, where γmin=minsγ(s). Our strategy is not heuristic and does not require guessing time parameters or annealing paths. Rather, our algorithm naturally produces an annealing path such that dH/ds\≈γ(s) and chooses its own runtime T to be as close as possible to optimal while promising convergence to the ground state. We then demonstrate the feasibility of this approach in practice by explicitly constructing a gap oracle Γ for the problem of finding a vertex m=argminuW(u) of the cost function W:V⟶[0,1], restricting ourselves to computational basis measurements and driving Hamiltonian H(0)=I\−V\−1\∑u,v\∈V|u\⟩\⟨v|, with V=|V|. Requiring only that W have a constant lower bound on its spectral gap and upper bound κ on its spectral ratio, our QAO algorithm returns m using Γ with probability (1\−ε)(1\−e\−1/ε) in time O\˜(ε\−1[V\−\−\√+(κ\−1)2/3V2/3]). This achieves a quantum advantage for all κ, and when κ\≈1, recovers Grover scaling up to logarithmic factors. We implement the algorithm as a subroutine in an optimization procedure that produces m with exponentially small failure probability and expected runtime O\˜(ε\−1[V\−\−\√+(κ\−1)2/3V2/3]), even when κ is not known beforehand.

}, url = {https://arxiv.org/abs/1810.04686}, author = {Michael Jarret and Brad Lackey and Aike Liu and Kianna Wan} } @article {1392, title = {Modulus of continuity eigenvalue bounds for homogeneous graphs and convex subgraphs with applications to quantum Hamiltonians}, journal = {Journal of Mathematical Analysis and Applications}, volume = {452}, year = {2017}, month = {2017/03/03}, pages = {1269-1290}, abstract = {We adapt modulus of continuity estimates to the study of spectra of combinatorial graph Laplacians, as well as the Dirichlet spectra of certain weighted Laplacians. The latter case is equivalent to stoquastic Hamiltonians and is of current interest in both condensed matter physics and quantum computing. In particular, we introduce a new technique which bounds the spectral gap of such Laplacians (Hamiltonians) by studying the limiting behavior of the oscillations of their eigenvectors when introduced into the heat equation. Our approach is based on recent advances in the PDE literature, which include a proof of the fundamental gap theorem by Andrews and Clutterbuck.

}, doi = {10.1016/j.jmaa.2017.03.030}, url = {http://www.sciencedirect.com/science/article/pii/S0022247X1730272X}, author = {Michael Jarret and Stephen P. Jordan} } @article {1992, title = {Substochastic Monte Carlo Algorithms}, year = {2017}, month = {2017/04/28}, abstract = {In this paper we introduce and formalize Substochastic Monte Carlo (SSMC) algorithms. These algorithms, originally intended to be a better classical foil to quantum annealing than simulated annealing, prove to be worthy optimization algorithms in their own right. In SSMC, a population of walkers is initialized according to a known distribution on an arbitrary search space and varied into the solution of some optimization problem of interest. The first argument of this paper shows how an existing classical algorithm, \"Go-With-The-Winners\" (GWW), is a limiting case of SSMC when restricted to binary search and particular driving dynamics.\

Although limiting to GWW, SSMC is more general. We show that (1) GWW can be efficiently simulated within the SSMC framework, (2) SSMC can be exponentially faster than GWW, (3) by naturally incorporating structural information, SSMC can exponentially outperform the quantum algorithm that first inspired it, and (4) SSMC exhibits desirable search features in general spaces. Our approach combines ideas from genetic algorithms (GWW), theoretical probability (Fleming-Viot processes), and quantum computing. Not only do we demonstrate that SSMC is often more efficient than competing algorithms, but we also hope that our results connecting these disciplines will impact each independently. An implemented version of SSMC has previously enjoyed some success as a competitive optimization algorithm for Max-

Most experimental and theoretical studies of adiabatic optimization use stoquastic Hamiltonians, whose ground states are expressible using only real nonnegative amplitudes. This raises a question as to whether classical Monte Carlo methods can simulate stoquastic adiabatic algorithms with polynomial overhead. Here, we analyze diffusion Monte Carlo algorithms. We argue that, based on differences between L1 and L2 normalized states, these algorithms suffer from certain obstructions preventing them from efficiently simulating stoquastic adiabatic evolution in generality. In practice however, we obtain good performance by introducing a method that we call Substochastic Monte Carlo. In fact, our simulations are good classical optimization algorithms in their own right, competitive with the best previously known heuristic solvers for MAX-k-SAT at k=2,3,4.

}, url = {https://arxiv.org/abs/1607.03389}, author = {Michael Jarret and Stephen P. Jordan and Brad Lackey} } @article {1393, title = {Yang-Baxter operators need quantum entanglement to distinguish knots}, journal = {Journal of Physics A}, volume = {49}, year = {2016}, month = {2016/01/12}, pages = {075203}, abstract = { Any solution to the Yang-Baxter equation yields a family of representations of braid groups. Under certain conditions, identified by Turaev, the appropriately normalized trace of these representations yields a link invariant. Any Yang-Baxter solution can be interpreted as a two-qudit quantum gate. Here we show that if this gate is non-entangling, then the resulting invariant of knots is trivial. We thus obtain a general connection between topological entanglement and quantum entanglement, as suggested by Kauffman et al. }, doi = {10.1088/1751-8113/49/7/075203}, url = {http://arxiv.org/abs/1507.05979}, author = {Gorjan Alagic and Michael Jarret and Stephen P. Jordan} } @article {1390, title = {Adiabatic optimization without local minima}, journal = {Quantum Information and Computation}, volume = {15}, year = {2015}, month = {2015/05/01}, pages = {181-199}, abstract = { Several previous works have investigated the circumstances under which quantum adiabatic optimization algorithms can tunnel out of local energy minima that trap simulated annealing or other classical local search algorithms. Here we investigate the even more basic question of whether adiabatic optimization algorithms always succeed in polynomial time for trivial optimization problems in which there are no local energy minima other than the global minimum. Surprisingly, we find a counterexample in which the potential is a single basin on a graph, but the eigenvalue gap is exponentially small as a function of the number of vertices. In this counterexample, the ground state wavefunction consists of two "lobes" separated by a region of exponentially small amplitude. Conversely, we prove if the ground state wavefunction is single-peaked then the eigenvalue gap scales at worst as one over the square of the number of vertices. }, url = {http://arxiv.org/abs/1405.7552}, author = {Michael Jarret and Stephen P. Jordan} } @article {1389, title = {The Fundamental Gap for a Class of Schr{\"o}dinger Operators on Path and Hypercube Graphs}, journal = {Journal of Mathematical Physics}, volume = {55}, year = {2014}, month = {2014/03/06}, pages = {052104}, abstract = { We consider the difference between the two lowest eigenvalues (the fundamental gap) of a Schr\"{o}dinger operator acting on a class of graphs. In particular, we derive tight bounds for the gap of Schr\"{o}dinger operators with convex potentials acting on the path graph. Additionally, for the hypercube graph, we derive a tight bound for the gap of Schr\"{o}dinger operators with convex potentials dependent only upon vertex Hamming weight. Our proof makes use of tools from the literature of the fundamental gap theorem as proved in the continuum combined with techniques unique to the discrete case. We prove the tight bound for the hypercube graph as a corollary to our path graph results. }, doi = {10.1063/1.4878120}, url = {http://arxiv.org/abs/1403.1473v1}, author = {Michael Jarret and Stephen P. Jordan} }