License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.TQC.2021.8
URN: urn:nbn:de:0030-drops-140034
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14003/
Go to the corresponding LIPIcs Volume Portal

Flammia, Steven T. ; O'Donnell, Ryan

Pauli Error Estimation via Population Recovery

pdf-format:
LIPIcs-TQC-2021-8.pdf (0.7 MB)

Abstract

Motivated by estimation of quantum noise models, we study the problem of learning a Pauli channel, or more generally the Pauli error rates of an arbitrary channel. By employing a novel reduction to the "Population Recovery" problem, we give an extremely simple algorithm that learns the Pauli error rates of an n-qubit channel to precision ε in ?_∞ using just O(1/ε²) log(n/ε) applications of the channel. This is optimal up to the logarithmic factors. Our algorithm uses only unentangled state preparation and measurements, and the post-measurement classical runtime is just an O(1/ε) factor larger than the measurement data size. It is also impervious to a limited model of measurement noise where heralded measurement failures occur independently with probability ≤ 1/4.
We then consider the case where the noise channel is close to the identity, meaning that the no-error outcome occurs with probability 1-η. In the regime of small η we extend our algorithm to achieve multiplicative precision 1 ± ε (i.e., additive precision εη) using just O(1/(ε²η)) log(n/ε) applications of the channel.

BibTeX - Entry

@InProceedings{flammia_et_al:LIPIcs.TQC.2021.8,
  author =	{Flammia, Steven T. and O'Donnell, Ryan},
  title =	{{Pauli Error Estimation via Population Recovery}},
  booktitle =	{16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021)},
  pages =	{8:1--8:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-198-6},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{197},
  editor =	{Hsieh, Min-Hsiu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14003},
  URN =		{urn:nbn:de:0030-drops-140034},
  doi =		{10.4230/LIPIcs.TQC.2021.8},
  annote =	{Keywords: Pauli channels, population recovery, Goldreich-Levin, sparse recovery, quantum channel tomography}
}

Keywords: Pauli channels, population recovery, Goldreich-Levin, sparse recovery, quantum channel tomography
Collection: 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021)
Issue Date: 2021
Date of publication: 22.06.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI