For quantum state tomography on rank- r dimension- d states, we show that O~(r.5d1.5/ϵ)≤O~(d2/ϵ) copies suffice for accuracy ϵ with respect to (Bures) χ2 -divergence, and O~(rd/ϵ) copies suffice for accuracy ϵ with respect to quantum relative entropy. The best previous bound was O~(rd/ϵ)≤O~(d2/ϵ) with respect to infidelity; our results are an improvement since infidelity is bounded above by both the relative entropy and the χ2 -divergence. For algorithms that are required to use single-copy measurements, we show that O~(r1.5d1.5/ϵ)≤O~(d3/ϵ) copies suffice for χ2 -divergence, and O~(r2d/ϵ) suffice for relative entropy.Using this tomography algorithm, we show that O~(d2.5/ϵ) copies of a d×d -dimensional bipartite state suffice to test if it has quantum mutual information 0 or at least ϵ . As a corollary, we also improve the best known sample complexity for the classical version of mutual information testing to O~(d/ϵ) .
In the quantum state tomography problem, one wishes to estimate an unknown d-dimensional mixed quantum state ρ, given few copies. We show that O(d/ε) copies suffice to obtain an estimate ρ that satisfies ||ρ − ρ||F2 ≤ ε (with high probability). An immediate consequence is that O((ρ) · d/ε2) ≤ O(d2/ε2) copies suffice to obtain an ε-accurate estimate in the standard trace distance. This improves on the best known prior result of O(d3/ε2) copies for full tomography, and even on the best known prior result of O(d2log(d/ε)/ε2) copies for spectrum estimation. Our result is the first to show that nontrivial tomography can be obtained using a number of copies that is just linear in the dimension.
It is a fundamental problem to decide how many copies of an unknown mixed quantum state are necessary and sufficient to determine the state. Previously, it was known only that estimating states to error ε in trace distance required O(dr2/ε2) copies for a d-dimensional density matrix of rank r. Here, we give a theoretical measurement scheme (POVM) that requires O(dr/δ)ln (d/δ) copies to estimate ρ to error δ in infidelity, and a matching lower bound up to logarithmic factors. This implies O((dr/ε2)ln (d/ε)) copies suffice to achieve error ε in trace distance. We also prove that for independent (product) measurements, Ω(dr2/δ2)/ ln(1/δ) copies are necessary in order to achieve error δ in infidelity. For fixed d, our measurement can be implemented on a quantum computer in time polynomial in n.
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.
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.
In this paper, we study the quantum identity testing problem, i.e., testing whether two given quantum states are identical, and quantum independence testing problem, i.e., testing whether a given multipartite quantum state is in tensor product form. For the quantum identity testing problem of 𝒟(ℂ^d) system, we provide a deterministic measurement scheme that uses 𝒪(d²/ε²) copies via independent measurements with d being the dimension of the state and ε being the additive error. For the independence testing problem 𝒟(ℂ^d₁⊗ℂ^{d₂}⊗⋯⊗ℂ^{d_m}) system, we show that the sample complexity is Θ̃((Π_{i = 1}^m d_i)/ε²) via collective measurements, and 𝒪((Π_{i = 1}^m d_i²)/ε²) via independent measurements. If randomized choice of independent measurements are allowed, the sample complexity is Θ(d^{3/2}/ε²) for the quantum identity testing problem, and Θ̃((Π_{i = 1}^m d_i^{3/2})/ε²) for the quantum independence testing problem.