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''.
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''.
Many problems can be solved by preparing a specific eigenstate of some Hamiltonian H. The generic cost of quantum algorithms for these problems is determined by the inverse spectral gap of H for that eigenstate and the cost of evolving with H for some fixed time. The goal of spectral gap amplification is to construct a Hamiltonian H′ with the same eigenstate as H but a bigger spectral gap, requiring that constant-time evolutions with H′ and H are implemented with nearly the same cost. We show that a quadratic spectral gap amplification is possible when H satisfies a frustration-free property and give H′ for these cases. This results in quantum speedups for optimization problems. It also yields improved constructions for adiabatic simulations of quantum circuits and for the preparation of projected entangled pair states, which play an important role in quantum many-body physics. Defining a suitable black-box model, we establish that the quadratic amplification is optimal for frustration-free Hamiltonians and that no spectral gap amplification is possible, in general, if the frustration-free property is removed. A corollary is that finding a similarity transformation between a stoquastic Hamiltonian and the corresponding stochastic matrix is hard in the black-box model, setting limits to the power of some classical methods that simulate quantum adiabatic evolutions.
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.
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.
One of the most important algorithmic applications of quantum walks is to solve spatial search problems. A widely used quantum algorithm for this problem, introduced by Childs and Goldstone [Phys. Rev. A 70, 022314 (2004)], finds a marked node on a graph of n nodes via a continuous-time quantum walk. This algorithm is said to be optimal if it can find any of the nodes in O(n) time. However, given a graph, no general conditions for the optimality of the algorithm are known and previous works demonstrating optimal quantum search for certain graphs required an instance-specific analysis. In fact, the demonstration of the necessary and sufficient conditions that a graph must fulfill for quantum search to be optimal has been a long-standing open problem. In this work we make significant progress towards solving this problem. We derive general expressions, depending on the spectral properties of the Hamiltonian driving the walk, that predict the performance of this quantum search algorithm provided certain spectral conditions are fulfilled. Our predictions are valid, for example, for (normalized) Hamiltonians whose spectral gap is considerably larger than ${n}^{\ensuremath{-}1/2}$. This allows us to derive necessary and sufficient conditions for optimal quantum search in this regime, as well as provide examples of graphs where quantum search is suboptimal. In addition, by extending this analysis, we are also able to show the optimality of quantum search for certain graphs with very small spectral gaps, such as graphs that can be efficiently partitioned into clusters. Our results imply that, to the best of our knowledge, all prior results analytically demonstrating the optimality of this algorithm for specific graphs can be recovered from our general results.
The design of new quantum algorithms has proven to be an extremely difficult task. This paper considers a different approach to the problem, by studying the problem of 'quantum state generation'. This approach provides intriguing links between many different areas: quantum computation, adiabatic evolution, analysis of spectral gaps and groundstates of Hamiltonians, rapidly mixing Markov chains, the complexity class statistical zero knowledge, quantum random walks, and more.
We first show that many natural candidates for quantum algorithms can be cast as a state generation problem. We define a paradigm for state generation, called 'adiabatic state generation' and develop tools for adiabatic state generation which include methods for implementing very general Hamiltonians and ways to guarantee non negligible spectral gaps. We use our tools to prove that adiabatic state generation is equivalent to state generation in the standard quantum computing model, and finally we show how to apply our techniques to generate interesting superpositions related to Markov chains.
The design of new quantum algorithms has proven to be an extremely difficult task. This paper considers a different approach to the problem, by studying the problem of 'quantum state generation'. This approach provides intriguing links between many different areas: quantum computation, adiabatic evolution, analysis of spectral gaps and groundstates of Hamiltonians, rapidly mixing Markov chains, the complexity class statistical zero knowledge, quantum random walks, and more. We first show that many natural candidates for quantum algorithms can be cast as a state generation problem. We define a paradigm for state generation, called 'adiabatic state generation' and develop tools for adiabatic state generation which include methods for implementing very general Hamiltonians and ways to guarantee non negligible spectral gaps. We use our tools to prove that adiabatic state generation is equivalent to state generation in the standard quantum computing model, and finally we show how to apply our techniques to generate interesting superpositions related to Markov chains.