The Keyl-Werner algorithm is not optimal for spectrum estimation

• URL: http://arxiv.org/abs/2607.27117v1
• Date: Wed, 29 Jul 2026 16:46:05 GMT
• Title: The Keyl-Werner algorithm is not optimal for spectrum estimation
• Abstract summary: We give an algorithm which estimates the eigenvalues of $$ to constant error in total variation distance.<n>This is the first improvement to spectrum estimation over the influential Keyl-Werner algorithm.
• Score: 1.4842441810416076
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We give an algorithm which, given $n = O(d^2 \cdot (\log\log(d)/\log(d))^2)$ copies of $ρ$, estimates the eigenvalues of $ρ$ to constant error in total variation distance. Thus, we can learn the eigenvalues of a quantum state with fewer copies than the $Θ(d^2)$ needed to run full state tomography. This is the first improvement to spectrum estimation over the influential Keyl-Werner algorithm, which uses $n = Θ(d^2)$ copies, thereby resolving a question raised by Keyl and Werner in 2001 and refuting a 2016 conjecture of Wright. Our main technical tool is a new tomography guarantee, where the error of tomography in a particular direction $|w\rangle$ scales with $\langle w | ρ|w\rangle$ for all directions simultaneously. From this stronger "relative-error" bound, we recover better algorithms for principal component analysis in Bures distance and tomography in $χ^2$-divergence as corollaries.

Related papers

• Instance-optimal high-precision shadow tomography with few-copy measurements: A metrological approach [2.956729394666618]
  We study the sample complexity of shadow tomography in the high-precision regime.<n>We use possibly adaptive measurements that act on $O(mathrmpolylog(d))$ number of copies of $$ at a time.
  arXiv  Detail & Related papers  (2026-02-04T19:00:00Z)
• Shadow Tomography Against Adversaries [31.34964957208756]
  We show that all non-adaptive shadow tomography algorithms must incur an error of $varepsilon=tildeO(max_iin[M]|O_i|_HS)$ for some choice of observables.<n>We design an algorithm that achieves an error of $varepsilon=tildeO(minsqrtM, sqrtd)$ for some choice of observables, even with unlimited copies.
  arXiv  Detail & Related papers  (2025-12-05T06:06:07Z)
• Accelerated Evolving Set Processes for Local PageRank Computation [75.54334100808022]
  This work proposes a novel framework based on nested evolving set processes to accelerate Personalized PageRank computation.<n>We show that the time complexity of such localized methods is upper bounded by $mintildemathcalO(R2/epsilon2), tildemathcalO(m)$ to obtain an $epsilon$-approximation of the PPR vector.
  arXiv  Detail & Related papers  (2025-10-09T09:47:40Z)
• The debiased Keyl's algorithm: a new unbiased estimator for full state tomography [1.4302622916198997]
  We present the debiased Keyl's algorithm, the first estimator for full state tomography which is both unbiased and sample-optimal.<n>We show that $n = O(rd/varepsilon2)$ copies are sufficient to learn a rank-$r$ mixed state to trace distance error $varepsilon$, which is optimal.<n>We further show that $n = O(rd/varepsilon2)$ copies are sufficient to learn to error $varepsilon$ in the more challenging Bures distance, which is also optimal.
  arXiv  Detail & Related papers  (2025-10-09T05:07:12Z)
• Near-Optimal Differentially Private Graph Algorithms via the Multidimensional AboveThreshold Mechanism [5.4971134662997025]
  We formulate a novel generalized sparse vector technique which generalizes SVT to vectors with multiple dimensions.<n>As an application, we solve a number of important graph problems with better bounds than previous work.<n>We give a tight local edge DP algorithm for $k$-core decomposition with $O(epsilon-1log n)$ additive error and no multiplicative error in $O(n)$ rounds.
  arXiv  Detail & Related papers  (2025-08-04T08:26:58Z)
• Beating full state tomography for unentangled spectrum estimation [4.162538161344671]
  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.
  arXiv  Detail & Related papers  (2025-04-03T17:29:12Z)
• Distribution-Independent Regression for Generalized Linear Models with Oblivious Corruptions [49.69852011882769]
  We show the first algorithms for the problem of regression for generalized linear models (GLMs) in the presence of additive oblivious noise. We present an algorithm that tackles newthis problem in its most general distribution-independent setting. This is the first newalgorithmic result for GLM regression newwith oblivious noise which can handle more than half the samples being arbitrarily corrupted.
  arXiv  Detail & Related papers  (2023-09-20T21:41:59Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss. Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
  arXiv  Detail & Related papers  (2023-07-24T14:37:22Z)
• Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
  Detection of a planted dense subgraph in a random graph is a fundamental statistical and computational problem. We consider detecting the presence of a planted $Gr(ngamma, n-alpha)$ subhypergraph in a $Gr(n, n-beta) hypergraph. Our results are already new in the graph case $r=2$, as we consider the subtle log-density regime where hardness based on average-case reductions is not known.
  arXiv  Detail & Related papers  (2023-04-17T10:38:08Z)
• Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
  We show that HSDMPG can attain an $mathcalObig (1/sttnbig)$ which is at the order of excess error on a learning model. For loss factors, we prove that HSDMPG can attain an $mathcalObig (1/sttnbig)$ which is at the order of excess error on a learning model.
  arXiv  Detail & Related papers  (2020-09-18T02:18:44Z)
• 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)

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.