Quantum advantages for Pauli channel estimation

An important challenge for the NISQ era is to demonstrate a practical quantum advantage. In this work, we show that quantum resources provide an exponential advantage in sample complexity for Pauli channel estimation, which is both a fundamental problem and an important subroutine for benchmarking near-term quantum devices. The specific task we consider is to simultaneously learn all the eigenvalues of an n-qubit Pauli channel to ε precision. We give an estimation protocol with an n-qubit ancilla that succeeds with high probability using only O(n/ε²) copies of the Pauli channel, while proving that any ancilla-free protocol (possibly with adaptive control and channel concatenation) would need at least Ω(2^n/3) rounds of measurement. We further study the advantages provided by a small amount of ancilla: For the case that a k-qubit ancilla (k≤n) is available, we obtain a sample complexity lower bound of Ω(2^(n-k)/3) for any non-concatenating protocol, and a stronger lower bound of Ω(2^n-k) for any non-adaptive non-concatenating protocol, which is shown to be tight. We then show how to apply the ancilla-assisted protocol to a practical quantum device characterization task in a noise-resilient and sample-efficient manner. Our results provide a practically interesting example for quantum advantages in learning, and also bring new insight for quantum device characterization.