Efficient Pauli channel estimation with logarithmic quantum memory

Understand

Here we revisit one of the prototypical tasks for characterizing the structure of noise in quantum devices: estimating every eigenvalue of an $n$-qubit Pauli noise channel to error $\epsilon$.

• Prior work [14] proved no-go theorems for this task in the practical regime where one has a limited amount of quantum memory, e.g.
• any protocol with $\le 0.99n$ ancilla qubits of quantum memory must make exponentially many measurements, provided it is non-concatenating.
• Such protocols can only interact with the channel by repeatedly preparing a state, passing it through the channel, and measuring immediately afterward.