Abstract
Since their original proposal in the 70s and 80s, quantum computers have evolved from an interesting theoretical concept to a physically realisable technology. This has been particularly exemplified with a recent publication by Arute et al. (Nature, 574(7779):505510, 2019), which has demonstrated a quantum computer solving a problem that is believed to be classically hard. While this is much cause for celebration and interest, the work towards showing what a quantum computer can really do is still yet to come. Arute et al.'s result shows a quantum computer solving a hard problem, but not a useful one.This is the question we push towards in this thesis: What problem with realworld applications can a quantum computer solve faster than a classical computer? We make contributions towards solving this problem in two ways:
First, an applicationsfocused approach: We show how a quantum computer can solve the Travelling Salesman Problem on boundeddegree graphs polynomially faster. This is achieved through applying a quantum speedup for Backtracking algorithms to classical algorithms for solving the Travelling Salesman Problem when the degree of the graph is at most 3 or 4. We then obtain further polynomial speedups when the degree of the graph is at most 6, by a combination of reducing to the degree4 case and quantum minimum finding.
Second, an architecturefocused approach: We consider how photon distinguishability and loss affect the nearterm quantum architecture known as Boson Sampling. In doing so, we provide a way of mathematically modelling these imperfections as decoherence in a quantum circuit, via representation theory in first quantisation. We then show how current classical simulation algorithms can be sped up by taking advantage of these imperfections, and suggest what photonic regimes our simulator provides better performance for.
Date of Award  23 Jun 2020 

Original language  English 
Awarding Institution 

Sponsors  Heilbronn Institute 
Supervisor  Noah Linden (Supervisor) & Peter Turner (Supervisor) 
Keywords
 quantum computing
 travelling salesman problem
 boson sampling