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.

1 aJarret, Michael1 aLackey, Brad1 aLiu, Aike1 aWan, Kianna uhttps://arxiv.org/abs/1810.0468601224nas a2200145 4500008004100000245013100041210006900172260001500241300001400256490000800270520068500278100002000963700002400983856007101007 2017 eng d00aModulus of continuity eigenvalue bounds for homogeneous graphs and convex subgraphs with applications to quantum Hamiltonians0 aModulus of continuity eigenvalue bounds for homogeneous graphs a c2017/03/03 a1269-12900 v4523 aWe 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.

1 aJarret, Michael1 aJordan, Stephen, P. uhttp://www.sciencedirect.com/science/article/pii/S0022247X1730272X03676nas a2200121 4500008004100000245004100041210004100082260001500123520334200138100002003480700001703500856003703517 2017 eng d00aSubstochastic Monte Carlo Algorithms0 aSubstochastic Monte Carlo Algorithms c2017/04/283 aIn 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.

1 aJarret, Michael1 aJordan, Stephen, P.1 aLackey, Brad uhttps://arxiv.org/abs/1607.0338901014nas a2200157 4500008004100000245007300041210006900114260001500183300001100198490000700209520054100216100001900757700002000776700002400796856003600820 2016 eng d00aYang-Baxter operators need quantum entanglement to distinguish knots0 aYangBaxter operators need quantum entanglement to distinguish kn c2016/01/12 a0752030 v493 a 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. 1 aAlagic, Gorjan1 aJarret, Michael1 aJordan, Stephen, P. uhttp://arxiv.org/abs/1507.0597901350nas a2200145 4500008004100000245004800041210004800089260001500137300001200152490000700164520095400171100002001125700002401145856003501169 2015 eng d00aAdiabatic optimization without local minima0 aAdiabatic optimization without local minima c2015/05/01 a181-1990 v153 a 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. 1 aJarret, Michael1 aJordan, Stephen, P. uhttp://arxiv.org/abs/1405.755201173nas a2200145 4500008004100000245009200041210007000133260001500203300001100218490000700229520071000236100002000946700002400966856003700990 2014 eng d00aThe Fundamental Gap for a Class of Schrödinger Operators on Path and Hypercube Graphs0 aFundamental Gap for a Class of Schrödinger Operators on Path and c2014/03/06 a0521040 v553 a 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. 1 aJarret, Michael1 aJordan, Stephen, P. uhttp://arxiv.org/abs/1403.1473v1