Optimal twirling depths for shadow tomography in the presence of noise

• URL: http://arxiv.org/abs/2311.10137v2
• Date: Sat, 20 Jan 2024 01:37:29 GMT
• Title: Optimal twirling depths for shadow tomography in the presence of noise
• Authors: Pierre-Gabriel Rozon, Ning Bao and Kartiek Agarwal
• Abstract summary: We consider the sample complexity as a function of the depth of the circuit, in the presence of noise. We find that this noise has important implications for determining the optimal twirling ensemble. These thresholds strongly constrain the search for optimal strategies to implement shadow tomography.
• Score: 0.1227734309612871
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The classical shadows protocol is an efficient strategy for estimating properties of an unknown state $\rho$ using a small number of state copies and measurements. In its original form, it involves twirling the state with unitaries from some ensemble and measuring the twirled state in a fixed basis. It was recently shown that for computing local properties, optimal sample complexity (copies of the state required) is remarkably achieved for unitaries drawn from shallow depth circuits composed of local entangling gates, as opposed to purely local (zero depth) or global twirling (infinite depth) ensembles. Here we consider the sample complexity as a function of the depth of the circuit, in the presence of noise. We find that this noise has important implications for determining the optimal twirling ensemble. Under fairly general conditions, we i) show that any single-site noise can be accounted for using a depolarizing noise channel with an appropriate damping parameter $f$; ii) compute thresholds $f_{\text{th}}$ at which optimal twirling reduces to local twirling for arbitrary operators and iii) $n^{\text{th}}$ order Renyi entropies ($n \ge 2$); and iv) provide a meaningful upper bound $t_{\text{max}}$ on the optimal circuit depth for any finite noise strength $f$, which applies to all operators and entanglement entropy measurements. These thresholds strongly constrain the search for optimal strategies to implement shadow tomography and can be easily tailored to the experimental system at hand.

Related papers

• Optimal High-probability Convergence of Nonlinear SGD under Heavy-tailed Noise via Symmetrization [50.49466204159458]
  We propose two novel estimators based on the idea of noise symmetrization.<n>We provide a sharper analysis and improved rates.<n>Compared to works assuming symmetric noise with moments, we provide a sharper analysis and improved rates.
  arXiv  Detail & Related papers  (2025-07-12T00:31:13Z)
• Local Averaging Accurately Distills Manifold Structure From Noisy Data [4.63748375343038]
  Local averaging is a cornerstone of state-of-the-art provable methods for manifold fitting and denoising.<n>We provide theoretical analyses of a two-round mini-batch local averaging method applied to noisy samples drawn from a $d$-dimensional manifold.<n>The proposed method can serve as a preprocessing step for a wide range of provable methods designed for lower-noise regimes.
  arXiv  Detail & Related papers  (2025-06-23T15:32:16Z)
• Sign Operator for Coping with Heavy-Tailed Noise: High Probability Convergence Bounds with Extensions to Distributed Optimization and Comparison Oracle [77.3806516979843]
  We show that SignSGD achieves optimal sample complexity $tildeO(varepsilon-frac3kappa - 2kappa 1right)$ with high accuracy. We also explore the application of the sign operator in zeroth-order optimization with an oracle that can only compare function values at two different points.
  arXiv  Detail & Related papers  (2025-02-11T19:54:11Z)
• Approximate inverse measurement channel for shallow shadows [0.025206105035672277]
  Classical shadows are a versatile tool to probe many-body quantum systems. We put forward a simple approximate post-processing scheme where the infinite-depth inverse channel is applied to the finite-depth classical shadows. Our work extends the applicability of shallow shadows to large system sizes and general circuit connectivity.
  arXiv  Detail & Related papers  (2024-07-16T15:02:25Z)
• Semi-Discrete Optimal Transport: Nearly Minimax Estimation With Stochastic Gradient Descent and Adaptive Entropic Regularization [38.67914746910537]
  We prove an $mathcalO(t-1)$ lower bound rate for the OT map, using the similarity between Laguerre cells estimation and density support estimation. To nearly achieve the desired fast rate, we design an entropic regularization scheme decreasing with the number of samples.
  arXiv  Detail & Related papers  (2024-05-23T11:46:03Z)
• Robust ultra-shallow shadows [0.251657752676152]
  We present a robust shadow estimation protocol for wide classes of low-depth measurement circuits. For weakly-correlated local noise, the measurement channel has an efficient matrix-product representation. We show how to estimate this directly from experimental data using tensor-network tools.
  arXiv  Detail & Related papers  (2024-05-09T18:00:09Z)
• Some Constructions of Private, Efficient, and Optimal $K$-Norm and Elliptic Gaussian Noise [54.34628844260993]
  Differentially private computation often begins with a bound on some $d$-dimensional statistic's sensitivity. For pure differential privacy, the $K$-norm mechanism can improve on this approach using a norm tailored to the statistic's sensitivity space. This paper solves both problems for the simple statistics of sum, count, and vote.
  arXiv  Detail & Related papers  (2023-09-27T17:09:36Z)
• Greedy versus Map-based Optimized Adaptive Algorithms for random-telegraph-noise mitigation by spectator qubits [6.305016513788048]
  In a scenario where data-storage qubits are kept in isolation as far as possible, noise mitigation can still be done using additional noise probes. We construct a theoretical model assuming projective measurements on the qubits, and derive the performance of different measurement and control strategies. We show, analytically and numerically, that MOAAAR outperforms the Greedy algorithm, especially in the regime of high noise sensitivity of SQ.
  arXiv  Detail & Related papers  (2022-05-25T08:25:10Z)
• Blind Source Separation for Mixture of Sinusoids with Near-Linear Computational Complexity [0.0]
  We propose a multi-tone decomposition algorithm that can find the frequencies, amplitudes and phases of the fundamental sinusoids in a noisy sequence. When estimating $M$ number of sinusoidal sources, our algorithm successively estimates their frequencies and jointly optimize their amplitudes and phases.
  arXiv  Detail & Related papers  (2022-03-27T15:16:07Z)
• 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)
• Towards Sample-Optimal Compressive Phase Retrieval with Sparse and Generative Priors [59.33977545294148]
  We show that $O(k log L)$ samples suffice to guarantee that the signal is close to any vector that minimizes an amplitude-based empirical loss function. We adapt this result to sparse phase retrieval, and show that $O(s log n)$ samples are sufficient for a similar guarantee when the underlying signal is $s$-sparse and $n$-dimensional.
  arXiv  Detail & Related papers  (2021-06-29T12:49:54Z)
• Lattice partition recovery with dyadic CART [79.96359947166592]
  We study piece-wise constant signals corrupted by additive Gaussian noise over a $d$-dimensional lattice. Data of this form naturally arise in a host of applications, and the tasks of signal detection or testing, de-noising and estimation have been studied extensively in the statistical and signal processing literature. In this paper we consider instead the problem of partition recovery, i.e.of estimating the partition of the lattice induced by the constancy regions of the unknown signal. We prove that a DCART-based procedure consistently estimates the underlying partition at a rate of order $sigma2 k*
  arXiv  Detail & Related papers  (2021-05-27T23:41:01Z)
• Byzantine-Resilient Non-Convex Stochastic Gradient Descent [61.6382287971982]
  adversary-resilient distributed optimization, in which. machines can independently compute gradients, and cooperate. Our algorithm is based on a new concentration technique, and its sample complexity. It is very practical: it improves upon the performance of all prior methods when no. setting machines are present.
  arXiv  Detail & Related papers  (2020-12-28T17:19:32Z)
• Fermionic partial tomography via classical shadows [0.0]
  We propose a tomographic protocol for estimating any $ k $-body reduced density matrix ($ k $-RDM) of an $ n $-mode fermionic state. Our approach extends the framework of classical shadows, a randomized approach to learning a collection of quantum-state properties, to the fermionic setting.
  arXiv  Detail & Related papers  (2020-10-30T06:28:26Z)
• 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.