# Lower Bounds on Learning Pauli Channels with Individual Measurements

arXiv: https://arxiv.org/abs/2301.09192 · HTML: https://mlsanity.com/paper/2301.09192/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 2 of its 36 references that are in the map.
- First posted on arXiv 22 Jan 2023.

## Builds on (most cited first, 2 of 2)

- [When Does Adaptivity Help for Quantum State Learning?](https://mlsanity.com/paper/2206.05265/) (2022)
- [Lower Bounds for Learning Quantum States with Single-Copy Measurements](https://mlsanity.com/paper/2207.14438/) (2022)

## Built on by (most cited first, 5 of 5)

- [Tight bounds on Pauli channel learning without entanglement](https://mlsanity.com/paper/2309.13461/) (2023)
- [On the sample complexity of purity and inner product estimation](https://mlsanity.com/paper/2410.12712/) (2024)
- [Learning low-degree quantum objects](https://mlsanity.com/paper/2405.10933/) (2024)
- [Generalization Bounds for Quantum Learning via R'enyi Divergences](https://mlsanity.com/paper/2505.11025/) (2025)
- [Noise-tolerant learnability of shallow quantum circuits from statistics and the cost of quantum pseudorandomness](https://mlsanity.com/paper/2405.12085/) (2024)

## Abstract (arXiv)

Understanding the noise affecting a quantum device is of fundamental importance for scaling quantum technologies. A particularly important class of noise models is that of Pauli channels, as randomized compiling techniques can effectively bring any quantum channel to this form and are significantly more structured than general quantum channels. In this paper, we show fundamental lower bounds on the sample complexity for learning Pauli channels in diamond norm. We consider strategies that may not use auxiliary systems entangled with the input to the unknown channel and have to perform a measurement before reusing the channel. For non-adaptive algorithms, we show a lower bound of Omega(23nvarepsilon-2) to learn an n-qubit Pauli channel. In particular, this shows that the recently introduced learning procedure by Flammia and Wallman is essentially optimal. In the adaptive setting, we show a lower bound of Omega(22.5nvarepsilon-2) for varepsilon=O(2-n), and a lower bound of Omega(22nvarepsilon-2 ) for any varepsilon> 0. This last lower bound holds even in a stronger model where in each step, before performing the measurement, the unknown channel may be used arbitrarily many times sequentially interspersed with unital operations.