On span programs and quantum algorithms

This dissertation is an in-depth discussion of the theory and applications of span programs. These objects, first introduced by Karchmer and Wigderson, encode 2-output functions and can be compiled into quantum query algorithms. Moreover, it was known before our work that the resulting span-program-based algorithms can be query and space optimal.

Part I of this thesis contains the introduction and mathematical preliminaries.

In Part II, we study the features and structure that are common to all - or at least large families - of span programs. First, we review two existing formulations of span programs before presenting a new formulation thatncontains and generalizes the previous two. Next, we present a plethora of quantum algorithms that can be compiled out of a span program, with special emphasis put on the flexibility of span programs for the purposes of algorithm design, an often-underappreciated feature.

In Chapter 4 we study a correspondence between quantum query algorithms and span programs. We conclude that for a broad category of functions, an optimal time, query and space span-program-based algorithm always exists, which implies that all these flavours of optimality are simultaneously achievable.

In Part III we use the st-connectivity span program to design quantum algorithms for graph connectivity and other related graph problems. We end the dissertation with a discussion of the st-connectivity problem as a boundary problem and a particular instance of the simplicial homology problem, and give span programs (and thus, quantum algorithms) for a few instances of this problem.