Since the discovery of Shor’s factoring algorithm, there has been a sustained interest in finding more such examples of quantum advantage, that is, tasks where a quantum device can outperform its classical counterpart. While the universal, programmable quantum computers that can run Shor’s algorithm represent one direction in which to search for quantum advantage, they are certainly not the only one. In this dissertation, we study the theory of quantum advantage along two alternative avenues: sensing and simulation.
We also study a specific form of simulation called Gaussian Boson Sampling, which is a member of a broad framework of random sampling tasks that have become a popular method for demonstrating quantum advantage. While many of the theoretical underpinnings of these random sampling tasks, including Gaussian Boson Sampling, are well understood, many questions remain. Anticoncentration, which is strongly related to the moments of the output distribution, is a particularly relevant property when it comes to formally proving the existence of quantum advantage. We develop a graph-theoretic framework to calculate these moments, and we show that there is a transition in the strength of anticoncentration as a function of how many of the photonic modes were initially squeezed. We therefore demonstrate a transition in the evidence for the so-called approximate average-case hardness of Gaussian Boson Sampling, hence clarifying in what regimes we have the strongest evidence for quantum advantage.
*We strongly encourage attendees to use their full name (and if possible, their UMD credentials) to join the zoom session.*