How many copies of a mixed state \(\rho \in \mathbb{C}^{d \times d}\) are needed to learn its spectrum? To date, the best known algorithms for spectrum estimation require as many copies as full state tomography, suggesting the possibility that learning a state's spectrum might be as difficult as learning the entire state. We show that this is not the case in the setting of unentangled measurements, by giving a spectrum estimation algorithm that uses \(n = O\left(d^{3} \cdot (\log \log(d) / \log(d))^{4}\right)\) copies of \(\rho\), which is asymptotically fewer than the \(n = \Omega(d^{3})\) copies necessary for full state tomography. Our algorithm is inspired by the technique of local moment matching from classical statistics, and shows how it can be applied in the quantum setting.

In the problem of quantum state tomography, one is given n copies of an unknown rank-r mixed state ρ ∈ ℂd × d and asked to produce an estimator of ρ. In this work, we present the debiased Keyl’s algorithm, the first estimator for full state tomography which is both unbiased and sample-optimal. We derive an explicit formula for the second moment of our estimator, with which we show the following five applications. First, we give a new proof that n = O(rd/ε2) copies are sufficient to learn a rank-r mixed state to trace distance error ε, which is optimal. Second, we show that n = O(rd/ε2) copies are sufficient to learn to error ε in the more challenging Bures distance, which is also optimal. Third, we consider full state tomography when one is only allowed to measure k copies at once. We show that n =O(max(d3/√kε2, d2/ε2 ) ) copies suffice to learn in trace distance. This improves on the prior work of Chen et al. and matches their lower bound. Fourth, for shadow tomography, we show that O(log(m)/ε2) copies are sufficient to learn m given observables O1, …, Om in the ”high accuracy regime”, when ε = O(1/d), improving on a result of Chen et al. More generally, we show that if tr(Oi2) ≤ F for all i, then n = O(log(m) · (min{√r F/ε, F2/3/ε4/3}+ 1/ε2)) copies suffice, improving on existing work. Finally, for quantum metrology, we give a locally unbiased algorithm whose mean squared error matrix is upper bounded by twice the inverse of the quantum Fisher information matrix in the asymptotic limit of large n, which is optimal.

We prove that the permutation computed by a reversible circuit with Õ (nk · log(1/ε )) random 3-bit gates is ε-approximately k-wise independent. Our bound improves on currently known bounds in the regime when the approximation error ε is not too small and is optimal up to logarithmic factors when ε is a constant. We obtain our results by analyzing the log-Sobolev constants of appropriate Markov chains rather than their spectral gaps.

It is a long-standing open question to construct a classical oracle relative to which BQP/qpoly $\neq$ BQP/poly or QMA $\neq$ QCMA. In this paper, we construct classically-accessible classical oracles relative to which BQP/qpoly $\neq$ BQP/poly and QMA $\neq$ QCMA. Here, classically-accessible classical oracles are oracles that can be accessed only classically even for quantum algorithms. Based on a similar technique, we also show an alternative proof for the separation of QMA and QCMA relative to a distributional quantumly-accessible classical oracle, which was recently shown by Natarajan and Nirkhe.