SPAM Tolerance for Pauli Error Estimation

• URL: http://arxiv.org/abs/2510.00230v1
• Date: Tue, 30 Sep 2025 19:53:30 GMT
• Title: SPAM Tolerance for Pauli Error Estimation
• Authors: Ryan O'Donnell, Samvitti Sharma,
• Abstract summary: We present an algorithm that builds on the reduction to Population Recovery introduced in [FO21].<n>Our algorithm has the key advantage of robustness against even severe state preparation and measurement (SPAM) errors.
• Score: 1.074267520911262
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Pauli channel is a fundamental model of noise in quantum systems, motivating the task of Pauli error estimation. We present an algorithm that builds on the reduction to Population Recovery introduced in [FO21]. Addressing an open question from that work, our algorithm has the key advantage of robustness against even severe state preparation and measurement (SPAM) errors. To tolerate SPAM, we must analyze Population Recovery on a combined erasure/bit-flip channel, which necessitates extending the complex analysis techniques from [PSW17, DOS17]. For $n$-qubit channels, our Pauli error estimation algorithm requires only $\exp(n^{1/3})$ unentangled state preparations and measurements, improving on previous SPAM-tolerant algorithms that had $2^n$-dependence even for restricted families of Pauli channels. We also give evidence that no SPAM-tolerant method can make asymptotically fewer than $\exp(n^{1/3})$ uses of the channel.

Related papers

• Sample- and Hardware-Efficient Fidelity Estimation by Stripping Phase-Dominated Magic [0.2796197251957245]
  This work proposes a sample- and gate-efficient fidelity estimation algorithm that is affordable within feasible quantum devices.<n>We show that the fidelity estimation with pure states close to the structure of phase states, for which sample-efficient DFE is limited by their strong entanglement and magic, can be done by using $mathcalO(mathrmpoly(n))$ sampling copies, with a single $n$-qubit fan-out gate.
  arXiv  Detail & Related papers  (2026-02-10T12:13:25Z)
• Adapting to Stochastic and Adversarial Losses in Episodic MDPs with Aggregate Bandit Feedback [61.49239204705301]
  We study online learning in finite-horizon episodic Markov decision processes (MDPs) under the challenging aggregate bandit feedback model.<n>Our results rely on a combination of FTRL over occupancy measures, self-bounding techniques, and new loss estimators inspired by recent advances in online shortest path problems.
  arXiv  Detail & Related papers  (2025-10-20T02:28:08Z)
• On the Constant Depth Implementation of Pauli Exponentials [49.48516314472825]
  We decompose $Zotimes n$ exponentials of arbitrary length into circuits of constant depth using $mathcalO(n)$ ancillae and two-body XX and ZZ interactions.<n>We prove the correctness of our approach, after introducing novel rewrite rules for circuits which benefit from qubit recycling.
  arXiv  Detail & Related papers  (2024-08-15T17:09:08Z)
• Adaptivity is not helpful for Pauli channel learning [11.029146548022291]
  We prove that adaptive strategies offer no advantage over non-adaptive ones for learning and testing Pauli channels using entangled inputs.<n>We characterize the query complexity for several fundamental tasks by translating optimal classical estimation algorithms into the quantum setting.
  arXiv  Detail & Related papers  (2024-03-14T01:54:29Z)
• Lower Bounds on Learning Pauli Channels with Individual Measurements [6.909352249236339]
  We show lower bounds on the sample complexity for learning Pauli channels in diamond norm.<n>We consider strategies that may not use auxiliary systems entangled with the input to the unknown channel.
  arXiv  Detail & Related papers  (2023-01-22T20:01:34Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)
• Under-Approximating Expected Total Rewards in POMDPs [68.8204255655161]
  We consider the optimal expected total reward to reach a goal state in a partially observable Markov decision process (POMDP) We use mixed-integer linear programming (MILP) to find such minimal probability shifts and experimentally show that our techniques scale quite well.
  arXiv  Detail & Related papers  (2022-01-21T16:43:03Z)
• Pauli error estimation via Population Recovery [1.52292571922932]
  We study the problem of learning a Pauli channel, or more generally the Pauli error rates of an arbitrary channel. We give an extremely simple algorithm that learns the Pauli error rates of an $n$-qubit channel to precision $epsilon$ in $ell_infty$ We extend our algorithm to achieve multiplicative precision $1 pm epsilon$ (i.e., additive precision $epsilon eta$) using just $Obigl(frac1epsilon2 etabigr)
  arXiv  Detail & Related papers  (2021-05-06T18:00:02Z)
• Sampling Overhead Analysis of Quantum Error Mitigation: Uncoded vs. Coded Systems [69.33243249411113]
  We show that Pauli errors incur the lowest sampling overhead among a large class of realistic quantum channels. We conceive a scheme amalgamating QEM with quantum channel coding, and analyse its sampling overhead reduction compared to pure QEM.
  arXiv  Detail & Related papers  (2020-12-15T15:51:27Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)
• Fast Estimation of Sparse Quantum Noise [1.933681537640272]
  We present a practical algorithm for estimating the $s$ nonzero Pauli error rates in an $s$-sparse, $n$-qubit Pauli noise channel. We experimentally validate a version of the algorithm that uses simplified Clifford circuits on data from an IBM 14-qubit superconducting device.
  arXiv  Detail & Related papers  (2020-07-15T18:00:01Z)
• Learning Halfspaces with Tsybakov Noise [50.659479930171585]
  We study the learnability of halfspaces in the presence of Tsybakov noise. We give an algorithm that achieves misclassification error $epsilon$ with respect to the true halfspace.
  arXiv  Detail & Related papers  (2020-06-11T14:25:02Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.