John Wright

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".

We study the error correcting properties of Haar random codes, in which a $K$-dimensional code space $\bC \subseteq \C^N$ is chosen at random from the Haar distribution. Our main result is that Haar random codes can approximately correct errors up to the quantum Hamming bound, meaning that a set of $m$ Pauli errors can be approximately corrected so long as $mK \ll N$. This is the strongest bound known for any family of quantum error correcting codes (QECs), and continues a line of work showing that approximate QECs can significantly outperform exact QECs [LNCY97,CGS05,BGG24]. Our proof relies on a recent matrix concentration result of Bandeira, Boedihardjo, and van Handel [BBV23].

In the problem of quantum state tomography, one is given $n$ copies of an unknown rank-$r$ mixed state $\rho \in \C^{d \times d}$ and asked to produce an estimator $\widehat{\brho}$ of $\rho$ which is close to it. One of the most basic and useful properties a statistical estimator can have is that of being \emph{unbiased}, meaning that $\widehat{\brho}$ is equal to the true state $\rho$ in expectation. Unfortunately, of the three estimators for tomography which are known to be either sample-optimal or almost sample-optimal, namely Keyl's algorithm~\cite{Key06} and the two tomography algorithms from~\cite{HHJ+16}, none of them produce unbiased estimators. This situation has recently been highlighted as a bottleneck in several important tomographic applications~\cite{CLL24a,CLL24b}. In this work, we present the \emph{debiased Keyl's algorithm}, the first estimator for full state tomography which is both unbiased and sample-optimal. Our algorithm is the result of taking Keyl's algorithm and carefully modifying it in order to correct for its bias. In addition, we derive an explicit formula for the second moment of our estimator which is simple and easy to use. Using it, we show the following applications. \begin{itemize} \item[$\circ$] We show that $n = O(rd/\epsilon^2)$ copies are sufficient to learn a rank-$r$ mixed state $\rho \in \C^{d \times d}$ to trace distance error $\epsilon$. This gives a new proof of the main result of~\cite{OW16} and matches the lower bound of~\cite{SSW25}. \item[$\circ$] We then improve this result and show that $n = O(rd/\epsilon^2)$ copies are sufficient to learn to error $\epsilon$ in the more challenging Bures distance. This is optimal due to the lower bound of~\cite{Yue23} and improves on the best known bound of $n = \widetilde{O}(rd/\epsilon^2)$ from prior work~\cite{HHJ+16,OW17a,FO24}. \item[$\circ$] We consider the scenario of full state tomography with limited entanglement, in which one is given $n$ copies of $\rho$ but only allowed to perform entangled measurements across $k$ of them at a time. We show that \begin{equation*} n =O\left(\max \left(\frac{d^3}{\sqrt{k}\epsilon^2}, \frac{d^2}{\epsilon^2} \right) \right) \end{equation*} copies of $\rho$ suffice to learn $\rho$ to trace distance error $\epsilon$ in this scenario. This improves on the prior work of \cite{CLL24a} and matches their lower bound which holds for $k \leq 1/\epsilon^c$, where $c$ is a constant. \item[$\circ$] In the problem of shadow tomography, one is given $m$ observables $O_1, \ldots, O_m$, and the goal is to estimate each quantity $\tr(O_i \cdot \rho)$ up to $\epsilon$ error. If $\Vert O_i \Vert_{\infty} \leq 1$ for all $i$, we show that $O(\log(m)/\epsilon^2)$ copies are sufficient to solve this task in the ``high accuracy regime'' when $\epsilon = O(1/d)$. This improves a result of~\cite{CLL24b}, who showed this bound holds when $\epsilon = O(1/d^{12})$. More generally, we show that if $\tr(O_i^2) \leq F$ for all $i$, then \begin{equation*} n = O\Big(\log(m) \cdot \Big(\min\Big\{\frac{\sqrt{r F}}{\epsilon}, \frac{F^{2/3}}{\epsilon^{4/3}}\Big\} + \frac{1}{\epsilon^2}\Big)\Big) \end{equation*} copies suffice to solve this task. This improves on a result of~\cite{GLM24}, who showed a bound of $n = O(\log(m) \cdot \sqrt{rF}/\epsilon^2)$, and disproves a conjecture of~\cite{CLL24b}. \item[$\circ$] Our final application is to the field of quantum metrology. In quantum metrology, one is provided copies of a mixed state $\rho_{\theta}$ parameterized by a vector $\theta \in \R^n$, and the goal is to estimate the parameter $\theta$. An algorithm is \emph{locally unbiased} at a parameter $\theta^*$ if, roughly, it is unbiased given $\rho_{\theta}$ when $\theta$ is in a small neighborhood around $\theta^*$. The quantum Cramér–Rao bound states that the mean squared error matrix (MSEM) of any locally unbiased algorithm is lower bounded by the inverse of the Quantum Fisher Information (QFI) matrix. We give a locally unbiased algorithm whose MSEM is \emph{upper bounded} by twice the inverse of the QFI matrix in the asymptotic limit of large $n$, which is optimal. \end{itemize}

We show that $n = \Omega(rd/\epsilon^2)$ copies are necessary to learn a rank $r$ mixed state $\rho \in \C^{d \times d}$ up to error~$\epsilon$ in trace distance. This matches the upper bound of $n = O(rd/\epsilon^2)$ from~\cite{OW16} and therefore settles the sample complexity of mixed state tomography. We prove this lower bound by studying a special case of full state tomography that we refer to as \emph{projector tomography}, in which $\rho$ is promised to be of the form $\rho = P/r$, where $P \in \C^{d \times d}$ is a rank $r$ projector. A key technical ingredient in our proof, which may be of independent interest, is a reduction which converts any algorithm for projector tomography which learns to error $\epsilon$ in trace distance to an algorithm which learns to error $O(\epsilon)$ in the more stringent Bures distance.

Abstract Boris Tsirelson in 1993 implicitly posed "Tsirelson's Problem", a question about the possible equivalence between two different ways of modeling locality, and hence entanglement, in quantum mechanics. Tsirelson's Problem gained prominence through work of Fritz, Navascues et al., and Ozawa a decade ago that establishes its equivalence to the famous "Connes' Embedding Problem" in the theory of von Neumann algebras. Recently we gave a negative answer to Tsirelson's Problem and Connes' Embedding Problem by proving a seemingly stronger result in quantum complexity theory. This result is summarized in the equation MIP* = RE between two complexity classes. In the talk I will present and motivate Tsirelson's problem, and outline its connection to Connes' Embedding Problem. I will then explain the connection to quantum complexity theory and show how ideas developed in the past two decades in the study of classical and quantum interactive proof systems led to the characterization (which I will explain) MIP* = RE and the negative resolution of Tsirelson's Problem. Based on joint work with Ji, Natarajan, Wright and Yuen available at arXiv:2001.04383.