Tight Lower Bounds for State Tomography with Limited Entanglement
Abstract
We study state tomography when each measurement acts on at most k fresh copies and no quantum memory is retained between blocks. We prove a lower bound matching the upper bound in [arXiv:2510.07788]. Thus the copy complexity of estimating an arbitrary d-dimensional state to trace distance ε is, up to absolute constant factors, max{d3/(√kε2),d2/ε2} for every k and all sufficiently small ε. This removes the earlier restriction that k be small as a function of the accuracy. The lower bound applies to arbitrary measurements within each block and adaptive choices between blocks. The lower bound already applies in a small neighborhood of any state whose smallest eigenvalue is of order 1/d, even when the center is known. The main ingredient is a uniform Fisher information bound for one measurement block that depends only on the smallest eigenvalue of the state. The proof avoids the perturbative expansion responsible for the restriction in [arXiv:2402.16353]. Fano's inequality for metric balls and a log-Sobolev comparison between mutual and Fisher information then reduce the adaptive protocol to this block bound [arXiv:1607.00550, arXiv:1902.08582].
Related
- Tight Lower Bounds under Matched High-Order Hölder Smoothness and Uniform Convexity
- Tight Lower Bounds for Stochastic Nonconvex-Strongly-Concave Minimax Optimization
- Tight lower bounds for Lipschitz geodesically convex optimization on hyperbolic space
- Feature Priming in Online Linear Regression: Sparse-Regret Lower Bounds and Tight Coordinatewise Rates
- Tight Bounds for Equivalence Testing with Non-Adaptive Conditional Samples
BibTeX
@misc{keskin2026tight,
title = {{Tight Lower Bounds for State Tomography with Limited Entanglement}},
author = {Ufuk Keskin and Jason Luo and Mahbod Majid and Matthew Radzihovsky},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.05718},
eprint = {2609.05718},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.05718},
}
RIS
TY - UNPB
TI - Tight Lower Bounds for State Tomography with Limited Entanglement
AU - Ufuk Keskin
AU - Jason Luo
AU - Mahbod Majid
AU - Matthew Radzihovsky
PY - 2026
DA - 2026/09/04
PB - arXiv
DO - 10.48550/arxiv.2609.05718
UR - https://arxiv.org/abs/2609.05718
AB - We study state tomography when each measurement acts on at most k fresh copies and no quantum memory is retained between blocks. We prove a lower bound matching the upper bound in [arXiv:2510.07788]. Thus the copy complexity of estimating an arbitrary d-dimensional state to trace distance ε is, up to absolute constant factors, max{d^3/(√kε^2),d^2/ε^2} for every k and all sufficiently small ε. This removes the earlier restriction that k be small as a function of the accuracy. The lower bound applies to arbitrary measurements within each block and adaptive choices between blocks. The lower bound already applies in a small neighborhood of any state whose smallest eigenvalue is of order 1/d, even when the center is known. The main ingredient is a uniform Fisher information bound for one measurement block that depends only on the smallest eigenvalue of the state. The proof avoids the perturbative expansion responsible for the restriction in [arXiv:2402.16353]. Fano's inequality for metric balls and a log-Sobolev comparison between mutual and Fisher information then reduce the adaptive protocol to this block bound [arXiv:1607.00550, arXiv:1902.08582].
ER -