Quantum advantages for Pauli channel estimation

Understand

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 specific task we consider is to simultaneously learn all the eigenvalues of an $n$-qubit Pauli channel to $\pm\varepsilon$ precision.
• 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.