Optimality of the Keyl–Werner spectrum estimator

Let $\rho\in\mathbb{C}^{d\times d}$ be an unknown quantum state with spectrum $\alpha=(\alpha_{1},\ldots,\alpha_{d})$ . Given copies of $\rho$ , estimate $\alpha$ to total variation error at most $\varepsilon$ with constant success probability. In the regime of sufficiently large $\varepsilon$ , conjecture that the optimal copy complexity is

n=\Theta\left(\frac{d^{2}}{\log^{2}(d)\,\varepsilon^{2}}\right),

up to possible additional $\log\log(d)$ factors. The cited paper notes that this conjecture concerns the optimal spectrum-estimation complexity, not necessarily the optimality of the Keyl--Werner estimator itself.

The problem asks whether weak Schur sampling, introduced by Keyl and Werner, achieves the optimal sample complexity for learning a quantum state’s spectrum. The question was explicitly posed by Wright in 2016 and by Anshu and Arunachalam in 2023.

Known results

Keyl–Werner analysis: upper bound $O(d^{2}/\varepsilon^{2})$ .
Some instances require $\Omega(d^{2}/\varepsilon^{2})$ samples.
The general lower bound was only $\Omega(d/\varepsilon^{2})$ .
Wright’s 2016 conjecture predicted that only one logarithmic factor could be saved.

July 2026 counterexample

A preprint gives an alternative estimator using $O\!\left(d^{2}(\log\log d)^{2}/(\varepsilon^{4}(\log d)^{2})\right)$ copies. For $\varepsilon=\omega(\log\log(d)/\log(d))$ , this is asymptotically smaller than Keyl–Werner; for constant error it saves two logarithmic factors and refutes Wright’s conjectured lower bound. The optimal complexity outside this regime remains open.

Current status (as of July 2026): Keyl–Werner is not asymptotically optimal in the stated regime, while the optimal spectrum-estimation complexity remains unresolved.

Optimality of the Keyl–Werner spectrum estimator

Progress summary

Solutions 0