Quantum computers exist today that are capable of performing calculations that challenge the largest classical supercomputers. Now the great challenge is to make use of these devices, or their successors, to perform calculations of independent interest. This thesis focuses on a family of algorithms that aim to accomplish this goal, known as variational quantum algorithms, and the challenges that they face. We frame these challenges in terms of two kinds of resources, the number of operations that we can afford to perform in a single quantum circuit, and the overall number of circuit repetitions required. Before turning to our specific contributions, we provide a review of the electronic structure problem, which serves as a central example for our work. We also provide a self-contained introduction to the field of quantum computing and the notion of a variational quantum algorithm.

We begin the main body of the thesis by studying a generalization of the standard unitary coupled cluster ansatz. We present a sparse version of unitary coupled cluster and show that it can accurately represent the ground and excited states of small molecular systems using fewer quantum gates than the full unitary coupled cluster. We then introduce a strategy for representing molecular ground states as linear combinations of parameterized wavefunctions, allowing for a tradeoff between the number of operations required for each circuit and the number of circuit repetitions. We provide circuit primitives that allow for the efficient measurement of the required matrix elements between these wavefunctions. Subsequently, we show how the cost of estimating the energy of a quantum chemical wavefunction on a near-term quantum computer can be dramatically reduced by using a factorization of the two-electron integral

tensor. Furthermore, we explain how this measurement strategy helps mitigate against errors during state preparation and measurement. We then present a Monte Carlo version of a classical algorithm for calculating the partition function of two-dimensional lattice models that shows a similar kind of tradeoff between two resources, albeit in a different context. Finally, we show how ideas based on tensor networks can inform the design of quantum circuits for machine learning tasks. We argue that this application is especially tolerant to noise and present numerical data substantiating this argument. We conclude by explaining explicitly how our work addresses the problems of the limited resources available to near-term quantum computers and offering some optimism about the future of the field.

Quantum computers now exist, and will likely continue to get bigger and better. But will theyever be useful? That is, are there real-world problems that future quantum computers will be able to solve well enough in a reasonable amount of time, but for which classical computers cannot do the same? This thesis presents a collection of results that together address this question from different directions. The first part limits the utility of quantum computers. We show how to characterize and minimize the cost (in time and memory) of simulating quantum computations on a classical computer in terms of the congestion (a graph property) of a graphical representation of the quantum computation. Therefore, for a quantum computation to have an advantage over classical computation, it must have large congestion. Even when that is the case, better classical simulations, costly though they may be, can help validate and develop quantum computers. We also prove that the fundamental problem of quantum chemistry, the electronic structure problem, is QMA-complete. Therefore, under standard complexity-theoretic assumptions, the solution must be represented using a quantum state, and yet still even quantum computers cannot efficiently find it. The second part includes methods for applying and compiling quantum algorithms in order to maximize the utility of the hardware we have, now and in the future. We introduce the strategy of generalized swap networks and show how to use them to compile quantum algorithms for quantum chemistry and classical optimization. We combine quantum computation with constraint programming in two ways: we show how to combine existing quantum algorithms to speed up the solution of constraint programming problems, which capture a wide range of realistic application domains, and also discuss the application of constraint programming to compiling quantum algorithms. We also present a framework for generalizing the Quantum Approximate Optimization Algorithm to what we call the Quantum Alternating Operator Ansatz. Many of the algorithms are heuristic, but by improving the efficiency of their implementation on actual devices, we improve our chances of successfully trying them out and seeing if they work or not.