Dimension Independent and Computationally Efficient Shadow Tomography

We describe a new shadow tomography algorithm that uses n=Θ(√mlogm/є2) samples, for m measurements and additive error є, which is independent of the dimension of the quantum state being learned. This stands in contrast to all previously known algorithms that improve upon the naive approach. The sample complexity also has optimal dependence on є. Due to its dimension independent nature, this algorithm has the best known sample complexity in the regime m=o(log2 d) (when є is chosen independently from d). Additionally, this algorithm is efficient in various aspects, including quantum memory usage (possibly even O(1)), gate complexity, classical computation, all of which are also do not have any dimension dependence. This algorithm is also robust against qubit measurement noise, by which we mean that the qubit measurement errors can only affect the accuracy of the estimates, and small noise leads to small additive error in the estimates. Apart from this, the algorithm can be modified to also be implementable as a read-once quantum circuit with low quantum memory usage, i.e., it will hold only one copy of ρ in memory, and discard it before asking for a new one, with the additional quantum memory needed being O(mlogn) qubits. Our approach builds on the idea of using noisy measurements, but instead of focusing on gentleness in trace distance, we focus on the gentleness in shadows, i.e., we show that the noisy measurements do not significantly perturb the expected values. To work with this, we think of noisy measurements as measuring a noisy encoding of the quantity we are trying to noisily measure. In our case, these are the observables corresponding to sample means of the m POVMs. We see that the product state structure of the samples is effectively maintained (with possibly some additional randomness) even after the creation and tracing out of the specific noisy encodings we work with.