Beating full state tomography for unentangled spectrum estimation

• URL: http://arxiv.org/abs/2504.02785v1
• Date: Thu, 03 Apr 2025 17:29:12 GMT
• Title: Beating full state tomography for unentangled spectrum estimation
• Authors: Angelos Pelecanos, Xinyu Tan, Ewin Tang, John Wright,
• Abstract summary: Best known algorithms for spectrum estimation require as many copies as full state tomography.<n>We show that this is not the case in the setting of unentangled measurements.<n>We present numerical evidence that the sample complexity of spectrum estimation can only improve over full state tomography by a sub-nomial factor.
• Score: 4.162538161344671
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: How many copies of a mixed state $\rho \in \mathbb{C}^{d \times d}$ are needed to learn its spectrum? To date, the best known algorithms for spectrum estimation require as many copies as full state tomography, suggesting the possibility that learning a state's spectrum might be as difficult as learning the entire state. We show that this is not the case in the setting of unentangled measurements, by giving a spectrum estimation algorithm that uses $n = O(d^3\cdot (\log\log(d) / \log(d))^4 )$ copies of $\rho$, which is asymptotically fewer than the $n = \Omega(d^3)$ copies necessary for full state tomography. Our algorithm is inspired by the technique of local moment matching from classical statistics, and shows how it can be applied in the quantum setting. As an important subroutine in our spectrum estimation algorithm, we give an estimator of the $k$-th moment $\operatorname{tr}(\rho^k)$ which performs unentangled measurements and uses $O(d^{3-2/k})$ copies of $\rho$ in order to achieve a constant multiplicative error. This directly translates to an additive-error estimator of quantum Renyi entropy of order $k$ with the same number of copies. Finally, we present numerical evidence that the sample complexity of spectrum estimation can only improve over full state tomography by a sub-polynomial factor. Specifically, for spectrum learning with fully entangled measurements, we run simulations which suggest a lower bound of $\Omega(d^{2 - \gamma})$ copies for any constant $\gamma > 0$. From this, we conclude the current best lower bound of $\Omega(d)$ is likely not tight.

Related papers

• Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
  Previous private estimators on distributions over $mathRd suffer from a curse of dimensionality. We present an algorithm whose sample complexity has improved dependence on dimension.
  arXiv  Detail & Related papers  (2024-11-01T17:59:53Z)
• 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)
• An optimal tradeoff between entanglement and copy complexity for state tomography [24.737530909081915]
  We study tomography in the natural setting where one can make measurements of $t$ copies at a time. This is the first smooth entanglement-copy protocol known for any quantum learning task. A key insight is to use SchurilonWeyl sampling not to estimate the spectrum of $rho$, but to estimate the deviation of $rho$ from the maximally mixed state.
  arXiv  Detail & Related papers  (2024-02-26T07:18:57Z)
• 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)
• Learning Distributions over Quantum Measurement Outcomes [4.467248776406005]
  Shadow tomography for quantum states provides a sample efficient approach for predicting the properties of quantum systems. We develop an online shadow tomography procedure that solves this problem with high success probability.
  arXiv  Detail & Related papers  (2022-09-07T09:08:58Z)
• 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)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  We study a function of the form $mathbfxmapstosigma(mathbfwcdotmathbfx)$ for monotone activations. The goal of the learner is to output a hypothesis vector $mathbfw$ that $F(mathbbw)=C, epsilon$ with high probability.
  arXiv  Detail & Related papers  (2022-06-17T17:55:43Z)
• When Does Adaptivity Help for Quantum State Learning? [19.89243001385691]
  We show that any protocol using incoherent measurements requires $Omega(d3/epsilon2)$ copies, matching the best known upper bound. We give an adaptive algorithm that outputs a state which is $gamma$-close in infidelity to $rho$ using only $tildeO(d3/gamma)$ copies, which is optimal for incoherent measurements.
  arXiv  Detail & Related papers  (2022-06-10T17:59:16Z)
• Hardness of Learning Halfspaces with Massart Noise [56.98280399449707]
  We study the complexity of PAC learning halfspaces in the presence of Massart (bounded) noise. We show that there an exponential gap between the information-theoretically optimal error and the best error that can be achieved by a SQ algorithm.
  arXiv  Detail & Related papers  (2020-12-17T16:43:11Z)
• Streaming Complexity of SVMs [110.63976030971106]
  We study the space complexity of solving the bias-regularized SVM problem in the streaming model. We show that for both problems, for dimensions of $frac1lambdaepsilon$, one can obtain streaming algorithms with spacely smaller than $frac1lambdaepsilon$.
  arXiv  Detail & Related papers  (2020-07-07T17:10:00Z)
• Spectral density estimation with the Gaussian Integral Transform [91.3755431537592]
  spectral density operator $hatrho(omega)=delta(omega-hatH)$ plays a central role in linear response theory. We describe a near optimal quantum algorithm providing an approximation to the spectral density.
  arXiv  Detail & Related papers  (2020-04-10T03:14:38Z)

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.