{
  "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.",
  "abstract_shown": true,
  "affiliations": [],
  "article_type": null,
  "arxiv": "2607.29680",
  "author_total": 3,
  "authors": [
    {
      "name": "Marco Fanizza"
    },
    {
      "name": "Ryan O'Donnell"
    },
    {
      "name": "Chirag Wadhwa"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/12fhsk6t11c9r.bib",
  "cited_by": 0,
  "doi": "10.48550/arxiv.2607.29680",
  "fulltext_url": null,
  "id": "12fhsk6t11c9r",
  "issns": [],
  "landing_url": "https://arxiv.org/abs/2607.29680",
  "language": null,
  "licence": "LicenseRef-arXiv-nonexclusive-1.0",
  "licence_label": "arXiv licence",
  "licence_source": "article",
  "licence_url": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
  "metadata_licence": "CC0-1.0",
  "native_subjects": [
    [
      "arxiv",
      "cs.DS"
    ],
    [
      "arxiv",
      "quant-ph"
    ],
    [
      "openalex",
      "1702|Quantum Information and Cryptography"
    ]
  ],
  "openalex": "W7172342741",
  "pdf_url": "https://arxiv.org/pdf/2607.29680",
  "pmcid": null,
  "pmid": null,
  "published": "2026-09-14",
  "publisher": null,
  "ris": "https://research.draconitic.com/paper/12fhsk6t11c9r.ris",
  "sources": [
    {
      "first_seen": "2026-10-30T12:21:25Z",
      "native_id": "2607.29680",
      "source": "arxiv",
      "url": "https://arxiv.org/abs/2607.29680"
    }
  ],
  "subjects": [
    {
      "field": "physics",
      "origin": "arxiv:quant-ph",
      "subfield": "quantum"
    }
  ],
  "title": "Spectrum Estimation is Almost as Hard as Tomography",
  "title_text": "Spectrum Estimation is Almost as Hard as Tomography",
  "type": "preprint",
  "updated_at": "2026-10-30T12:21:25Z",
  "url": "https://research.draconitic.com/paper/12fhsk6t11c9r",
  "venue": "arXiv",
  "versions": []
}