Lower Bounds for Learning Quantum States with Single-Copy Measurements

Abstract

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 a known lower bound due to Haah et al. (2017) on quantum tomography with accuracy $\epsilon$ in trace distance, when the measurements choices are independent of previously observed outcomes (i.e., they are nonadaptive). We give a succinct proof of this result. This leads to stronger lower bounds when the learner uses measurements with a constant number of outcomes. 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 $\Omega (r^{2}d/{\epsilon }^2)$ and $\Omega (r^2{d}^2/{\epsilon }^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 different measurements used by an algorithm. We extend our lower bounds to the case where the learner performs possibly adaptive measurements from a fixed set of $\exp (O(d))$ 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.

v3. Minor typos fixed and references to subsequent work added. Most of the results in this article were included in the first author's Master's thesis at U. Waterloo (Oct. 2021) and were presented at QIP 2022 (Mar. 2022)

References in corpus (22)

• Improved Simulation of Stabilizer Circuits
• Predicting Many Properties of a Quantum System from Very Few Measurements
• Chaos and complexity by design
• Quantum Tomography via Compressed Sensing: Error Bounds, Sample Complexity, and Efficient Estimators
• Aspects of generic entanglement
• $f$-divergence Inequalities
• Information-theoretic bounds on quantum advantage in machine learning
• The quantum capacity of channels with arbitrarily correlated noise
• Multiqubit Clifford groups are unitary 3-designs
• Adaptive Bayesian Quantum Tomography
• Sample-optimal tomography of quantum states
• Adaptive quantum state tomography improves accuracy quadratically
• Quantum Algorithmic Measurement
• Experimental Estimation of Quantum State Properties from Classical Shadows
• Distributed quantum inner product estimation
• Online Learning of Quantum States
• Short Multi-Prover Quantum Proofs for SAT without Entangled Measurements
• Quantum chi-squared tomography and mutual information testing
• Entanglement and fermionization of two distinguishable fermions in a strict and non strict one-dimensional space
• A Hierarchy for Replica Quantum Advantage
• Limitations of Quantum Coset States for Graph Isomorphism
• Tight Bounds for Quantum State Certification with Incoherent Measurements

Cited by in corpus (2)

• Pseudorandom density matrices
• One, Two, Three: One empirical evaluation of a two-copy shadow tomography scheme with triple efficiency