Abstract
This thesis explores the apparent ability of quantum computers to outperform classical computers in a variety of settings. It approaches this goal from two quite different but complementary directions: at first by studying restricted models of quantum computing, and then by considering enhanced models of both quantum and classical computing. Both approaches aim to provide insight into the nature and power of universal quantum computers, understand what sorts of problems might be good candidate tasks for nearterm devices, and narrow down exactly what it is about quantum physics that seemingly gives us access to more computational power.It begins by introducing and describing span programs, a tool from the classical literature that has proved useful for designing quantum algorithms for a variety of problems, often with the added benefit that these algorithms are space efficient. Timeoptimal and space efficient quantum algorithms for deciding two graph properties, detecting cycles and testing bipartiteness, are developed using span programs as one of their main algorithmic ingredients.
The quantum computational complexity of estimating a natural mathematical quantity, the Schatten pnorm of a matrix, is studied and found to be closely related to the one clean qubit model – a restricted model of quantum computing inspired by NMR. It is shown that this quantity can be estimated efficiently using the one clean qubit model, and that estimating it is at least as hard as simulating this model.
The effect of postselection on quantum and classical computation is studied in the query complexity setting, where an unbounded separation is found between the postselected quantum and classical query complexities of computing a certain (total) Boolean function. This separation arises from a lower bound on the postselected classical query complexity of computing symmetric Boolean functions, which in turn arises from a characterisation of the query complexity in terms of the nonnegative rational degree of Boolean functions.
Date of Award  23 Jan 2020 

Original language  English 
Awarding Institution 

Supervisor  Ashley M R Montanaro (Supervisor) 