Spectral gaps play a fundamental role in many areas of mathematics, computer science, and physics. In quantum mechanics, the spectral gap of Schrödinger operators has a long history of study due to its physical relevance, while in quantum computing spectral gaps are an important proxy for efficiency, such as in the quantum adiabatic algorithm. Motivated by convex optimization, we study Schrödinger operators associated with self-concordant barriers over convex domains and prove non-asymptotic lower bounds on the spectral gap for this class of operators. Significantly, we find that the spectral gap does not display any condition-number dependence when the usual Laplacian is replaced by the Laplace--Beltrami operator, which uses second-order information of the barrier and hence can take the curvature of the barrier into account. As an algorithmic application, we construct a novel quantum interior point method that applies to arbitrary self-concordant barriers and shows no condition-number dependence. To achieve this we combine techniques from semiclassical analysis, convex optimization, and quantum annealing.
Spectral gaps play a fundamental role in many areas of mathematics, computer science, and physics. In quantum mechanics, the spectral gap of Schrödinger operators has a long history of study due to its physical relevance, while in quantum computing spectral gaps are an important proxy for efficiency, such as in the quantum adiabatic algorithm. Motivated by convex optimization, we study Schrödinger operators associated with self-concordant barriers over convex domains and prove non-asymptotic lower bounds on the spectral gap for this class of operators. Significantly, we find that the spectral gap does not display any condition-number dependence when the usual Laplacian is replaced by the Laplace--Beltrami operator, which uses second-order information of the barrier and hence can take the curvature of the barrier into account. As an algorithmic application, we construct a novel quantum interior point method that applies to arbitrary self-concordant barriers and shows no condition-number dependence. To achieve this we combine techniques from semiclassical analysis, convex optimization, and quantum annealing.
Convex optimization is the powerhouse behind the theory and practice of optimization. We introduce a quantum analogue of unconstrained convex optimization: computing the minimum eigenvalue of a Schrödinger operator $h = -Δ+ V $ with convex potential V:Rn→R≥0 such that $V(x)\rightarrow\infty $ as ∥x∥→∞. For this problem, we present an efficient quantum algorithm, called the Fundamental Gap Algorithm (FGA), that computes the minimum eigenvalue of h up to error ε in polynomial time in n, 1/ε, and parameters that depend on V. Adiabatic evolution of the ground state is used as a key subroutine, which we analyze with novel techniques that allow us to focus on the low-energy space. We apply the FGA to give the first known polynomial-time algorithm for finding the lowest frequency of an n-dimensional convex drum, or mathematically, the minimum eigenvalue of the Dirichlet Laplacian on an n-dimensional region that is defined by m linear constraints in polynomial time in n, m, 1/ε and the radius R of a ball encompassing the region.
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''.
We investigate algorithms for the quantum simulation of the Schrödinger equation on a Riemannian manifold, where the kinetic operator is defined by the Laplace--Beltrami operator corresponding to the metric. Our first algorithms are based on a global spectral method based on the identification of an efficient transform to the eigenbasis of the Laplace--Beltrami operator. We use this method to provide explicit, efficient, quantum simulation algorithms for the Riemannian Schrödinger equation on tori and spheres with their standard metrics, simplices with the Wright--Fisher metric, truncated positive orthants and their invertible affine images with the log-barrier Hessian metric, and ℓp balls with a metric induced by the Duffy map. Our second algorithm is based on a coherent simulation of local spectral methods on multiple charts, and is in principle applicable to any compact manifold. We first analyze this algorithm in the continuum and derive conditions under which a polynomial spectral cutoff suffices. We also provide a discretization analysis of a polynomial spectral cutoff for tensor-products of constant-dimensional manifolds. Finally, we consider applications of these methods to optimization and physical simulation. For optimization, we provide results including a generalization and convergence analysis of Quantum Hamiltonian Descent for geodesically convex functions that leads to explicit algorithms on the sphere and simplex, and a Riemannian generalization of the Real-Space Adiabatic Algorithm. For physical simulation, we show that our algorithms can simulate certain spatially discretized field theories, including a variant of the nonlinear sigma model.
Spectral properties of bounded linear operators play a crucial role in several areas of mathematics and physics. For each self-adjoint, trace-class operator O we define a set Λn⊂R, and we show that it converges to the spectrum of O in the Hausdorff metric under mild conditions. Our set Λn only depends on the first n moments of O. We show that it can be effectively calculated for physically relevant operators, and it approximates the spectrum well without diagonalization. We prove that using the above method we can converge to the minimal and maximal eigenvalues with super-exponential speed. We also construct monotone increasing lower bounds qn for the minimal eigenvalue (or decreasing upper bounds for the maximal eigenvalue). This sequence only depends on the moments of O and a concrete upper estimate of its 1-norm; we also demonstrate that qn can be effectively calculated for a large class of physically relevant operators. This rigorous lower bound qn tends to the minimal eigenvalue with super-exponential speed provided that O is not positive semidefinite. As a by-product, we obtain computable upper bounds for the 1-norm of O, too. Numerical examples demonstrate the relevance of our approximation in estimating entropy and negativity, which is useful, among others, in quantum optical and in open quantum system models. The results can be directly applicable to problems in quantum information, statistical mechanics, and quantum thermodynamics, where using traditional techniques based on diagonalization is impractical.
This dissertation is concerned with a variety of problems in quantum computing and the spectral theory of quantum-mechanical channels and Hamiltonians. We begin with the problem of quantum gate synthesis. The challenge is to find a fixed, finite set S of quantum gates such that, given a quantum circuit component U acting on n qubits and target precision ε, there is a short, efficiently computable composition of gates from S that approximates U to precision ε. This problem has already led to a rich literature in the case n=1 with deep connections to modern number theory. In this dissertation we present the state-of-the-art algorithm for a single qubit, achieving length 7 log (1/ε). The techniques used include the lattice structure of certain dense subgroups of PU(2) and Lenstra's algorithm for integer programming in convex domains. The next topic considered is scientific computing algorithms intended to run on a quantum computer. Specifically, we study a framework for computing functions of normal matrices using a quantum computer, with the objective of controlling the ancilla overhead, probability of success, and end precision. This arises as a special case of the multivariate quantum eigenvalue transform, for computing function of multiple commuting Hermitian matrices. The techniques applied include approximation of regular functions by low-degree polynomials and modern quantum primitives like quantum signal processing and linear combinations of unitaries. The third component is a spectral gap comparison result for Davies generators, a class of Lindbladians used for Gibbs state preparation and which are a well-studied example of quantum Markov dynamics, and which contain a canonical classical Markov chain. The main result shows that if the spectrum of the Hamiltonian driving the dynamics is free of long arithmetic progressions, then the spectral gaps of the quantum and classical Markov chains are comparable. Thus, classical techniques may be leveraged to control the behavior of the quantum dynamics. The proof is based on transferring any "off-diagonal" eigenvector of the Davies generator to an observable which commutes with the Hamiltonian and has a comparable Lindbladian Rayleigh quotient. Finally, we study the infimum of the spectrum, or ground state energy, of a discrete Schrödinger operator on the scaled integer grid in n dimensions, parameterized by a nonnegative potential V and a small frequency parameter θ. We relate this ground state energy to that of a corresponding continuous semiclassical Schrödinger operator on the full n-dimensional space with parameter θ, arising from the same choice of potential, and show that these quantities are equal up to vanishing factors depending on the regularity of V. The proofs are elementary and rely on sampling and interpolation to map low-energy functions for the discrete operator on the scaled grid to low-energy functions for the continuous operator on the full space, and vice versa. Coauthors on these works were J. Basso, T. R. Blackman, Y. Borns-Weil, I. Detherage, S. Ganguly, N. Srivastava, T. Saffat, A. Sinclair, and T.-D. Vuong.
I Plenary talks.- An adiabatic theorem without a gap condition.- Two-dimensional periodic Pauli operator. The effective masses at the lower edge of the spectrum.- Spectral problems in the theory of photonic crystals.- Optimal eigenvalues for some Laplacians and Schroedinger operators depending on curvature.- The spectral shift operator.- On the scattering operator for the Schroedinger equation with a time-dependent potential.- H_2-construction and some applications.- Scattering with time periodic potentials and cyclic states.- Some geometry related to decay properties of the resolvent of a class of symmetric operators.- On some asymptotic formulas in the strong localization regime of the theory of disordered systems.- Spectral measures and category.- Quantum dots. A survey of rigorous results.- II Session talks.- A simple model of concentrated nonlinearity.- Anomalous electron trapping by magnetic flux tubes and electric current vortices.- On the absolutely continuous energy distribution of a quantum mechanical system in a bounded domain.- Some aspects of generalized contact interaction in one-dimensional quantum mechanics.- Traces and trace norms for semigroup differences...- About a resolvent formula.- The determinant anomaly in low-dimensional quantum systems.- Linear Boltzmann equation as the weak coupling limit of the random Schroedinger equation.- Coexistence of different spectral types for almost periodic Schroedinger equations in dimension one.- Dynamical localization for random Schroedinger operators and an application to the almost Mathieu operator.- On fractal structure of the spectrum for periodic point perturbations of the Schroedinger operator with a uniform magnetic field.- A Weyl-Berry formula for the scattering operator associated to self-similar potentials on the line.- Localization and Lifshitz tails for random quantum waveguides.- Birman-Schwinger analysis for bound states in a pair of parallel quantum waveguides with a semitransparent boundary.- On the absolute continuity of spectra of periodic elliptic operators.- Hardy inequalities for magnetic Dirichlet forms.- Adiabatic curvature, chaos and the deformation of Riemann surfaces.- Operator interpretation of resonances arising in spectral problems for 2 x 2 matrix Hamiltonians.- On the operator-norm convergence of the Trotter-Kato product formula.- A particular case of the inverse problem for the Sturm-Liouville equation with parameter dependent potential.- One-dimensional Schroedinger operators with decaying potentials.- Stability of limiting absorption under singular perturbations.- Existence of averaging integrals for self-adjoint operators.- Monotonicity versus non-monotonicity in random operators.- A model in perturbation theory.- Band gap of the spectrum in periodically curved quantum waveguides.- A list of other talks.- A list of participants.