Structure, randomness and complexity in quantum computation

This thesis explores the interplay between structure and randomness in quantum computation, with the goal being to characterise the types of structure that give quantum computers an advantage over classical computation. The thesis begins by giving a necessary and sufficient condition for one notion of a quantum walk to be defined on a directed graph, and goes on to derive conditions on the structure of graphs that allow a quantum advantage in a non-local graph colouring game. A lower bound on entanglement-assisted quantum communication complexity based on information-theoretic ideas is given, and applied to the communication complexity of random functions. New lower bounds on the probability of success of quantum state discrimination are derived, and are applied to the problem of distinguishing random quantum states. This result is used to show a quantum advantage in almost all instances of a bounded-error single-query oracle identification problem. Lower bounds, and almost optimal algorithms, are given for two models of quantum search of partially ordered sets. This leads to the development of an optimal quantum algorithm to find the intersection of two sorted lists.