## Abstract

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.

Translated title of the contribution | Structure, randomness and complexity in quantum computation |
---|---|

Original language | English |

Publication status | Published - 2008 |