Efficient Pauli Channel Estimation with Logarithmic Quantum Memory - Sitan Chen; Weiyuan Gong (PRX Quantum)
In this work, we consider one of the prototypical tasks for characterizing the structure of noise in quantum devices: estimating eigenvalues of an n-qubit Pauli noise channel. Prior work [Chen et al., Phys. Rev. A 105, 032435 (2022)] has proved no-go theorems for this task in the practical regime in which one has a limited amount of quantum memory; i.e., any protocol with ≤0.99n ancilla qubits of quantum memory must make exponentially many measurements, provided that 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. Surprisingly, in this work we show that concatenating protocols with an extremely small amount of quantum memory achieve an exponential advantage for this task. We give a protocol that can estimate any prescribed set of eigenvalues A of a Pauli channel to error ε using only O(log⁡log⁡(|A|)/ε^{2}) ancilla qubits, O[over ~](n^{2}/ε^{2}) measurements, and O(n^{2}|A|/ε^{2}) queries to the Pauli channel. In contrast, we show that any protocol with zero ancilla—even a concatenating one—must make Ω(2^{n}/ε^{2}) measurements. We also prove that the number of queries cannot be improved significantly: with k ancilla qubits, Ω(2^{(n−k)/3}) queries to the channel are necessary to learn all eigenvalues, even for concatenating protocols.