Search

We prove an adiabatic theorem that applies at timescales short of the adiabatic limit. Our proof analyzes the stability of solutions to Schrodinger's equation under perturbation. We directly characterize cross-subspace effects of perturbation, which are typically significantly less than suggested by the perturbation's operator norm. This stability has numerous consequences: we can (1) find timescales where the solution of Schrodinger's equation converges to the ground state of a block, (2) lower bound the convergence to the global ground state by demonstrating convergence to some other known quantum state, (3) guarantee faster convergence than the standard adiabatic theorem when the ground state of the perturbed Hamiltonian ($H$) is close to that of the unperturbed $H$, and (4) bound tunneling effects in terms of the global spectral gap when $H$ is ``stoquastic'' (a $Z$-matrix). Our results apply to quantum annealing protocols with faster convergence than usually guaranteed by a standard adiabatic theorem. Our upper and lower bounds demonstrate that at timescales short of the adiabatic limit, subspace dynamics can dominate over global dynamics. Thus, we see that convergence to particular target states can be understood as the result of otherwise local dynamics., 20 pages

An important family of span programs, st-connectivity span programs, have been used to design quantum algorithms in various contexts, including a number of graph problems and formula evaluation problems. The complexity of the resulting algorithms depends on the largest positive witness size of any 1-input, and the largest negative witness size of any 0-input. Belovs and Reichardt first showed that the positive witness size is exactly characterized by the effective resistance of the input graph, but only rough upper bounds were known previously on the negative witness size. We show that the negative witness size in an st-connectivity span program is exactly characterized by the capacitance of the input graph. This gives a tight analysis for algorithms based on st-connectivity span programs on any set of inputs. We use this analysis to give a new quantum algorithm for estimating the capacitance of a graph. We also describe a new quantum algorithm for deciding if a graph is connected, which improves the previous best quantum algorithm for this problem if we're promised that either the graph has at least kappa > 1 components, or the graph is connected and has small average resistance, which is upper bounded by the diameter. We also give an alternative algorithm for deciding if a graph is connected that can be better than our first algorithm when the maximum degree is small. Finally, using ideas from our second connectivity algorithm, we give an algorithm for estimating the algebraic connectivity of a graph, the second largest eigenvalue of the Laplacian., 33 pages

We consider the difference between the two lowest eigenvalues (the fundamental gap) of a Schr��dinger operator acting on a class of graphs. In particular, we derive tight bounds for the gap of Schr��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��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., 24 pages, 1 figure