Adaptivity is not helpful for Pauli channel learning

• URL: http://arxiv.org/abs/2403.09033v3
• Date: Tue, 19 Mar 2024 20:04:42 GMT
• Title: Adaptivity is not helpful for Pauli channel learning
• Authors: Xuan Du Trinh, Nengkun Yu,
• Abstract summary: This note shows that adaptive strategies do not offer additional advantages for learning and testing Pauli channels with entangled input. First, the tight query complexity of learning Pauli channels with entangled input is established for the general norm $l_p$. We demonstrate that the query complexity of estimating the noise level of a Pauli channel, characterized by the entropy of its error distribution, is $Theta(4n/n)$.
• Score: 12.123876307427103
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: This note shows that adaptive strategies do not offer additional advantages for learning and testing Pauli channels with entangled input. First, the tight query complexity of learning Pauli channels with entangled input is established for the general norm $l_p$. In particular, the complexities for the $l_{1}$, $l_2$ and $l_\infty$ norms are improved or matched compared to previous results using entanglement in the literature. We also settle the query complexity to test if Pauli channels are white noise sources across $l_p$. Additionally, we demonstrate that the query complexity of estimating the noise level of a Pauli channel, characterized by the entropy of its error distribution and the count of non-zero probabilities, is $\Theta(4^n/n)$. Further, $\Theta(4^n/n)$ queries are sufficient to estimate the diamond norm between two Pauli channels.

Related papers

• 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)
• 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)
• 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.