Ewin Tang

What does it mean to have access to a subroutine? In quantum computing, the usual answer is that, if we can perform a circuit implementing a unitary $U$, we can also implement its variants $U^\dagger$, $\controlled U$, and $\controlled U^\dagger$ equally as efficiently. These four operations are the "usual" suite of oracles we mean when we model access to a subroutine. We interrogate these choices and investigate how changing our access model to $U$ affects the tractability of its computational problems. This submission is a collection of three preprints on possible models of oracle access. 1. In the most limited setting, we only have access to $U$: this is the natural model for metrology, sensing, learning, and other experimental contexts. We show that, unlike in the usual model, the generic Grover speedups for search and estimation, ubiquitous throughout quantum algorithms, cannot be achieved in this setting. 2. In the usual model as well as in general, we show that controlled unitary oracles have a surprisingly limited role. We prove they are not helpful for a large class of problems: problems which are invariant up to global phase, i.e. problems which are a about $U$ as a unitary channel. 3. In the full setting, we are given a circuit implementing $U$: this model is natural for algorithms on scalable quantum computers. We show that the usual suite of oracles is not enough to characterize the strength of this model, by giving a natural problem which cannot be solved efficiently without queries to $U^*$ or $U^T$---which can be implemented from any circuit for $U$. Our proofs are simple and use two main techniques: the compressed oracle method and a lifting principle which we call the "acorn trick".

A central challenge of quantum physics is to understand the structural properties of many-body systems, both in equilibrium and out of equilibrium. For classical systems, we have a unified perspective which connects structural properties of systems at thermal equilibrium to the Markov chain dynamics which mix to them. We lack such a perspective for quantum systems: many of the most fundamental ideas of the modern classical theory are notably absent from our quantum toolkit. We develop a theory which brings the broad scope and flexibility of the classical theory to quantum Gibbs states at high temperature. At its core is a natural quantum analogue of Dobrushin’s condition; whenever this condition holds, a concise path-coupling argument proves rapid mixing for the corresponding Markovian evolution. The same machinery bridges dynamic and structural properties: rapid mixing yields exponential decay of CMI without restrictions on the size of the probed subsystems, resolving a central question in the theory of open quantum systems. Our key technical insight is an optimal transport viewpoint which couples the quantum dynamics to a linear differential equation, enabling precise control over how local deviations from equilibrium propagate to distant sites.