Paper Overview
Field: Machine Learning / Quantum Information Authors: Ashwin Nayak, Xingyu Zhou Published: 2026-09-09 arXiv: 2609.10514
Summary
This paper determines the optimal sample complexity of low-rank quantum state tomography when each measurement may act jointly on at most \(t\) samples.
For sufficiently small \(\varepsilon\), estimating an unknown state on \(\mathbb{C}^d\) of rank at most \(r\) to trace norm error \(\varepsilon\) with constant success probability requires, and is achievable with,
\[\Theta\left( \frac{dr}{\varepsilon^2} \max\left\{1,\frac r{\sqrt t}\right\} \right)\]
samples.
Key Results
- Lower bound is adaptive-robust: the lower bound allows the protocol to choose each joint measurement adaptively using all previous classical outcomes; the matching upper bound is nonadaptive.
- Speedup limit: joint measurements on at most \(t\) samples improve the complexity of algorithms making single-sample measurements by at most a factor \(\sqrt t\).
- Collective rate threshold: measuring order \(r^2\) samples jointly is necessary and sufficient to attain the unrestricted collective rate.
- Lower bound: vary the support of a state with fixed uniform spectrum and bound the Fisher information trace of every joint measurement on \(t\) samples. The adaptive Fisher chain rule and the van Trees inequality then give the trace norm lower bound.
- Upper bound: construct and analyze a nonadaptive tomography protocol based on a Gaussian joint measurement. An explicit second moment identity and a conditional Gaussian law outside the state's support give a rank-dependent error analysis, yielding the matching rate.
Proof Techniques
*Auto-collected on 2026-09-11.*