We provide more sample-efficient versions of some basic routines in quantum data analysis, along with simpler proofs. Particularly, we give a quantum "Threshold Search" algorithm that requires only $O((\log^2 m)/\epsilon^2)$ samples of a $d$-dimensional state $\rho$. That is, given observables $0 \le A_1, A_2, ..., A_m \le 1$ such that $\mathrm{tr}(\rho A_i) \ge 1/2$ for at least one $i$, the algorithm finds $j$ with $\mathrm{tr}(\rho A_j) \ge 1/2-\epsilon$. As a consequence, we obtain a Shadow Tomography algorithm requiring only $\tilde{O}((\log^2 m)(\log d)/\epsilon^4)$ samples, which simultaneously achieves the best known dependence on each parameter $m$, $d$, $\epsilon$. This yields the same sample complexity for quantum Hypothesis Selection among $m$ states; we also give an alternative Hypothesis Selection method using $\tilde{O}((\log^3 m)/\epsilon^2)$ samples.
We provide more sample-efficient versions of some basic routines in quantum data analysis, along with simpler proofs. Particularly, we give a quantum "Threshold Search" algorithm that requires only O((log2m)/ϵ2) samples of a d-dimensional state ρ. That is, given observables 0≤A1,A2,...,Am≤1 such that tr(ρAi)≥1/2 for at least one i, the algorithm finds j with tr(ρAj)≥1/2−ϵ. As a consequence, we obtain a Shadow Tomography algorithm requiring only O~((log2m)(logd)/ϵ4) samples, which simultaneously achieves the best known dependence on each parameter m, d, ϵ. This yields the same sample complexity for quantum Hypothesis Selection among m states; we also give an alternative Hypothesis Selection method using O~((log3m)/ϵ2) samples.
Shadow Tomography is a fundamental problem in quantum information theory. Given multiple copies of an unknown d-dimensional quantum state ρ and a known collection of observables E1,…,EM, the goal is to estimate all expectation values {Tr(ρEi)}i=1M to additive accuracy ε with probability at least 1−δ.
An elusive open question from the seminal shadow tomography work of Aaronson is whether this task admits a dimension-independent sample complexity with only polylogarithmic dependence on M, as suggested by the best-known lower bounds. In this work, we propose two different quantum protocols for shadow tomography with the best sample complexity O(ε2log(M)log(M/δ)), which is polylogarithmic in the number of observables and independent of the dimension of the unknown state, thereby answering Aaronson's original question while also providing an exponential improvement in the prior best dimension independent sample complexity of shadow tomography from Sinha (STOC 2025) and, more recently, Chen, O'Donnell, Pelecanos, and Wright.
Our approach first reduces the general shadow tomography problem to a finite-ensemble estimation problem via a minimax argument. We then develop an observable-independent protocol that repeatedly applies the pretty-good measurement while updating the prior distribution over the finite ensemble according to the measurement outcomes. A tail analysis of the resulting estimation error yields simultaneous accuracy guarantees for all observables and a cubic-logarithmic upper bound. We also introduce a refined recovery-label measurement for the same finite ensemble, which yields the bound in our main theorem.
We provide more sample-efficient versions of some basic routines in quantum data analysis, along with simpler proofs. Particularly, we give a quantum ”Threshold Search” algorithm that requires only O((log2 m)/є2) samples of a d-dimensional state ρ. That is, given observables 0 ≤ A1, A2, …, Am ≤ 1 such that (ρ Ai) ≥ 1/2 for at least one i, the algorithm finds j with (ρ Aj) ≥ 1/2−є. As a consequence, we obtain a Shadow Tomography algorithm requiring only O((log2 m)(logd)/є4) samples, which simultaneously achieves the best known dependence on each parameter m, d, є. This yields the same sample complexity for quantum Hypothesis Selection among m states; we also give an alternative Hypothesis Selection method using O((log3 m)/є2) samples.
We give a shadow tomography algorithm that uses O(log(m)log(m/δ)/ε2) copies of the input state. Specifically, given a quantum state ρ and observables O1,…,Om, the algorithm outputs estimates of tr(Oiρ) for all i∈[m] that are all accurate to within ±ε, except with probability at most δ. The key idea is to work in the average-case setting: for a random state drawn from a known prior, a pretty good measurement on O(log(m)/ε2) copies gives a constant-error guarantee on all but a small fraction of the prior. Boosting this guarantee gives an average-case shadow tomography algorithm, and the minimax principle then (non-constructively) implies the existence of a measurement with the same worst-case guarantee.
We also identify an obstruction to further improvement with this approach. While pretty good measurements amplify success over the randomness of the prior, they do not amplify success over the randomness of measurement. This issue appears to be inherent, and gives rise to the remaining log(m) factor separating the complexity of the quantum problem from its classical counterpart.
In Online Shadow Tomography, we are given copies of an unknown d-dimensional quantum state ρ, an adversary (adaptively) proposes a sequence of bounded observables A(1),…,A(m), and after each A(t) is given we must estimate Tr(A(t)ρ) to within ±ε. This is the direct quantum generalization of the classical problem of Adaptive Data Analysis. Prior results for online Shadow Tomography were suboptimal in all three parameters m,d,ε, lagging behind the best known and classical rates, for which there is some evidence of optimality. In this work, we finally close this gap, giving a pair of algorithms matching the classical rates. Our first algorithm is the first to achieve o(log2m)-dependence together with poly(log(d)/ε); moreover, it improves all three exponents even in the Offline Shadow Tomography setting. Our second algorithm is known to be optimal among bounds independent of d, and improves the best prior result by a mlogm factor.
The key to our proof is a new framework for quantifying post-measurement damage, based on the quantum Efron-Stein decomposition.
We study the sample complexity of shadow tomography in the high-precision regime under realistic measurement constraints. Given an unknown d-dimensional quantum state ρ and a known set of observables {Oi}i=1m, the goal is to estimate expectation values {tr(Oiρ)}i=1m to accuracy ε in Lp-norm, using possibly adaptive measurements that act on O(polylog(d)) number of copies of ρ at a time. We focus on the regime where ε is below an instance-dependent threshold.
Our main contribution is an instance-optimal characterization of the sample complexity as Θ~(Γp/ε2), where Γp is a function of {Oi}i=1m defined via an optimization formula involving the inverse Fisher information matrix. Previously, tight bounds were known only in special cases, e.g. Pauli shadow tomography with L∞-norm error. Concretely, we first analyze a simpler oblivious variant where the goal is to estimate an observable of the form ∑i=1mαiOi with ∥α∥q=1 (where q is dual to p) revealed after the measurement. For single-copy measurements, we obtain a sample complexity of Θ(Γpob/ε2). We then show Θ~(Γp/ε2) is necessary and sufficient for the original problem, with the lower bound applying to unbiased, bounded estimators. Our upper bounds rely on a two-step algorithm combining coarse tomography with local estimation. Notably, Γ∞ob=Γ∞. In both cases, allowing c-copy measurements improves the sample complexity by at most Ω(1/c).
Our results establish a quantitative correspondence between quantum learning and metrology, unifying asymptotic metrological limits with finite-sample learning guarantees.
Following the first paper on quantum algorithms for SDP-solving by Brandão and Svore in 2016, rapid developments has been made on quantum optimization algorithms. Recently Brandão et al. improved the quantum SDP-solver in the so-called quantum state input model, where the input matrices of the SDP are given as purified mixed states. They also gave the first non-trivial application of quantum SDP-solving by obtaining a more efficient algorithm for the problem of shadow tomography (proposed by Aaronson in 2017). In this paper we improve on all previous quantum SDP-solvers. Mainly we construct better Gibbs-samplers for both input models, which directly gives better bounds for SDP-solving. For an SDP with m constraints involving n×n matrices, our improvements yield an O((m+nγ)sγ4) upper bound on SDP-solving in the sparse matrix input model and an O((m+B2.5γ3.5)Bγ4) upper bound in the quantum state input model. We then apply these results to the problem of shadow tomography to simultaneously improve the best known upper bounds on sample complexity due to Aaronson and complexity due Brandao et al. Furthermore, we apply our quantum SDP-solvers to the problems of quantum state discrimination and E-optimal design. In both cases we beat the classical lower bound in terms of some parameters, at the expense of heavy dependence on some other parameters. Finally we prove two lowers bounds for solving SDPs using quantum algorithms: (1) $\tildeΩ(\sqrt{m}B/\eps)$ in the quantum state input model, and (2) $\tildeΩ(\sqrt{m}α/\eps)$ in the quantum operator input model. These lower bounds show that the m factor and the polynomial dependence on the parameters B,α, and $1/\eps$ are necessary.