Towards a Quantum Speedup via Applications and Architectures

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):505-510, 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 real-world applications can a quantum computer solve faster than a classical computer? We make contributions towards solving this problem in two ways:

First, an applications-focused approach: We show how a quantum computer can solve the Travelling Salesman Problem on bounded-degree 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 degree-4 case and quantum minimum finding.

Second, an architecture-focused approach: We consider how photon distinguishability and loss affect the near-term 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	The University of Bristol
Sponsors	Heilbronn Institute
Supervisor	Noah Linden (Supervisor) & Peter Turner (Supervisor)