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.
Sensing refers to the task of measuring some unknown quantity with the smallest possible error. In many cases, when the sensing apparatus is a quantum device, this ultimate achievable precision, as well as specific protocols achieving this precision, are unknown. In this dissertation, we help close this gap for both qubit-based and photonic quantum sensors for the specific task of measuring a linear function of unknown parameters. We use quantum Fisher information and the quantum Cramér-Rao bound to derive limits on their ultimate precision. We further develop an algebraic framework that allows us to derive protocols saturating these bounds and also better understand the quantum resources, such as entanglement, that are necessary to implement these protocols. In doing so, we help clarify how quantum resources like entanglement lead to more precise sensing.
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.*