Towards a Quantum Speedup via Applications and Architectures

  • Alexandra E. Moylett

Student thesis: Doctoral ThesisDoctor of Philosophy (PhD)


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 Award23 Jun 2020
Original languageEnglish
Awarding Institution
  • The University of Bristol
SponsorsHeilbronn Institute
SupervisorNoah Linden (Supervisor) & Peter Turner (Supervisor)


  • quantum computing
  • travelling salesman problem
  • boson sampling

Cite this