Applications of Gaussian boson sampling in graph theory

Abstract

Quantum optics, which encodes information in the states of light, is privileged to have
complexity-theoretic evidence supporting a scheme for quantum advantage that is native to
the platform – boson sampling, and its variant Gaussian boson sampling – providing a natu-
ral choice for early proof-of-concept quantum computing experiments.
Beyond the objective of quantum advantage, the known applications of Gaussian boson
sampling are limited. A useful framework for developing and analysing potential uses arises
from its description in the language of graph theory, which is the basis for many well-known
mathematically hard problems, including dense subgraph finding, a problem which repre-
sents difficult tasks in various fields, from finance to drug discovery.
In this thesis, we consider evidence for Gaussian boson sampling showing a performance
or time advantage for certain applications. We use numerical simulations of realistic sources
of error in Gaussian boson sampling, when applied to dense subgraph finding, which dis-
agree with the possibility of quantum advantage for this use case; we show how a similar per-
formance in sampling high-density subgraphs can be achieved by classical sampling tech-
niques, and assess the performance of various sampling schemes for graph problems; we
provide evidence that sampling from displaced Gaussian states also cannot be efficiently
classically simulated (that is, in polynomial time) in the case of sufficiently low displace-
ment, and we use the connection between the loop hafnian and the matching polynomial
to identify regimes in which simulating displaced Gaussian boson sampling is classically ef-
ficient. Although these techniques do not show any additional uses of Gaussian boson sam-
pling, they provide important insights into its value as a computational tool and improve
our understanding of the features expected in further applications.

Date of Award	7 May 2024
Original language	English
Awarding Institution	University of Bristol
Supervisor	Anthony Laing (Supervisor)