Journal article · 2025 · Open access
Lower Bounds for Learning Quantum States with Single-Copy Measurements
ACM Transactions on Computation Theory, 17(1), 1–42 · Published 13 February 2025 · DOI 10.1145/3717450
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
| Year | Citations | Share of the best year |
|---|---|---|
| 2023 | 7 | |
| 2024 | 4 | |
| 2025 | 12 | |
| 2026 | 33 |
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
- ImageNet classification with deep convolutional neural networksAlex Krizhevsky, Ilya Sutskever, Geoffrey E. Hinton · Communications of the ACM · 2017 · 114,726 citations
- Long Short-Term MemorySepp Hochreiter, Jürgen Schmidhuber · Neural Computation · 1997 · 109,097 citations
- A Mathematical Theory of CommunicationClaude E. Shannon · Bell System Technical Journal · 1948 · 91,736 citations
- Deep learningYann LeCun, Yoshua Bengio, Geoffrey E. Hinton · Nature · 2015 · 90,226 citations
- Faster R-CNN: Towards Real-Time Object Detection with Region Proposal NetworksShaoqing Ren, Kaiming He, Ross Girshick and 1 more · IEEE Transactions on Pattern Analysis and Machine Intelligence · 2016 · 74,143 citations
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.