A minimax estimator has the minimum possible error ("risk") in the worst case. We construct the first minimax estimators for quantum state tomography with relative entropy risk. The minimax risk of nonadaptive tomography scales as O(1/sqrt[N])-in contrast to that of classical probability estimation, which is O(1/N)-where N is the number of copies of the quantum state used. We trace this deficiency to sampling mismatch: future observations that determine risk may come from a different sample space than the past data that determine the estimate. This makes minimax estimators very biased, and we propose a computationally tractable alternative with similar behavior in the worst case, but superior accuracy on most states.
A minimax estimator has the minimum possible error ("risk") in the worst case. We construct the first minimax estimators for quantum state tomography with relative entropy risk. The minimax risk of nonadaptive tomography scales as O(1/sqrt[N])-in contrast to that of classical probability estimation, which is O(1/N)-where N is the number of copies of the quantum state used. We trace this deficiency to sampling mismatch: future observations that determine risk may come from a different sample space than the past data that determine the estimate. This makes minimax estimators very biased, and we propose a computationally tractable alternative with similar behavior in the worst case, but superior accuracy on most states.
We investigate minimax estimators for quantum state tomography under general Bregman divergences. First, generalizing the work of Koyama et al. [Entropy 19, 618 (2017)] for relative entropy, we find that given any estimator for a quantum state, there always exists a sequence of Bayes estimators that asymptotically perform at least as well as the given estimator, on any state. Second, we show that there always exists a sequence of priors for which the corresponding sequence of Bayes estimators is asymptotically minimax (i.e. it minimizes the worst-case risk). Third, by re-formulating Holevo's theorem for the covariant state estimation problem in terms of estimators, we find that there exists a covariant measurement that is, in fact, minimax (i.e. it minimizes the worst-case risk). Moreover, we find that a measurement that is covariant only under a unitary 2-design is also minimax. Lastly, in an attempt to understand the problem of finding minimax measurements for general state estimation, we study the qubit case in detail and find that every spherical 2-design is a minimax measurement.
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 investigate minimax estimators for quantum state tomography under general Bregman divergences. First, generalizing the work of Komaki et al. hrefhttp://dx.doi.org/10.3390/e19110618textrm[Entropy19,618(2017)] for relative entropy, we find that given any estimator for a quantum state, there always exists a sequence of Bayes estimators that asymptotically perform at least as well as the given estimator, on any state. Second, we show that there always exists a sequence of priors for which the corresponding sequence of Bayes estimators is asymptotically minimax (i.e. it minimizes the worst-case risk). Third, by re-formulating Holevo's theorem for the covariant state estimation problem in terms of estimators, we find that any covariant measurement is, in fact, minimax (i.e. it minimizes the worst-case risk). Moreover, we find that a measurement is minimax if it is only covariant under a unitary 2-design. Lastly, in an attempt to understand the problem of finding minimax measurements for general state estimation, we study the qubit case in detail and find that every spherical 2-design is a minimax measurement.
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.
The problem of quantum tomography is to estimate an unknown quantum state ρ from a measurement of n copies of ρ. One can ask which tomography protocol, i.e.\ which choice of multi-copy measurement, gives the best possible estimate of ρ. To do so, we characterize tomography protocols by their \emph{rate function}, which governs the exponential rate at which a protocol assigns probability to a particular estimate σ of the true state ρ. This rate function is a quantum mechanical generalization of the classical relative entropy between the true state and its estimate, and depends on the choice of protocol. It is bounded by the quantum relative entropy, and we show that this bound is sharp: for any ρ and σ we construct a family of protocols whose rate functions converge to the quantum relative entropy D(σ∥ρ).
We consider the family of covariant tomography protocols; these are the basis independent state estimation schemes that assume no prior information about ρ and σ. Keyl described a specific tomography protocol based on Schur sampling, and conjectured that among all covariant tomography protocols it has the largest possible rate function for all σ and ρ. We prove this conjecture. The resulting rate function is an annealed version of quantum relative entropy, due to the cost of learning the eigenbasis in covariant quantum state tomography.
Quantum tomography requires repeated measurements of many copies of the physical system, all prepared by a source in the unknown state. In the limit of very many copies measured, the often-used maximum-likelihood (ML) method for converting the gathered data into an estimate of the state works very well. For smaller data sets, however, it often suffers from problems of rank deficiency in the estimated state. For many systems of relevance for quantum information processing, the preparation of a very large number of copies of the same quantum state is still a technological challenge, which motivates us to look for estimation strategies that perform well even when there is not much data. In this article, we review the concept of minimax state estimation, and use minimax ideas to construct a simple estimator for quantum states. We demonstrate that, for the case of tomography of a single qubit, our estimator significantly outperforms the ML estimator for small number of copies of the state measured. Our estimator is always full-rank, and furthermore, has a natural dependence on the number of copies measured, which is missing in the ML estimator.