Quantum Advantage in Sensing and Simulation

Abstract

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 producing estimators with 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 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 the 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 are 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.

Finally, we also discuss the simulation complexity of Many-Body Localized systems. Many-Body Localization is a widely studied phase of matter that is often characterized by the appearance of a large number of quasilocal integrals of motion (operators that commute with the Hamiltonian) that interact via exponentially decaying interactions. In this dissertation, we study a phenomenological form of Many-Body Localization and show three main results. First, we demonstrate that, for polynomially long evolution times under a Hamiltonian in the Many-Body Localized phase, there is a quasipolynomial-time classical algorithm that can perform strong simulation of the output state. On the flip side, our second result is that, when the evolution time is exponentially long, weak simulation of the output state becomes formally classically hard. Finally, as a consequence of our classical results, we show the approximate quantum circuit complexity of these Hamiltonians grows sublinearly in the evolution time (in contrast with the proposed linear growth for chaotic Hamiltonians). Thus, this work helps clarify whether and how we might find quantum advantage via simulating certain types of condensed matter systems.