Quantum state tomography provides a foundation for characterizing state preparation and predicting measurement outcomes. We characterize the minimax expected trace norm risk of quantum state tomography over classes with polynomial spectral decay under randomized nonadaptive single copy measurements. Under an explicit sufficient block size condition for the two layer periodic Clifford ensemble, we establish statewise expected trace norm oracle inequalities for operator norm minimum distance and measurement weighted projected least squares, with bounds that depend on each state's actual spectral tail, while the estimators require no prior knowledge of the state's structural characteristics, including its rank, eigenbasis, or spectral structure. Over these polynomial spectral decay classes, both estimators attain the minimax expected trace norm rates up to constants. As a direct consequence, the same estimators attain the minimax rate over every fixed rank constrained class, while remaining adaptive to the unknown structural characteristics of the state. For admissible logarithmic block sizes, the periodic Clifford measurements attain these guarantees with logarithmic elementary gate depth. The main technical ingredient is a uniform bound on the fourth moment of projectors for the periodic Clifford ensemble. The bound is sharp in dimension and holds for arbitrary test states, including those entangled across blocks. Covariance concentration and positivity yield adaptive oracle bounds, while a shared rotation information argument on spectral tail packings establishes matching lower bounds. We also provide polynomial time reconstruction algorithms, numerical comparisons, and Lean formalizations of all labeled theoretical results.
Quantum state tomography provides a foundation for characterizing state preparation and predicting measurement outcomes. We characterize the minimax expected trace norm risk of quantum state tomography over classes with polynomial spectral decay under randomized nonadaptive single copy measurements. Under an explicit sufficient block size condition for the two layer periodic Clifford ensemble, we establish statewise expected trace norm oracle inequalities for operator norm minimum distance and measurement weighted projected least squares, with bounds that depend on each state's actual spectral tail, while the estimators require no prior knowledge of the state's structural characteristics, including its rank, eigenbasis, or spectral structure. Over these polynomial spectral decay classes, both estimators attain the minimax expected trace norm rates up to constants. As a direct consequence, the same estimators attain the minimax rate over every fixed rank constrained class, while remaining adaptive to the unknown structural characteristics of the state. For admissible logarithmic block sizes, the periodic Clifford measurements attain these guarantees with logarithmic elementary gate depth. The main technical ingredient is a uniform bound on the fourth moment of projectors for the periodic Clifford ensemble. The bound is sharp in dimension and holds for arbitrary test states, including those entangled across blocks. Covariance concentration and positivity yield adaptive oracle bounds, while a shared rotation information argument on spectral tail packings establishes matching lower bounds. We also provide polynomial time reconstruction algorithms, numerical comparisons, and Lean formalizations of all labeled theoretical results.
We study quantum state tomography when the unknown state lies in a trace-distance ball of radius R around a known reference state ρ. For arbitrary collective measurements, we determine the minimax expected risk and confidence radius up to universal constants, uniformly over the dimension, center spectrum, radius, and sample size. Write Γ=d(Trρ)2+d2R. For d≥2, 0<R≤1, and n≥1 copies, the expected risk is Θ(min{R,Γ/n}). At failure probability 0<δ≤1/3, the minimax confidence radius is Θ(min{R,nΓ+log(1/δ)}). For ε≤c0R with a universal c0>0, the copy complexity is Θ((Γ+log(1/δ))/ε2). For the lower bound we use a weighted trace-norm witness to retain all spectral scales in a square-root perturbation family. For the upper bound, we give a direct spectral and concentration analysis of a modified existing purification-based procedure.
We determine the optimal sample complexity of low-rank quantum state tomography when each measurement may act jointly on at most t samples. For sufficiently small ε, estimating an unknown state on Cd of rank at most r to trace norm error ε with constant success probability requires, and is achievable with, Θ(ε2drmax{1,tr}) samples. The lower bound allows the protocol to choose each joint measurement adaptively using all previous classical outcomes; the matching upper bound is nonadaptive. Thus joint measurements on at most t samples improve the complexity of algorithms making single-sample measurements by at most a factor t. Further, measuring order r2 samples jointly is necessary and sufficient to attain the unrestricted collective rate.
For the lower bound, we vary the support of a state with fixed uniform spectrum and bound the Fisher information trace of every joint measurement on t samples. The adaptive Fisher chain rule and the van Trees inequality then give the trace norm lower bound. For the upper bound, we construct and analyze a nonadaptive tomography protocol based on a Gaussian joint measurement. An explicit second moment identity and a conditional Gaussian law outside the state's support give a rank-dependent error analysis, yielding the matching rate.
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 study state tomography when each measurement acts on at most k fresh copies and no quantum memory is retained between blocks. We prove a lower bound matching the upper bound in [arXiv:2510.07788]. Thus the copy complexity of estimating an arbitrary d-dimensional state to trace distance ε is, up to absolute constant factors, max{d3/(kε2),d2/ε2} for every k and all sufficiently small ε. This removes the earlier restriction that k be small as a function of the accuracy. The lower bound applies to arbitrary measurements within each block and adaptive choices between blocks. The lower bound already applies in a small neighborhood of any state whose smallest eigenvalue is of order 1/d, even when the center is known.
The main ingredient is a uniform Fisher information bound for one measurement block that depends only on the smallest eigenvalue of the state. The proof avoids the perturbative expansion responsible for the restriction in [arXiv:2402.16353]. Fano's inequality for metric balls and a log-Sobolev comparison between mutual and Fisher information then reduce the adaptive protocol to this block bound [arXiv:1607.00550, arXiv:1902.08582].
Quantum state tomography estimates an unknown density operator from measurement data. Dense reconstruction however, can be impractical for many-qubit systems because the Hilbert-space dimension grows exponentially. This contribution develops a rank-adaptive matrix-free approach to low-rank quantum state tomography based on rank-one atomic coordinates. The density operator is represented as a convex combination of pure-state atoms, which preserves positivity and unit trace while avoiding dense density, measurement, and gradient matrices. The resultant algorithm combines atom updates, simplex-constrained coefficient reweighting, and periodic spectral refactorization using only predicted probability vectors, atom vectors, and descriptor-level measurement actions. These computations decompose across measurement outcomes, and admit a master--worker implementation with the measurements partitioned across workers. A rank penalty adapts the representation size during optimization. Provable feasibility, prediction consistency, monotone descent of the penalized objective, and an exact spectral proximal characterization of the refactorization step are established. Simulations with Pauli measurements show favorable accuracy--runtime--memory tradeoffs relative to competing alternatives.
We study the problems of quantum tomography and shadow tomography using measurements performed on individual, identical copies of an unknown d -dimensional state. We first revisit known lower bounds [ 23 ] on quantum tomography with accuracy ε in trace distance, when the measurement choices are independent of previously observed outcomes, i.e., they are nonadaptive. We give a succinct proof of these results through the χ 2 -divergence between suitable distributions. Unlike prior work, we do not require that the measurements be given by rank-one operators. This leads to stronger lower bounds when the learner uses measurements with a constant number of outcomes (e.g., two-outcome measurements). In particular, this rigorously establishes the optimality of the folklore “Pauli tomography” algorithm in terms of its sample complexity. We also derive novel bounds of Ω(r2d/ϵ2) and Ω(r2d2/ϵ2) for learning rank r states using arbitrary and constant-outcome measurements, respectively, in the nonadaptive case. In addition to the sample complexity, a resource of practical significance for learning quantum states is the number of unique measurement settings required (i.e., the number of different measurements used by an algorithm, each possibly with an arbitrary number of outcomes). Motivated by this consideration, we employ concentration of measure of χ 2 -divergence of suitable distributions to extend our lower bounds to the case where the learner performs possibly adaptive measurements from a fixed set of exp(O(d)) possible measurements. This implies in particular that adaptivity does not give us any advantage using single-copy measurements that are efficiently implementable. We also obtain a similar bound in the case where the goal is to predict the expectation values of a given sequence of observables, a task known as shadow tomography. Finally, in the case of adaptive, single-copy measurements implementable with polynomial-size circuits, we prove that a straightforward strategy based on computing sample means of the given observables is optimal.