Spectrum Estimation is Almost as Hard as Tomography

• URL: http://arxiv.org/abs/2607.29680v1
• Date: Fri, 31 Jul 2026 17:57:03 GMT
• Title: Spectrum Estimation is Almost as Hard as Tomography
• Abstract summary: We prove a sample complexity lower bound of $(d2-)$ for spectrum estimation to constant sorted total-variation error.<n>Our hard instances are constructed from sandwiched products of Haar-random projectors.
• Score: 1.7205106391379026
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the sample complexity of estimating and testing fundamental unitarily invariant properties of unknown quantum states; namely, the tasks of spectrum estimation, von Neumann entropy estimation, and rank-testing. For $d$-dimensional states, and for every $γ>0$, we prove a sample complexity lower bound of $Ω(d^{2-γ})$ for spectrum estimation to constant sorted total-variation error, entropy estimation to constant additive error, and rank-testing to constant trace distance. Our hard instances are constructed from sandwiched products of Haar-random projectors, suitably normalized using a novel technique that lets us derive explicit expressions for high-order tensor moments of the resultant states. These moments can be expressed as symmetric functions of Jucys--Murphy elements of the symmetric group algebra. To show that two such mixtures are indistinguishable, we analyze the log-likelihood ratio and perform moment-matching, i.e., we set its low-order Jucys--Murphy components to zero. Indistinguishability is then obtained by bounding an $f$-divergence through the high-order components; the non-zero high-order terms and concentration of functions of Haar-random unitaries also imply separations in typical spectra, entropies, and ranks, proving all our lower bounds.

Related papers

• Uniqueness and Cramér-Rao Efficiency of Quantum U-Statistics [8.156494881838947]
  We study unbiased estimation of scalar-valued functionals of quantum states from independent copies.<n>We prove that, among unbiased permutation-invariant estimators, the quantum U-statistic is the unique extension to an arbitrary number of copies.
  arXiv  Detail & Related papers  (2026-09-08T13:37:19Z)
• Spectral Convergence of Random Feature Method in Multiple Dimensions [5.361030050051251]
  We first prove spectral convergence of the random feature method (RFM) for multidimensional targets in Sobolev, Gevrey, ultra-analytic, and bandlimited classes.<n>The analysis identifies a common mechanism: the same spectral approximation that yields high accuracy also drives severe ill-conditioning.
  arXiv  Detail & Related papers  (2026-09-03T06:01:00Z)
• Time-series Random Process Complexity Ranking Using a Bound on Conditional Differential Entropy [0.8666096694354596]
  We build on the information theoretic prediction error bounds established by Fang et al.<n>We show that conditional differential entropy textbf$h(X_k mid X_k-1,...,X_k-m)$ is upper bounded by a function of the determinant of next-step prediction errors.
  arXiv  Detail & Related papers  (2025-10-23T13:36:04Z)
• Tensor cumulants for statistical inference on invariant distributions [49.80012009682584]
  We show that PCA becomes computationally hard at a critical value of the signal's magnitude. We define a new set of objects, which provide an explicit, near-orthogonal basis for invariants of a given degree. It also lets us analyze a new problem of distinguishing between different ensembles.
  arXiv  Detail & Related papers  (2024-04-29T14:33:24Z)
• Sampling and estimation on manifolds using the Langevin diffusion [45.57801520690309]
  Two estimators of linear functionals of $mu_phi $ based on the discretized Markov process are considered.<n>Error bounds are derived for sampling and estimation using a discretization of an intrinsically defined Langevin diffusion.
  arXiv  Detail & Related papers  (2023-12-22T18:01:11Z)
• Random Lindblad operators obeying detailed balance [0.18899300124593646]
  We introduce different ensembles of random Lindblad operators $cal L$, which satisfy quantum detailed balance condition with respect to the given stationary state $sigma$ of size $N$. We show that similar universal properties hold for the detailed balance-obeying Kolmogorov generators obtained by applying superdecoherence to an ensemble of random Davies generators.
  arXiv  Detail & Related papers  (2023-04-06T09:38:16Z)
• Extremal jumps of circuit complexity of unitary evolutions generated by random Hamiltonians [0.0]
  We investigate circuit complexity of unitaries generated by time evolution of randomly chosen strongly interacting Hamiltonians in finite dimensional Hilbert spaces. We prove that the complexity of $exp(-it H)$ exhibits a surprising behaviour -- with high probability it reaches the maximal allowed value on the same time scale as needed to escape the neighborhood of the identity consisting of unitaries with trivial (zero) complexity.
  arXiv  Detail & Related papers  (2023-03-30T17:05:06Z)
• Near-Optimal Non-Parametric Sequential Tests and Confidence Sequences with Possibly Dependent Observations [44.71254888821376]
  We provide the first type-I-error and expected-rejection-time guarantees under general non-data generating processes. We show how to apply our results to inference on parameters defined by estimating equations, such as average treatment effects.
  arXiv  Detail & Related papers  (2022-12-29T18:37:08Z)
• Clipped Stochastic Methods for Variational Inequalities with Heavy-Tailed Noise [64.85879194013407]
  We prove the first high-probability results with logarithmic dependence on the confidence level for methods for solving monotone and structured non-monotone VIPs. Our results match the best-known ones in the light-tails case and are novel for structured non-monotone problems. In addition, we numerically validate that the gradient noise of many practical formulations is heavy-tailed and show that clipping improves the performance of SEG/SGDA.
  arXiv  Detail & Related papers  (2022-06-02T15:21:55Z)
• Tight Exponential Analysis for Smoothing the Max-Relative Entropy and for Quantum Privacy Amplification [56.61325554836984]
  The max-relative entropy together with its smoothed version is a basic tool in quantum information theory. We derive the exact exponent for the decay of the small modification of the quantum state in smoothing the max-relative entropy based on purified distance.
  arXiv  Detail & Related papers  (2021-11-01T16:35:41Z)
• Mean-Square Analysis with An Application to Optimal Dimension Dependence of Langevin Monte Carlo [60.785586069299356]
  This work provides a general framework for the non-asymotic analysis of sampling error in 2-Wasserstein distance. Our theoretical analysis is further validated by numerical experiments.
  arXiv  Detail & Related papers  (2021-09-08T18:00:05Z)
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
  This paper shows that graph spectral embedding using the random walk Laplacian produces vector representations which are completely corrected for node degree. In the special case of a degree-corrected block model, the embedding concentrates about K distinct points, representing communities.
  arXiv  Detail & Related papers  (2021-05-03T16:36:27Z)

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.