Learning Distributions over Quantum Measurement Outcomes
share
Shadow tomography for quantum states provides a sample efficient approach for predicting the properties of quantum systems when the properties are restricted to expectation values of 2-outcome POVMs. However, these shadow tomography procedures yield poor bounds if there are more than 2 outcomes per measurement. In this paper, we consider a general problem of learning properties from unknown quantum states: given an unknown d-dimensional quantum state ρ and M unknown quantum measurements ℳ_1,...,ℳ_M with K≥ 2 outcomes, estimating the probability distribution for applying ℳ_i on ρ to within total variation distance ϵ. Compared to the special case when K=2, we need to learn unknown distributions instead of values. We develop an online shadow tomography procedure that solves this problem with high success probability requiring Õ(Klog^2Mlog d/ϵ^4) copies of ρ. We further prove an information-theoretic lower bound that at least Ω(min{d^2,K+log M}/ϵ^2) copies of ρ are required to solve this problem with high success probability. Our shadow tomography procedure requires sample complexity with only logarithmic dependence on M and d and is sample-optimal for the dependence on K.
READ FULL TEXT
