# Tight bounds on Pauli channel learning without entanglement

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 53 references that are in the map.
- First posted on arXiv 23 Sep 2023.

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

- [Quantum advantage in learning from experiments](https://mlsanity.com/paper/2112.00778/) (2021)
- [Information-theoretic bounds on quantum advantage in machine learning](https://mlsanity.com/paper/2101.02464/) (2021)
- [Exponential separations between learning with and without quantum memory](https://mlsanity.com/paper/2111.05881/) (2021)
- [Entanglement is Necessary for Optimal Quantum Property Testing](https://mlsanity.com/paper/2004.07869/) (2020)
- [Learning Quantum Processes and Hamiltonians via the Pauli Transfer Matrix](https://mlsanity.com/paper/2212.04471/) (2022)
- [The Complexity of NISQ](https://mlsanity.com/paper/2210.07234/) (2022)
- [Foundations for learning from noisy quantum experiments](https://mlsanity.com/paper/2204.13691/) (2022)
- [Lower Bounds on Learning Pauli Channels with Individual Measurements](https://mlsanity.com/paper/2301.09192/) (2023)

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

- [On the sample complexity of purity and inner product estimation](https://mlsanity.com/paper/2410.12712/) (2024)
- [An optimal tradeoff between entanglement and copy complexity for state tomography](https://mlsanity.com/paper/2402.16353/) (2024)
- [Demonstration of Efficient Predictive Surrogates for Large-scale Quantum Processors](https://mlsanity.com/paper/2507.17470/) (2025)
- [Testing classical properties from quantum data](https://mlsanity.com/paper/2411.12730/) (2024)
- [Efficient learning of bosonic Gaussian unitaries](https://mlsanity.com/paper/2510.05531/) (2025)
- [Noise-tolerant learnability of shallow quantum circuits from statistics and the cost of quantum pseudorandomness](https://mlsanity.com/paper/2405.12085/) (2024)
- [Adaptivity can help exponentially for shadow tomography](https://mlsanity.com/paper/2412.19022/) (2024)

## Abstract (arXiv)

Quantum entanglement is a crucial resource for learning properties from nature, but a precise characterization of its advantage can be challenging. In this work, we consider learning algorithms without entanglement to be those that only utilize states, measurements, and operations that are separable between the main system of interest and an ancillary system. Interestingly, we show that these algorithms are equivalent to those that apply quantum circuits on the main system interleaved with mid-circuit measurements and classical feedforward. Within this setting, we prove a tight lower bound for Pauli channel learning without entanglement that closes the gap between the best-known upper and lower bound. In particular, we show that Theta(2nvarepsilon-2) rounds of measurements are required to estimate each eigenvalue of an n-qubit Pauli channel to varepsilon error with high probability when learning without entanglement. In contrast, a learning algorithm with entanglement only needs Theta(varepsilon-2) copies of the Pauli channel. The tight lower bound strengthens the foundation for an experimental demonstration of entanglement-enhanced advantages for Pauli noise characterization.