We show that Ω(rd/ϵ) copies of an unknown rank- r , dimension- d quantum mixed state are necessary in order to learn a classical description with 1–ϵ fidelity. This improves upon the tomography lower bounds obtained by Haah, et al. and Wright (when closeness is measured with respect to the fidelity function).
We show that n=Ω(rd/ε2) copies are necessary to learn a rank r mixed state ρ∈Cd×d up to error ε in trace distance. This matches the upper bound of n=O(rd/ε2) from prior work, and therefore settles the sample complexity of mixed state tomography. We prove this lower bound by studying a special case of full state tomography that we refer to as projector tomography, in which ρ is promised to be of the form ρ=P/r, where P∈Cd×d is a rank r projector. A key technical ingredient in our proof, which may be of independent interest, is a reduction which converts any algorithm for projector tomography which learns to error ε in trace distance to an algorithm which learns to error O(ε) in the more stringent Bures distance.
We describe algorithms to obtain an approximate classical description of a d-dimensional quantum state when given access to a unitary (and its inverse) that prepares it. For pure states we characterize the query complexity for ℓq-norm error up to logarithmic factors. As a special case, we show that it takes applications of the unitaries to obtain an ε-ℓ2-approximation of the state. For mixed states we consider a similar model, where the unitary prepares a purification of the state. We characterize the query complexity for obtaining Schatten q-norm estimates of a rank-r mixed state, up to polylogarithmic factors. In particular, we show that a trace-norm (q = 1) estimate can be obtained with queries. This improves (assuming our stronger input model) the ε-dependence over the works of O'Donnell and Wright (STOC 2016) and Haah et al. (IEEE Trans. Inf. Theory, 63.9, 2017), that use a joint measurement on copies of the state. To our knowledge, the most sample-efficient results for pure-state tomography come from setting the rank to 1 in generic mixed-state tomography algorithms, which can require a large amount of computing resources. We describe sample-optimal algorithms for pure states that are simple and fast to implement. Along the way we show that an ℓ∞-norm estimate of a normalized vector induces a (slightly worse) ℓq-norm estimate for that vector, without losing a dimension-dependent factor in the precision. We also develop an unbiased and symmetric version of phase estimation, where the probability distribution of the estimate is centered around the true value. Finally, we give an efficient method for estimating multiple expectation values, improving over the recent result by Huggins et al. (arXiv:2111.09283) when the measurement operators do not fully overlap. More specifically, we show that for E1,…, Em normalized measurement operators, all expectation values Tr(Ejρ) can be efficiently learned up to error ε with applications of a state-preparation unitary for a purification of ρ. * The full version of the paper can be accessed at https://arxiv.org/abs/2207.08800
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.
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.
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/ϵ) .
A longstanding belief in quantum tomography is that estimating a mixed state is far harder than estimating a pure state. This is borne out in the mathematics, where mixed state algorithms have always required more sophisticated techniques to design and analyze than pure state algorithms. We present a new approach to tomography demonstrating that, contrary to this belief, state-of-the-art mixed state tomography follows easily and naturally from pure state algorithms.
We analyze the following strategy: given n copies of an unknown state ρ, convert them into copies of a purification ∣ρ⟩; run a pure state tomography algorithm to produce an estimate of ∣ρ⟩; and output the resulting estimate of ρ. The purification subroutine was recently discovered via the "acorn trick" of Tang, Wright, and Zhandry. With this strategy, we obtain the first tomography algorithm which is sample-optimal in all parameters. For a rank-rd-dimensional state, it uses n=O((rd+log(1/δ))/ε) samples to output an estimate which is ε-close in fidelity with probability at least 1−δ. This algorithm also uses poly(n) gates, making it the first gate-efficient tomography algorithm which is sample-optimal even in terms of the dimension d alone. Moreover, with this method we recover essentially all results on mixed state tomography, including its applications to tomography with limited entanglement, classical shadows, and quantum metrology. Our proofs are simple, closing the gap in conceptual difficulty between mixed and pure tomography. Our results also clarify the role of entangled measurement in mixed state tomography: the only step of the algorithm which requires entanglement across copies is the purification step, suggesting that, for tomography, the reason entanglement is useful is for consistent purification.