  The unavoidable presence of noise is a crucial roadblock for the development
of large-scale quantum computers and the ability to characterize quantum noise
reliably and efficiently with high precision is essential to scale quantum
technologies further. Although estimating an arbitrary quantum channel requires
exponential resources, it is expected that physically relevant noise has some
underlying local structure, for instance that errors across different qubits
have a conditional independence structure. Previous works showed how it is
possible to estimate Pauli noise channels with an efficient number of samples
in a way that is robust to state preparation and measurement errors, albeit
departing from a known conditional independence structure.
  We present a novel approach for learning Pauli noise channels over n qubits
that addresses this shortcoming. Unlike previous works that focused on learning
coefficients with a known conditional independence structure, our method learns
both the coefficients and the underlying structure. We achieve our results by
leveraging a groundbreaking result by Bresler for efficiently learning Gibbs
measures and obtain an optimal sample complexity of O(log(n)) to learn the
unknown structure of the noise acting on n qubits. This information can then be
leveraged to obtain a description of the channel that is close in diamond
distance from O(poly(n)) samples. Furthermore, our method is efficient both in
the number of samples and postprocessing without giving up on other desirable
features such as SPAM-robustness, and only requires the implementation of
single qubit Cliffords. In light of this, our novel approach enables the
large-scale characterization of Pauli noise in quantum devices under minimal
experimental requirements and assumptions.
