Adaptivity is not helpful for Pauli channel learning

• URL: http://arxiv.org/abs/2403.09033v4
• Date: Fri, 19 Sep 2025 05:40:13 GMT
• Title: Adaptivity is not helpful for Pauli channel learning
• Authors: Xuan Du Trinh, Nengkun Yu,
• Abstract summary: 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.
• Score: 11.029146548022291
• License: http://creativecommons.org/licenses/by/4.0/
• 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)$.

Related papers

• Rate optimal learning of equilibria from data [63.14746189846806]
  We close theoretical gaps in Multi-Agent Imitation Learning (MAIL) by characterizing the limits of non-interactive MAIL and presenting the first interactive algorithm with near-optimal sample complexity.<n>For the interactive setting, we introduce a framework that combines reward-free reinforcement learning with interactive MAIL and instantiate it with an algorithm, MAIL-WARM.<n>We provide numerical results that support our theory and illustrate, in environments such as grid worlds, where Behavior Cloning fails to learn.
  arXiv  Detail & Related papers  (2025-10-10T12:28:35Z)
• SPAM Tolerance for Pauli Error Estimation [1.074267520911262]
  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.
  arXiv  Detail & Related papers  (2025-09-30T19:53:30Z)
• Query-Optimal Estimation of Unitary Channels via Pauli Dimensionality [0.8594140167290097]
  We study process tomography of unitary channels whose Pauli spectrum is supported on a small subgroup.<n>We present an algorithm that achieves this using $O(2k/epsilon)$ queries.<n>We also give a computationally efficient algorithm for learning compositions of depth-$O(log n)$ circuits with near-Clifford circuits.
  arXiv  Detail & Related papers  (2025-09-30T18:40:42Z)
• 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)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  We study multiclass PAC learning with bandit feedback, where inputs are classified into one of $K$ possible labels and feedback is limited to whether or not the predicted labels are correct. Our main contribution is in designing a novel learning algorithm for the agnostic $(varepsilon,delta)$PAC version of the problem.
  arXiv  Detail & Related papers  (2024-06-18T08:54:04Z)
• Tight bounds on Pauli channel learning without entanglement [2.2845597309741157]
  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. 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.
  arXiv  Detail & Related papers  (2023-09-23T19:12:29Z)
• Beyond the mixture of generalized Pauli dephasing channels [3.4521402245831583]
  We show that non-invertibility of mixed channels is not a prerequisite for the resulting mapping to constitute a Markovian semigroup. We demonstrate that every Pauli channel can be represented as a mixture of $(d+1)$ Pauli dephasing channels, but this generalization doesn't apply to higher dimensions.
  arXiv  Detail & Related papers  (2023-09-10T00:50:38Z)
• Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise [50.64137465792738]
  We study the problem of PAC $gamma$-margin halfspaces with Random Classification Noise. We establish an information-computation tradeoff suggesting an inherent gap between the sample complexity of the problem and the sample complexity of computationally efficient algorithms.
  arXiv  Detail & Related papers  (2023-06-28T16:33:39Z)
• On the average-case complexity of learning output distributions of quantum circuits [55.37943886895049]
  We show that learning the output distributions of brickwork random quantum circuits is average-case hard in the statistical query model. This learning model is widely used as an abstract computational model for most generic learning algorithms.
  arXiv  Detail & Related papers  (2023-05-09T20:53:27Z)
• Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPs [60.40452803295326]
  We propose a new reward-free algorithm for learning linear Markov decision processes (MDPs) At the core of our algorithm is uncertainty-weighted value-targeted regression with exploration-driven pseudo-reward. We show that our algorithm only needs to explore $tilde O( d2varepsilon-2)$ episodes to find an $varepsilon$-optimal policy.
  arXiv  Detail & Related papers  (2023-03-17T17:53:28Z)
• Lower Bounds on Learning Pauli Channels [8.72305226979945]
  We show lower bounds on the sample complexity for learning Pauli channels in diamond norm with unentangled measurements. In the non-adaptive setting, we show a lower bound of $Omega (23nepsilon-2)$ to learn an $n$-qubit Pauli channel. In the adaptive setting, we show a lower bound of $Omega (22.5nepsilon-2)$ for $epsilon=mathcalO (2-n)$, and a lower bound of $Omega (22n
  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)
• Random quantum circuits transform local noise into global white noise [118.18170052022323]
  We study the distribution over measurement outcomes of noisy random quantum circuits in the low-fidelity regime. For local noise that is sufficiently weak and unital, correlations (measured by the linear cross-entropy benchmark) between the output distribution $p_textnoisy$ of a generic noisy circuit instance shrink exponentially. If the noise is incoherent, the output distribution approaches the uniform distribution $p_textunif$ at precisely the same rate.
  arXiv  Detail & Related papers  (2021-11-29T19:26:28Z)
• Quantum advantages for Pauli channel estimation [2.5496329090462626]
  entangled measurements provide an exponential advantage in sample complexity for Pauli channel estimation. We show how to apply the ancilla-assisted estimation protocol to a practical quantum benchmarking task.
  arXiv  Detail & Related papers  (2021-08-19T04:10:28Z)
• On $\ell_p$-norm Robustness of Ensemble Stumps and Trees [83.81523991945018]
  We develop an efficient programming based algorithm for sound verification of ensemble stumps. We demonstrate the first certified defense method for training ensemble stumps and trees with respect to $ell_p$ norm perturbations.
  arXiv  Detail & Related papers  (2020-08-20T03:42:40Z)
• 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)
• Quantum Communication Complexity of Distribution Testing [114.31181206328276]
  Two players each receive $t$ samples from one distribution over $[n]$. The goal is to decide whether their two distributions are equal, or are $epsilon$-far apart. We show that the quantum communication complexity of this problem is $tildeO$(tepsilon2))$ qubits when distributions have low $l$-norm.
  arXiv  Detail & Related papers  (2020-06-26T09:05:58Z)

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.