Journal article · 2025 · Open access

Lower Bounds for Learning Quantum States with Single-Copy Measurements

Angus Lowe, Ashwin Nayak

ACM Transactions on Computation Theory, 17(1), 1–42 · Published 13 February 2025 · DOI 10.1145/3717450

Open PDFView at the publisherCite this paper

In brief

“Lower Bounds for Learning Quantum States with Single-Copy Measurements” is a 2025 journal article by Angus Lowe and Ashwin Nayak, published in ACM Transactions on Computation Theory. OpenAlex counts 56 citations as of 19 November 2026, which puts it in the top 4% of works published in 2025 by citations. It is open access: the full text is free to read at arXiv (Cornell University).

Citations
56
Most cited in
2026 (33)
Field-weighted impact
8.57
References
48
Authors
2

Abstract

We study the problems of quantum tomography and shadow tomography using measurements performed on individual, identical copies of an unknown d -dimensional state. We first revisit known lower bounds [ 23 ] on quantum tomography with accuracy ε in trace distance, when the measurement choices are independent of previously observed outcomes, i.e., they are nonadaptive. We give a succinct proof of these results through the χ 2 -divergence between suitable distributions. Unlike prior work, we do not require that the measurements be given by rank-one operators. This leads to stronger lower bounds when the learner uses measurements with a constant number of outcomes (e.g., two-outcome measurements). In particular, this rigorously establishes the optimality of the folklore “Pauli tomography” algorithm in terms of its sample complexity. We also derive novel bounds of \(\Omega (r^2 d/\epsilon ^2)\) and \(\Omega (r^2 d^2/\epsilon ^2)\) for learning rank r states using arbitrary and constant-outcome measurements, respectively, in the nonadaptive case. In addition to the sample complexity, a resource of practical significance for learning quantum states is the number of unique measurement settings required (i.e., the number of different measurements used by an algorithm, each possibly with an arbitrary number of outcomes). Motivated by this consideration, we employ concentration of measure of χ 2 -divergence of suitable distributions to extend our lower bounds to the case where the learner performs possibly adaptive measurements from a fixed set of \(\exp (O(d))\) possible measurements. This implies in particular that adaptivity does not give us any advantage using single-copy measurements that are efficiently implementable. We also obtain a similar bound in the case where the goal is to predict the expectation values of a given sequence of observables, a task known as shadow tomography. Finally, in the case of adaptive, single-copy measurements implementable with polynomial-size circuits, we prove that a straightforward strategy based on computing sample means of the given observables is optimal.

Cite this paper

Formatted from the catalogue record. Check names, capitals and page numbers against the paper before you submit.

APA 7

Lowe, A., & Nayak, A. (2025). Lower Bounds for Learning Quantum States with Single-Copy Measurements. ACM Transactions on Computation Theory, 17(1), 1–42. https://doi.org/10.1145/3717450

MLA 9

Lowe, Angus, and Ashwin Nayak. “Lower Bounds for Learning Quantum States with Single-Copy Measurements.” ACM Transactions on Computation Theory, vol. 17, no. 1, 2025, pp. 1–42. https://doi.org/10.1145/3717450.

Chicago

Lowe, Angus and Ashwin Nayak. 2025. “Lower Bounds for Learning Quantum States with Single-Copy Measurements.” ACM Transactions on Computation Theory 17 (1): 1–42. https://doi.org/10.1145/3717450.

Harvard

Lowe, A. and Nayak, A. (2025) ‘Lower Bounds for Learning Quantum States with Single-Copy Measurements’, ACM Transactions on Computation Theory, 17(1), pp. 1–42. doi:10.1145/3717450.

IEEE

A. Lowe and A. Nayak, “Lower Bounds for Learning Quantum States with Single-Copy Measurements,” ACM Transactions on Computation Theory, vol. 17, no. 1, pp. 1–42, 2025, doi: 10.1145/3717450.

BibTeX

@article{lowe2025lower,
  title     = {{Lower Bounds for Learning Quantum States with Single-Copy Measurements}},
  author    = {Lowe, Angus and Nayak, Ashwin},
  journal   = {ACM Transactions on Computation Theory},
  year      = {2025},
  volume    = {17},
  number    = {1},
  pages     = {1--42},
  doi       = {10.1145/3717450},
  url       = {https://doi.org/10.1145/3717450}
}

Download for a reference manager: BibTeX (.bib) · RIS for Zotero, Mendeley and EndNote (.ris)

Citations by year

YearCitationsShare of the best year
202377
202444
20251212
20263333

Its field-weighted citation impact is 8.57: it has been cited 8.57 times as often as the average work of the same field, type and year (1.00 is the world average).

Topic and keywords

Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture

  • quantum state tomography
  • shadow tomography
  • sample complexity
  • lower bounds
  • adaptive measurement
  • chi-square divergence
  • concentration of measure
  • trace distance

Work with this paper

Most-cited papers in Computer Science

All highly cited Computer Science papers

Questions about this paper

How do I cite this paper in APA style?

Lowe, A., & Nayak, A. (2025). Lower Bounds for Learning Quantum States with Single-Copy Measurements. ACM Transactions on Computation Theory, 17(1), 1–42. https://doi.org/10.1145/3717450

How many times has this paper been cited?

56 times, according to OpenAlex on 19 November 2026. Google Scholar and Scopus count different sets of sources, so their numbers differ.

Is this paper free to read?

Yes. It is open access at arXiv (Cornell University): sign in and open the PDF from this page.

Who wrote this paper?

Angus Lowe, Ashwin Nayak.

What is the DOI of this paper?

10.1145/3717450, permanently at https://doi.org/10.1145/3717450. Sign in and open it from this page.

Bibliographic data from OpenAlex (CC0), last checked 19 November 2026. ResearchGuru does not host this paper; once you are signed in, the links open it at the publisher or the repository that does.