Sample-optimal classical shadows for pure states

• URL: http://arxiv.org/abs/2211.11810v2
• Date: Mon, 13 May 2024 18:53:44 GMT
• Title: Sample-optimal classical shadows for pure states
• Authors: Daniel Grier, Hakop Pashayan, Luke Schaeffer,
• Abstract summary: We consider the classical shadows task for pure states in the setting of both joint and independent measurements. In the independent measurement setting, we show that $mathcal O(sqrtBd epsilon-1 + epsilon-2)$ samples suffice.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the classical shadows task for pure states in the setting of both joint and independent measurements. The task is to measure few copies of an unknown pure state $\rho$ in order to learn a classical description which suffices to later estimate expectation values of observables. Specifically, the goal is to approximate $\mathrm{Tr}(O \rho)$ for any Hermitian observable $O$ to within additive error $\epsilon$ provided $\mathrm{Tr}(O^2)\leq B$ and $\lVert O \rVert = 1$. Our main result applies to the joint measurement setting, where we show $\tilde{\Theta}(\sqrt{B}\epsilon^{-1} + \epsilon^{-2})$ samples of $\rho$ are necessary and sufficient to succeed with high probability. The upper bound is a quadratic improvement on the previous best sample complexity known for this problem. For the lower bound, we see that the bottleneck is not how fast we can learn the state but rather how much any classical description of $\rho$ can be compressed for observable estimation. In the independent measurement setting, we show that $\mathcal O(\sqrt{Bd} \epsilon^{-1} + \epsilon^{-2})$ samples suffice. Notably, this implies that the random Clifford measurements algorithm of Huang, Kueng, and Preskill, which is sample-optimal for mixed states, is not optimal for pure states. Interestingly, our result also uses the same random Clifford measurements but employs a different estimator.

Related papers

• Optimal high-precision shadow estimation [22.01044188849049]
  Formally we give a protocol that measures $O(log(m)/epsilon2)$ copies of an unknown mixed state $rhoinmathbbCdtimes d$. We show via dimensionality reduction that we can rescale $epsilon$ and $d$ to reduce to the regime where $epsilon le O(d-1/2)$.
  arXiv  Detail & Related papers  (2024-07-18T19:42:49Z)
• Principal eigenstate classical shadows [0.0]
  Given many copies of an unknown quantum state $rho$, we consider the task of learning a classical description of its principal eigenstate. We present a protocol for this task scaling with the principal eigenvalue $lambda$ and show that it is optimal within a space of natural approaches.
  arXiv  Detail & Related papers  (2024-05-22T19:13:05Z)
• Better and Simpler Lower Bounds for Differentially Private Statistical Estimation [7.693388437377614]
  We prove that for any $alpha le O(1)$, estimating the covariance of a Gaussian up to spectral error $alpha$ requires $tildeOmegaleft(fracd3/2alpha varepsilon + fracdalpha2right)$ samples. Next, we prove that estimating the mean of a heavy-tailed distribution with bounded $k$th moments requires $tildeOmegaleft(fracdalphak/(k-1) varepsilon +
  arXiv  Detail & Related papers  (2023-10-10T04:02:43Z)
• Memory Efficient And Minimax Distribution Estimation Under Wasserstein Distance Using Bayesian Histograms [6.21295508577576]
  We show that when $d 2v$, histograms possess a special textitmemory efficiency property, in reference to the sample size $n, order $nd/2v$ bins are needed to obtain minimax rate optimality. The attained memory footprint overcomes existing minimax optimal procedures by a factor in $n$; for example an $n1 - d/2v$ factor reduction in the footprint when compared to the empirical measure, a minimax estimator in the Borel probability measure class.
  arXiv  Detail & Related papers  (2023-07-19T16:13:20Z)
• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  We show that any efficient SQ algorithm for the problem requires sample complexity at least $Omega(d1/2/(maxp, epsilon)2)$. Our lower bound suggests that this quadratic dependence on $1/epsilon$ is inherent for efficient algorithms.
  arXiv  Detail & Related papers  (2023-07-13T18:59:28Z)
• Quantum tomography using state-preparation unitaries [0.22940141855172028]
  We describe algorithms to obtain an approximate classical description of a $d$-dimensional quantum state when given access to a unitary. We show that it takes $widetildeTheta(d/varepsilon)$ applications of the unitary to obtain an $varepsilon$-$ell$-approximation of the state. We give an efficient algorithm for obtaining Schatten $q$-optimal estimates of a rank-$r$ mixed state.
  arXiv  Detail & Related papers  (2022-07-18T17:56:18Z)
• Approximate Function Evaluation via Multi-Armed Bandits [51.146684847667125]
  We study the problem of estimating the value of a known smooth function $f$ at an unknown point $boldsymbolmu in mathbbRn$, where each component $mu_i$ can be sampled via a noisy oracle. We design an instance-adaptive algorithm that learns to sample according to the importance of each coordinate, and with probability at least $1-delta$ returns an $epsilon$ accurate estimate of $f(boldsymbolmu)$.
  arXiv  Detail & Related papers  (2022-03-18T18:50:52Z)
• Optimal Mean Estimation without a Variance [103.26777953032537]
  We study the problem of heavy-tailed mean estimation in settings where the variance of the data-generating distribution does not exist. We design an estimator which attains the smallest possible confidence interval as a function of $n,d,delta$.
  arXiv  Detail & Related papers  (2020-11-24T22:39:21Z)
• Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction [63.41789556777387]
  Asynchronous Q-learning aims to learn the optimal action-value function (or Q-function) of a Markov decision process (MDP) We show that the number of samples needed to yield an entrywise $varepsilon$-accurate estimate of the Q-function is at most on the order of $frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$ up to some logarithmic factor.
  arXiv  Detail & Related papers  (2020-06-04T17:51:00Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  We output a distribution from $mathcalQ$ whose total variation distance to $p$ is comparable to the best such distribution. We show that the constraint of local differential privacy incurs an exponential increase in cost. Our algorithms result in exponential improvements on the round complexity of previous methods.
  arXiv  Detail & Related papers  (2020-02-21T18:30:48Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  We show that extending the smoothing technique to defend against other attack models can be challenging. We present experimental results on CIFAR to validate our theory.
  arXiv  Detail & Related papers  (2020-02-08T22:02:14Z)

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.