We exhibit an exact correspondence between sampling with score-based diffusion models and adiabatic transport of ground states for a family of Schrödinger operators we call Score Hamiltonians, built from the learned score's quantum potential. We obtain novel density reconstruction bounds and principled annealing schedules via adiabatic theorems for Fokker-Planck equations with time-varying potentials. We find the fundamental limit of sampling is set by the ratio of squared score-matching error to Score Hamiltonian spectral gap - the inverse Poincaré constant of the data density.
We exhibit an exact correspondence between sampling with score-based diffusion models and adiabatic transport of ground states for a family of Schrödinger operators we call Score Hamiltonians, built from the learned score's quantum potential. We obtain novel density reconstruction bounds and principled annealing schedules via adiabatic theorems for Fokker-Planck equations with time-varying potentials. We find the fundamental limit of sampling is set by the ratio of squared score-matching error to Score Hamiltonian spectral gap - the inverse Poincaré constant of the data density.
We prove an adiabatic theorem that applies at time scales short of the typical adiabatic limit. Our proof analyses 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 time scales where the solution of Schrodinger’s equation converges to the ground state of a subspace, (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 is close to that of the unperturbed Hamiltonian and (4) bound leakage effects in terms of the global spectral gap when the Hamiltonian is ‘stoquastic’ (a Z -matrix). Our results can help explain quantum annealing protocols that exhibit faster convergence than is guaranteed by a standard adiabatic theorem. Our upper and lower bounds demonstrate that at time scales short of the adiabatic limit, subspace dynamics can dominate over global dynamics. Thus, we see that when our results apply, convergence to particular global target states can be understood as the result of local dynamics.
In this dissertation I draw a connection between quantum adiabatic optimization, spectral graph theory, heat-diffusion, and sub-stochastic processes through the operators that govern these processes and their associated spectra. In particular, we study Hamiltonians which have recently become known as ``stoquastic'' or, equivalently, the generators of sub-stochastic processes. The operators corresponding to these Hamiltonians are of interest in all of the settings mentioned above. I predominantly explore the connection between the spectral gap of an operator, or the difference between the two lowest energies of that operator, and certain equilibrium behavior. In the context of adiabatic optimization, this corresponds to the likelihood of solving the optimization problem of interest. I will provide an instance of an optimization problem that is easy to solve classically, but leaves open the possibility to being difficult adiabatically. Aside from this concrete example, the work in this dissertation is predominantly mathematical and we focus on bounding the spectral gap. Our primary tool for doing this is spectral graph theory, which provides the most natural approach to this task by simply considering Dirichlet eigenvalues of subgraphs of host graphs. I will derive tight bounds for the gap of one-dimensional, hypercube, and general convex subgraphs. The techniques used will also adapt methods recently used by Andrews and Clutterbuck to prove the long-standing ``Fundamental Gap Conjecture''.
Quantum control could be implemented by varying the system Hamiltonian. According to adiabatic theorem, a slowly changing Hamiltonian can approximately keep the system at the ground state during the evolution if the initial state is a ground state. In this paper we consider this process as an interpolation between the initial and final Hamiltonians. We use the mean value of a single operator to measure the distance between the final state and the ideal ground state. This measure resembles the excitation energy or excess work performed in thermodynamics, which can be taken as the error of adiabatic approximation. We prove that under certain conditions, this error can be estimated for an arbitrarily given interpolating function. This error estimation could be used as guideline to induce adiabatic evolution. According to our calculation, the adiabatic approximation error is not linearly proportional to the average speed of the variation of the system Hamiltonian and the inverse of the energy gaps in many cases. In particular, we apply this analysis to an example in which the applicability of the adiabatic theorem is questionable.
The quantum adiabatic theorem ensures that a slowly changing system, initially prepared in its ground state, will evolve to its final ground state with arbitrary precision. As a first result this thesis extends the original theorem to projection operators keeping the statement valid for Hamiltonians with degenerate ground spaces. Yet the main focus of this work lies in studying the efficiency of quantum circuit simulations by adabatic quantum computation. The standard Hamiltonian construction by Kitaev is based on a path graph reflecting the L computation steps and influencing the scaling of the necessary evolution time by its spectral gap of O(L21). Aspiring to an improved running time we generalize Kitaev's Hamiltonian to so-called standard graph Hamiltonians based on graph families with a different spectral gap. In this generalized construction the first two time derivatives of the Hamiltonian and the fraction of initial vertices appear as additional parameters of running time. In a first step the time derivatives can be proven to be constant. Expansion results from spectral graph theory however impose a trade-off between the spectral gap and the fraction of initial vertices as well as the fraction of final vertices which corresponds to the probability for obtaining the correct computational output. Graphs with spectral gap O(Lk1), k<2, turn out to contradict very likely, graphs with k<1 even for sure at least one of the efficiency criterias for running time, output probability or Hamiltonian implementation. The above results may also be obstacles for a possible quantum PCP-theorem in complexity theory claiming the local Hamiltonian problem with constant gap to be QMA-complete since the very same Kitaev Hamiltonian is constructed in the QMA-hardness proof for the Local Hamiltonian problem.
Many physically interesting models show a quantum phase transition when a single parameter is varied through a critical point, where the ground state and the first excited state become degenerate. When this parameter appears as a coupling constant, these models can be understood as straight-line interpolations between different Hamiltonians HI and HF. For finite-size realizations however, there will usually be a finite energy gap between ground and first excited state. By slowly changing the coupling constant through the point with the minimum energy gap one thereby has an adiabatic algorithm that prepares the ground state of HF from the ground state of HI. The adiabatic theorem implies that in order to obtain a good preparation fidelity the runtime $\ensuremath{\tau}$ should scale with the inverse energy gap and thereby also with the system size. In addition, for open quantum systems not only nonadiabatic but also thermal excitations are likely to occur. It is shown that---using only local Hamiltonians---for the one-dimensional quantum Ising model and the cluster model in a transverse field the conventional straight-line path can be replaced by a series of straight-line interpolations, along which the fundamental energy gap is always greater than a constant independent on the system size. The results are of interest for adiabatic quantum computation since strong similarities between adiabatic quantum algorithms and quantum phase transitions exist.
Diffusion sampling is related to imaginary-time quantum annealing through a forward/backward Schrödinger equation pair and its one-sided counterdiabatic connection. For a smooth, gapped Score-Hamiltonian path, the exact connection transports the target density at any evolution time. We apply quantum-annealing performance analysis to residuals from approximating this connection with a trained score. If the first r terminal schedule derivatives vanish, the squared Hellinger error scales as T−2r−2, with a prefactor determined by the terminal learning residual and inverse gaps. Direct two-dimensional imaginary-time evolution with one fixed neural score reproduces these powers and prefactors. Terminal schedule design thus suppresses the distributional effect of imperfect score learning without retraining the network.