On Near-Term Quantum Computation: Theoretical Aspects of Variational Quantum Algorithms and Quantum Computational Supremacy

In recent years, programmable quantum devices have reached sizes and complexities which put them outside the regime of simulation on modern supercomputers. However, since their computational power is not well understood, it’s not obvious what to do with them! Of course, there are several ideas, and this thesis contributes to the theory underpinning some of these ideas. It has two parts, corresponding to two of the most natural directions to pursue in searching for applications of near-term quantum computers. The first part is concerned with obtaining a deeper understanding of heuristic, hybrid quantum-classical algorithms which are potentially implementable on near-term devices and are aimed at attaining quantum speedups for practical problems, but lack a strong theoretical foundation and provable guarantees on their performance. More precisely, we obtain new theoretical results on the convergence rates of variational quantum algorithms, and prove that certain optimization strategies in such algorithms can, in some settings, lead to substantially better performance than the originally proposed, simpler, and potentially easier-to-implement approach. The second part is concerned with better understanding the capabilities of near-term quantum computers for demonstrating evidence of quantum computational supremacy in the complexity-theoretic sense of violating the Extended Church-Turing Thesis: a superpolynomial quantum speedup for a well-defined computational problem, possibly of no practical use, over all classical algorithms. More precisely, we study the computational complexity of classically simulating random 2D quantum circuits. While the classical hardness of simulating random circuits forms the basis of one of the leading quantum supremacy proposals, we challenge some of the intuition and evidence underlying this belief by developing new classical simulation algorithms which are efficient (polynomial-time) for 2D random circuits of sufficiently low constant depth; interestingly, these algorithms appear to experience computational phase transitions into an inefficient, exponential-time regime when the depth or local Hilbert space dimension surpasses some critical value.Ph.D