Adaptivity is not helpful for Pauli channel learning

Xuan Du Trinh; Nengkun Yu

doi:10.22331/q-2025-09-24-1864

Adaptivity is not helpful for Pauli channel learning

Department of Computer Science, Stony Brook University, Stony Brook, NY 11794, USA

Published:	2025-09-24, volume 9, page 1864
Editor:	Tom Gur
Eprint:	arXiv:2403.09033v4
Doi:	https://doi.org/10.22331/q-2025-09-24-1864
Citation:	Quantum 9, 1864 (2025).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

We prove that adaptive strategies offer no advantage over non-adaptive ones for learning and testing Pauli channels using entangled inputs. This key observation allows us to characterize the query complexity for several fundamental tasks by translating optimal classical estimation algorithms into the quantum setting. First, we determine the tight query complexity for learning a Pauli channel under the general $\ell_p$ norm, providing results that improve upon or match the best-known bounds for the $\ell_1, \ell_2,$ and $\ell_\infty$ distances. Second, we resolve the complexity of testing whether a Pauli channel is a white noise source. Finally, we show that the optimal query complexities for estimating the Shannon entropy and support size of the channel's error distribution, and for estimating the diamond distance between two Pauli channels, are all $\Theta\left(\tfrac{4^n}{n\epsilon^2}\right)$.

► BibTeX data

@article{Trinh2025adaptivityisnot,
  doi = {10.22331/q-2025-09-24-1864},
  url = {https://doi.org/10.22331/q-2025-09-24-1864},
  title = {Adaptivity is not helpful for {P}auli channel learning},
  author = {Trinh, Xuan Du and Yu, Nengkun},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {9},
  pages = {1864},
  month = sep,
  year = {2025}
}

► References

[1] Konstantinos Georgopoulos, Clive Emary, and Paolo Zuliani. Modeling and simulating the noisy behavior of near-term quantum computers. Phys. Rev. A, 104: 062432, Dec 2021. 10.1103/PhysRevA.104.062432. URL https://doi.org/10.1103/PhysRevA.104.062432.
https://doi.org/10.1103/PhysRevA.104.062432

[2] Steven T. Flammia and Joel J. Wallman. Efficient estimation of pauli channels. ACM Transactions on Quantum Computing, 1 (1), December 2020. 10.1145/3408039. URL https://doi.org/10.1145/3408039.
https://doi.org/10.1145/3408039

[3] Omar Fawzi, Aadil Oufkir, and Daniel Stilck França. Lower bounds on learning pauli channels with individual measurements. IEEE Transactions on Information Theory, 71 (4): 2642–2661, 2025. 10.1109/TIT.2025.3527902. URL https://doi.org/10.1109/TIT.2025.3527902.
https://doi.org/10.1109/TIT.2025.3527902

[4] Steven T. Flammia and Ryan O’Donnell. Pauli error estimation via population recovery. Quantum, 5: 549, September 2021. 10.22331/q-2021-09-23-549. URL https://doi.org/10.22331/q-2021-09-23-549.
https://doi.org/10.22331/q-2021-09-23-549

[5] Senrui Chen, Changhun Oh, Sisi Zhou, Hsin-Yuan Huang, and Liang Jiang. Tight bounds on pauli channel learning without entanglement. Phys. Rev. Lett., 132: 180805, May 2024. 10.1103/PhysRevLett.132.180805. URL https://doi.org/10.1103/PhysRevLett.132.180805.
https://doi.org/10.1103/PhysRevLett.132.180805

[6] Senrui Chen, Sisi Zhou, Alireza Seif, and Liang Jiang. Quantum advantages for pauli channel estimation. Phys. Rev. A, 105: 032435, Mar 2022. 10.1103/PhysRevA.105.032435. URL https://doi.org/10.1103/PhysRevA.105.032435.
https://doi.org/10.1103/PhysRevA.105.032435

[7] Joel J. Wallman and Joseph Emerson. Noise tailoring for scalable quantum computation via randomized compiling. Phys. Rev. A, 94: 052325, Nov 2016. 10.1103/PhysRevA.94.052325. URL https://doi.org/10.1103/PhysRevA.94.052325.
https://doi.org/10.1103/PhysRevA.94.052325

[8] S. Chen, Y. Liu, M. Otten, et al. The learnability of pauli noise. Nature Communications, 14: 52, 2023. 10.1038/s41467-022-35759-4. URL https://doi.org/10.1038/s41467-022-35759-4. Received: 4 July 2022; Accepted: 23 December 2022; Published: 4 January 2023.
https://doi.org/10.1038/s41467-022-35759-4

[9] Cambyse Rouzé and Daniel Stilck França. Efficient learning of the structure and parameters of local pauli noise channels. 2023. 10.48550/arXiv.2307.02959. URL https://doi.org/10.48550/arXiv.2307.02959.
https://doi.org/10.48550/arXiv.2307.02959

[10] Clément L. Canonne. A short note on learning discrete distributions. 2020. 10.48550/arXiv.2002.11457. URL https://doi.org/10.48550/arXiv.2002.11457.
https://doi.org/10.48550/arXiv.2002.11457

[11] Bo Waggoner. Lp testing and learning of discrete distributions. In Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, ITCS '15, page 347–356, New York, NY, USA, 2015. Association for Computing Machinery. ISBN 9781450333337. 10.1145/2688073.2688095. URL https://doi.org/10.1145/2688073.2688095.
https://doi.org/10.1145/2688073.2688095

[12] Gregory Valiant and Paul Valiant. Estimating the unseen: an n/log(n)-sample estimator for entropy and support size, shown optimal via new clts. In Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, STOC '11, page 685–694, New York, NY, USA, 2011. Association for Computing Machinery. ISBN 9781450306911. 10.1145/1993636.1993727. URL https://doi.org/10.1145/1993636.1993727.
https://doi.org/10.1145/1993636.1993727

[13] Gregory Valiant and Paul Valiant. Estimating the unseen: Improved estimators for entropy and other properties. J. ACM, 64 (6), October 2017. ISSN 0004-5411. 10.1145/3125643. URL https://doi.org/10.1145/3125643.
https://doi.org/10.1145/3125643

[14] Dominik Hangleiter and Michael J. Gullans. Bell sampling from quantum circuits. Physical Review Letters, 133 (2): 020601, 2024. 10.1103/PhysRevLett.133.020601. URL https://doi.org/10.1103/PhysRevLett.133.020601.
https://doi.org/10.1103/PhysRevLett.133.020601

[15] William K Wootters and Wojciech H Zurek. A single quantum cannot be cloned. Nature, 299 (5886): 802–803, 1982. 10.1038/299802a0. URL https://doi.org/10.1038/299802a0.
https://doi.org/10.1038/299802a0

[16] Gerardo Adesso and Fabrizio Illuminati. Entanglement in continuous variable systems: recent advances and current perspectives. Journal of Physics A: Mathematical and Theoretical, 40 (28): 7821–7880, 2007. 10.1088/1751-8113/40/28/S18. URL https://doi.org/10.1088/1751-8113/40/28/S18.
https://doi.org/10.1088/1751-8113/40/28/S18

[17] Easwar Magesan, Jay M. Gambetta, and Joseph Emerson. Characterizing quantum gates via randomized benchmarking. Phys. Rev. A, 85: 042311, Apr 2012. 10.1103/PhysRevA.85.042311. URL https://doi.org/10.1103/PhysRevA.85.042311.
https://doi.org/10.1103/PhysRevA.85.042311

Cited by

[1] Senrui Chen, Zhihan Zhang, Liang Jiang, and Steven T. Flammia, "Efficient Self-Consistent Learning of Gate Set Pauli Noise", PRX Quantum 7 1, 010305 (2026).

The above citations are from Crossref's cited-by service (last updated successfully 2026-08-17 19:41:58) and SAO/NASA ADS (last updated successfully 2026-08-17 19:42:01). The list may be incomplete as not all publishers provide suitable and complete citation data.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.