Predicting quantum channels over general product distributions

Abstract

We investigate the problem of predicting the output behavior of unknown quantum channels. Given query access to an n-qubit channel ℰ and an observable 𝒪, we aim to learn the mapping ρ↦(𝒪ℰ[ρ]) to within a small error for most ρ sampled from a distribution 𝒟. Previously, Huang et al. proved a surprising result that even if ℰ is arbitrary, this task can be solved in time roughly n^O(log(1/ϵ)), where ϵ is the target prediction error. However, their guarantee applied only to input distributions 𝒟 invariant under all single-qubit Clifford gates, and their algorithm fails for important cases such as general product distributions over product states ρ. In this work, we propose a new approach that achieves accurate prediction over essentially any product distribution 𝒟, provided it is not “classical” in which case there is a trivial exponential lower bound. Our method employs a “biased Pauli analysis,” analogous to classical biased Fourier analysis. Implementing this approach requires overcoming several challenges unique to the quantum setting, including the lack of a basis with appropriate orthogonality properties. The techniques we develop to address these issues may have broader applications in quantum information.