We show that entangled measurements provide an exponential advantage in sample complexity for Pauli channel estimation, which is both a fundamental problem and a practically important subroutine for benchmarking near-term quantum devices. The specifi
c task we consider is to learn the eigenvalues of an $n$-qubit Pauli channel to precision $varepsilon$ in $l_infty$ distance. We give an estimation protocol with an $n$-qubit ancilla that succeeds with high probability using only $O(n/varepsilon^{2})$ copies of the Pauli channel, while prove that any ancilla-free protocol (possibly with adaptive control and channel concatenation) would need at least $Omega(2^{n/3})$ rounds of measurement. We further study the advantages provided by a small number of ancillas. For the case that a $k$-qubit ancilla ($kle n$) is available, we obtain a sample complexity lower bound of $Omega(2^{(n-k)/3})$ for any non-concatenating protcol, and a stronger lower bound of $Omega(n2^{n-k})$ for any non-adaptive, non-concatenating protocol. The latter is shown to be tight by explicitly constructing a $k$-qubit-ancilla-assisted estimation protocol. We also show how to apply the ancilla-assisted estimation protocol to a practical quantum benchmarking task in a noise-resilient and sample-efficient manner, given reasonable noise assumptions. Our results provide a practically-interesting example for quantum advantages in property learning and also bring new insight for quantum benchmarking.
Efficiently estimating properties of large and strongly coupled quantum systems is a central focus in many-body physics and quantum information theory. While quantum computers promise speedups for many such tasks, near-term devices are prone to noise
that will generally reduce the accuracy of such estimates. Here we show how to mitigate errors in the shadow estimation protocol recently proposed by Huang, Kueng, and Preskill. By adding an experimentally friendly calibration stage to the standard shadow estimation scheme, our robust shadow estimation algorithm can obtain an unbiased estimate of the classical shadow of a quantum system and hence extract many useful properties in a sample-efficient and noise-resilient manner given only minimal assumptions on the experimental conditions. We give rigorous bounds on the sample complexity of our protocol and demonstrate its performance with several numerical experiments.
