On Span Programs and Quantum Algorithms
Álvaro Piedrafita

Abstract:
This dissertation is an in-depth discussion of the theory and applications of span programs. These objects, first introduced in the context of classical counting branching programs by Karchmer and Wigderson, are a model of computation (i.e. they 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. The thesis is divided in three parts. Part I contains the introduction and mathematical preliminaries.
In Part II, we discuss the theory of span programs, meaning that we study the features and structure that are common to all - or at least large families - of span programs. Chapter 3 begins with a review of two existing formulations of span programs before presenting a new formulation that contains and generalizes the previous two. The second part of the chapter presents a plethora of different quantum algorithms that can be compiled out of a span program. Special emphasis is put on the flexibility of span programs for the purposes of algorithm design, a feature that has often been underappreciated. 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, and perhaps more importantly, that all these flavours of optimality are simultaneously achievable.
In Part III we use span programs to design quantum algorithms. In Chapter 5, we use the st-connectivity span program to design quantum algorithms for graph connectivity and other related graph problems, some of which are not decision problems. We end the dissertation in Chapter 6 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.