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 near-term 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. Time-optimal 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 p-norm 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 post-selection on quantum and classical computation is studied in the query complexity setting, where an unbounded separation is found between the post-selected quantum and classical query complexities of computing a certain (total) Boolean function. This separation arises from a lower bound on the post-selected classical query complexity of computing symmetric Boolean functions, which in turn arises from a characterisation of the query complexity in terms of the non-negative rational degree of Boolean functions.
| Date of Award | 23 Jan 2020 |
|---|---|
| Original language | English |
| Awarding Institution |
|
| Supervisor | Ashley M R Montanaro (Supervisor) |