Classical Shadows with Improved Median-of-Means Estimation

• URL: http://arxiv.org/abs/2412.03381v1
• Date: Wed, 04 Dec 2024 15:07:58 GMT
• Title: Classical Shadows with Improved Median-of-Means Estimation
• Authors: Winston Fu, Dax Enshan Koh, Siong Thye Goh, Jian Feng Kong,
• Abstract summary: The classical shadows protocol makes use of the median-of-means (MoM) estimator to efficiently estimate the expectation values of $M$ observables.<n>We studied a modified MoM estimator proposed by Minsker that uses optimal constants and involves a U-statistic over the data set.<n>Our findings highlight the importance of tailoring estimators to specific measurement settings to optimize the performance of the classical shadows protocol.
• Score: 0.19285000127136376
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The classical shadows protocol, introduced by Huang et al. [Nat. Phys. 16, 1050 (2020)], makes use of the median-of-means (MoM) estimator to efficiently estimate the expectation values of $M$ observables with failure probability $\delta$ using only $\mathcal{O}(\log(M/\delta))$ measurements. In their analysis, Huang et al. used loose constants in their asymptotic performance bounds for simplicity. However, the specific values of these constants can significantly affect the number of shots used in practical implementations. To address this, we studied a modified MoM estimator proposed by Minsker [PMLR 195, 5925 (2023)] that uses optimal constants and involves a U-statistic over the data set. For efficient estimation, we implemented two types of incomplete U-statistics estimators, the first based on random sampling and the second based on cyclically permuted sampling. We compared the performance of the original and modified estimators when used with the classical shadows protocol with single-qubit Clifford unitaries (Pauli measurements) for an Ising spin chain, and global Clifford unitaries (Clifford measurements) for the Greenberger-Horne-Zeilinger (GHZ) state. While the original estimator outperformed the modified estimators for Pauli measurements, the modified estimators showed improved performance over the original estimator for Clifford measurements. Our findings highlight the importance of tailoring estimators to specific measurement settings to optimize the performance of the classical shadows protocol in practical applications.

Related papers

• A Statistical Analysis for Per-Instance Evaluation of Stochastic Optimizers: How Many Repeats Are Enough? [0.8575004906002217]
  We present a statistical analysis of the common metrics, and develop guidelines for experiment design. We derive a lower bound on the number of repeats in order to guarantee achieving a given accuracy in the metrics. We propose an algorithm to adaptively adjust the number of repeats needed to ensure the accuracy of the evaluated metric.
  arXiv  Detail & Related papers  (2025-03-20T17:38:50Z)
• Bayesian Optimization for Robust Identification of Ornstein-Uhlenbeck Model [4.0148499400442095]
  This paper deals with the identification of the derivation Ornstein-Uhlenbeck (OU) process error model. We put forth a sample-efficient global optimization approach based on the Bayesian optimization framework.
  arXiv  Detail & Related papers  (2025-03-09T01:38:21Z)
• Efficient Sampling for Pauli Measurement-Based Shadow Tomography in Direct Fidelity Estimation [4.513787113118679]
  A constant number of random Clifford measurements allows the classical shadow protocol to perform direct fidelity estimation (DFE) with high precision. We show that similar strategies can be derived from classical shadows. Specifically, we describe efficient methods using only local Pauli measurements to perform DFE with GHZ, W, and Dicke states.
  arXiv  Detail & Related papers  (2025-01-07T04:09:13Z)
• Multivariate root-n-consistent smoothing parameter free matching estimators and estimators of inverse density weighted expectations [51.000851088730684]
  We develop novel modifications of nearest-neighbor and matching estimators which converge at the parametric $sqrt n $-rate. We stress that our estimators do not involve nonparametric function estimators and in particular do not rely on sample-size dependent parameters smoothing.
  arXiv  Detail & Related papers  (2024-07-11T13:28:34Z)
• Nearest Neighbor Sampling for Covariate Shift Adaptation [7.940293148084844]
  We propose a new covariate shift adaptation method which avoids estimating the weights. The basic idea is to directly work on unlabeled target data, labeled according to the $k$-nearest neighbors in the source dataset. Our experiments show that it achieves drastic reduction in the running time with remarkable accuracy.
  arXiv  Detail & Related papers  (2023-12-15T17:28:09Z)
• Optimization of Annealed Importance Sampling Hyperparameters [77.34726150561087]
  Annealed Importance Sampling (AIS) is a popular algorithm used to estimates the intractable marginal likelihood of deep generative models. We present a parameteric AIS process with flexible intermediary distributions and optimize the bridging distributions to use fewer number of steps for sampling. We assess the performance of our optimized AIS for marginal likelihood estimation of deep generative models and compare it to other estimators.
  arXiv  Detail & Related papers  (2022-09-27T07:58:25Z)
• Semi-Supervised Quantile Estimation: Robust and Efficient Inference in High Dimensional Settings [0.5735035463793009]
  We consider quantile estimation in a semi-supervised setting, characterized by two available data sets. We propose a family of semi-supervised estimators for the response quantile(s) based on the two data sets.
  arXiv  Detail & Related papers  (2022-01-25T10:02:23Z)
• A Non-Classical Parameterization for Density Estimation Using Sample Moments [0.0]
  We propose a non-classical parametrization for density estimation using sample moments. The proposed estimator is the first one in the literature for which the power moments up to an arbitrary even order exactly match the sample moments.
  arXiv  Detail & Related papers  (2022-01-13T04:28:52Z)
• Learning to Estimate Without Bias [57.82628598276623]
  Gauss theorem states that the weighted least squares estimator is a linear minimum variance unbiased estimation (MVUE) in linear models. In this paper, we take a first step towards extending this result to non linear settings via deep learning with bias constraints. A second motivation to BCE is in applications where multiple estimates of the same unknown are averaged for improved performance.
  arXiv  Detail & Related papers  (2021-10-24T10:23:51Z)
• Rao-Blackwellizing the Straight-Through Gumbel-Softmax Gradient Estimator [93.05919133288161]
  We show that the variance of the straight-through variant of the popular Gumbel-Softmax estimator can be reduced through Rao-Blackwellization. This provably reduces the mean squared error. We empirically demonstrate that this leads to variance reduction, faster convergence, and generally improved performance in two unsupervised latent variable models.
  arXiv  Detail & Related papers  (2020-10-09T22:54:38Z)
• Nonparametric Score Estimators [49.42469547970041]
  Estimating the score from a set of samples generated by an unknown distribution is a fundamental task in inference and learning of probabilistic models. We provide a unifying view of these estimators under the framework of regularized nonparametric regression. We propose score estimators based on iterative regularization that enjoy computational benefits from curl-free kernels and fast convergence.
  arXiv  Detail & Related papers  (2020-05-20T15:01:03Z)
• SUMO: Unbiased Estimation of Log Marginal Probability for Latent Variable Models [80.22609163316459]
  We introduce an unbiased estimator of the log marginal likelihood and its gradients for latent variable models based on randomized truncation of infinite series. We show that models trained using our estimator give better test-set likelihoods than a standard importance-sampling based approach for the same average computational cost.
  arXiv  Detail & Related papers  (2020-04-01T11:49:30Z)

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.