Conference paper · 2024 · Open access
An Optimal Tradeoff between Entanglement and Copy Complexity for State Tomography
ACM Symposium on Theory of Computing (STOC), 1331–1342 · Published 10 June 2024 · DOI 10.1145/3618260.3649704
In brief
“An Optimal Tradeoff between Entanglement and Copy Complexity for State Tomography” is a 2024 conference paper by Sitan Chen and 2 co-authors, published in ACM Symposium on Theory of Computing (STOC). OpenAlex counts 48 citations as of 19 November 2026, which puts it in the top 3% of works published in 2024 by citations. It is open access under a CC BY licence: the full text is free to read at ACM Symposium on Theory of Computing (STOC).
- Citations
- 48
- Most cited in
- 2026 (29)
- Field-weighted impact
- 4.16
- References
- 34
- Authors
- 3
Abstract
There has been significant interest in understanding how practical constraints on contemporary quantum devices impact the complexity of quantum learning. For the classic question of tomography, recent work tightly characterized the copy complexity for any protocol that can only measure one copy of the unknown state at a time, showing it is polynomially worse than if one can make fully-entangled measurements. While we now have a fairly complete picture of the rates for such tasks in the near-term and fault-tolerant regimes, it remains poorly understood what the landscape in between these extremes looks like, and in particular how to gracefully scale up our protocols as we transition away from NISQ. In this work, we study tomography in the natural setting where one can make measurements of t copies at a time. For sufficiently small є, we show that for any t ≤ d2, Θ(d3/√tє2) copies are necessary and sufficient to learn an unknown d-dimensional state ρ to trace distance є. This gives a smooth and optimal interpolation between the known rates for single-copy measurements and fully-entangled measurements. To our knowledge, this is the first smooth entanglement-copy tradeoff known for any quantum learning task, and for tomography, no intermediate point on this curve was known, even at t = 2. An important obstacle is that unlike the optimal single-copy protocol, the optimal fully-entangled protocol is inherently a biased estimator. This bias precludes naive batching approaches for interpolating between the two protocols. Instead, we devise a novel two-stage procedure that uses Keyl’s algorithm to refine a crude estimate for ρ based on single-copy measurements. A key insight is to use Schur-Weyl sampling not to estimate the spectrum of ρ, but to estimate the deviation of ρ from the maximally mixed state. When ρ is far from the maximally mixed state, we devise a novel quantum splitting procedure that reduces to the case where ρ is close to maximally mixed.
Cite this paper
Formatted from the catalogue record. Check names, capitals and page numbers against the paper before you submit.
APA 7
Chen, S., Li, J. Z., & Liu, A. (2024). An Optimal Tradeoff between Entanglement and Copy Complexity for State Tomography. ACM Symposium on Theory of Computing (STOC), 1331–1342. https://doi.org/10.1145/3618260.3649704
MLA 9
Chen, Sitan, et al. “An Optimal Tradeoff between Entanglement and Copy Complexity for State Tomography.” ACM Symposium on Theory of Computing (STOC), 2024, pp. 1331–1342. https://doi.org/10.1145/3618260.3649704.
Chicago
Chen, Sitan, Jerry Zheng Li, and Allen Liu. 2024. “An Optimal Tradeoff between Entanglement and Copy Complexity for State Tomography.” ACM Symposium on Theory of Computing (STOC): 1331–1342. https://doi.org/10.1145/3618260.3649704.
Harvard
Chen, S., Li, J. Z. and Liu, A. (2024) ‘An Optimal Tradeoff between Entanglement and Copy Complexity for State Tomography’, ACM Symposium on Theory of Computing (STOC), pp. 1331–1342. doi:10.1145/3618260.3649704.
IEEE
S. Chen, J. Z. Li, and A. Liu, “An Optimal Tradeoff between Entanglement and Copy Complexity for State Tomography,” ACM Symposium on Theory of Computing (STOC), pp. 1331–1342, 2024, doi: 10.1145/3618260.3649704.
BibTeX
@inproceedings{chen2024optimal,
title = {{An Optimal Tradeoff between Entanglement and Copy Complexity for State Tomography}},
author = {Chen, Sitan and Li, Jerry Zheng and Liu, Allen},
booktitle = {ACM Symposium on Theory of Computing (STOC)},
year = {2024},
pages = {1331--1342},
doi = {10.1145/3618260.3649704},
url = {https://doi.org/10.1145/3618260.3649704}
}
Download for a reference manager: BibTeX (.bib) · RIS for Zotero, Mendeley and EndNote (.ris)
Citations by year
| Year | Citations | Share of the best year |
|---|---|---|
| 2024 | 6 | |
| 2025 | 13 | |
| 2026 | 29 |
Its field-weighted citation impact is 4.16: it has been cited 4.16 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
- NISQ devices
- quantum machine learning
- trace distance
- two-stage estimation
- biased estimators
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?
Chen, S., Li, J. Z., & Liu, A. (2024). An Optimal Tradeoff between Entanglement and Copy Complexity for State Tomography. ACM Symposium on Theory of Computing (STOC), 1331–1342. https://doi.org/10.1145/3618260.3649704
How many times has this paper been cited?
48 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 ACM Symposium on Theory of Computing (STOC): sign in and open the PDF from this page.
Who wrote this paper?
Sitan Chen, Jerry Zheng Li, Allen Liu.
What is the DOI of this paper?
10.1145/3618260.3649704, permanently at https://doi.org/10.1145/3618260.3649704. 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.