We present a two-step protocol for quantum measurement tomography that is light on classical co-processing cost and still achieves optimal sample complexity. Given measurement data from a known probe state ensemble, we first apply least-squares estimation to produce an unconstrained approximation of the POVM, and then project this estimate onto the set of valid quantum measurements. For a POVM with L outcomes acting on a d -dimensional system, we show that the protocol requires O ( ( d 3 + d 2 L ) / ϵ 2 ) samples to achieve error ϵ in worst-case distance, and O ( d 2 L / ϵ 2 ) samples in average-case distance. We further establish two matching sample complexity lower bounds of Ω ( ( d 3 + d 2 L ) / ϵ 2 ) and Ω ( d 2 L / ϵ 2 ) for any non-adaptive, single-copy POVM tomography protocol. Hence, our projected least squares POVM tomography is sample-optimal in both the dimension and the number of outcomes for both distances. Our method admits an analytic form when using global or local 2-designs as probe ensembles and enables rigorous non-asymptotic error guarantees. Finally, we also complement our findings with empirical performance studies carried out on a noisy superconducting quantum computer with flux-tunable transmon qubits.
We present a two-step protocol for quantum measurement tomography that is light on classical co-processing cost and still achieves optimal sample complexity. Given measurement data from a known probe state ensemble, we first apply least-squares estimation to produce an unconstrained approximation of the POVM, and then project this estimate onto the set of valid quantum measurements. For a POVM with L outcomes acting on a d -dimensional system, we show that the protocol requires O ( ( d 3 + d 2 L ) / ϵ 2 ) samples to achieve error ϵ in worst-case distance, and O ( d 2 L / ϵ 2 ) samples in average-case distance. We further establish two matching sample complexity lower bounds of Ω ( ( d 3 + d 2 L ) / ϵ 2 ) and Ω ( d 2 L / ϵ 2 ) for any non-adaptive, single-copy POVM tomography protocol. Hence, our projected least squares POVM tomography is sample-optimal in both the dimension and the number of outcomes for both distances. Our method admits an analytic form when using global or local 2-designs as probe ensembles and enables rigorous non-asymptotic error guarantees. Finally, we also complement our findings with empirical performance studies carried out on a noisy superconducting quantum computer with flux-tunable transmon qubits.
Projected least squares is an intuitive and numerically cheap technique for quantum state tomography: compute the least-squares estimator and project it onto the space of states. The main result of this paper equips this point estimator with rigorous, non-asymptotic convergence guarantees expressed in terms of the trace distance. The estimator's sample complexity is comparable to the strongest convergence guarantees available in the literature and—in the case of the uniform POVM—saturates fundamental lower bounds. Numerical simulations support these competitive features.
Abstract Projected least squares is an intuitive and numerically cheap technique for quantum state tomography: compute the least-squares estimator and project it onto the space of states. The main result of this paper equips this point estimator with rigorous, non-asymptotic convergence guarantees expressed in terms of the trace distance. The estimator’s sample complexity is comparable to the strongest convergence guarantees available in the literature and—in the case of the uniform POVM—saturates fundamental lower bounds. Numerical simulations support these competitive features.
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.
Quantum state and process tomography are typically analyzed under the assumption that devices emit independent and identically distributed (i.i.d.) states or channels. In realistic experiments, however, noise, drift, feedback, or adversarial behavior violate this assumption. We show that projected least-squares tomography remains statistically optimal even under fully adaptive state and channel preparation. Specifically, we prove that the sample complexity for reconstructing the time-averaged state or channel matches the optimal i.i.d. scaling for non-adaptive, single-copy measurements. For rank-r states, the sample complexity is O(dr2/ε2) to achieve accuracy ε in trace distance, while for process tomography it is O(d6/ε2) to achieve accuracy ε in diamond distance. Thus, dropping the i.i.d. assumption does not increase the fundamental sample complexity of quantum tomography, but only changes the interpretation of the reconstructed object.
Quantum state tomography is a fundamental problem in quantum computing. Given n copies of an unknown N -qubit state ρ∈ℂ d × d , d =2 N , the goal is to learn the state up to an accuracy ε in trace distance, say with at least constant probability 0.99. We are interested in the copy complexity, the minimum number of copies of ρ needed to fulfill the task. As current quantum devices are physically limited, Pauli measurements have attracted significant attention due to their ease of implementation. However, a large gap exists in the literature for tomography with Pauli measurements. The best-known upper bound is O ( N · 12 N /ε 2 ), and no non-trivial lower bound is known besides the general single-copy lower bound of Ω(8 N /ε 2 ), achieved by hard-to-implement structured POVMs such as MUB, SIC-POVM, and uniform POVM. We have made significant progress on this long-standing problem. We first prove a stronger upper bound of O (10 N /ε 2 ). To complement it, we also obtain a lower bound of Ω(9.118 N /ε 2 ), which holds even with adaptivity. To our knowledge, this demonstrates the first known separation between Pauli measurements and structured POVMs. The new lower bound is a consequence of a novel framework for adaptive quantum state tomography with measurement constraints. The main advantage is that we can use measurement-dependent hard instances to prove tight lower bounds for Pauli measurements, while prior lower-bound techniques for tomography only work with measurement-independent constructions. Moreover, we connect the copy complexity lower bound of tomography to the eigenvalues of the measurement information channel, which governs the measurement’s capacity to distinguish between states. To demonstrate the generality of the new framework, we obtain tight bounds for adaptive quantum state tomography with k -outcome measurements, where we recover existing results and establish new ones.
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.