# Efficient quantum tomography II

arXiv: https://arxiv.org/abs/1612.00034 · HTML: https://mlsanity.com/paper/1612.00034/

## Key facts

- Cited by 54 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Nov 2016.

## Built on by (most cited first, 30 of 54)

- [Exponential separations between learning with and without quantum memory](https://mlsanity.com/paper/2111.05881/) (2021)
- [A survey on the complexity of learning quantum states](https://mlsanity.com/paper/2305.20069/) (2023)
- [A comprehensive review of Quantum Machine Learning: from NISQ to Fault Tolerance](https://mlsanity.com/paper/2401.11351/) (2024)
- [Learning Quantum Processes and Hamiltonians via the Pauli Transfer Matrix](https://mlsanity.com/paper/2212.04471/) (2022)
- [Toward Instance-Optimal State Certification With Incoherent Measurements](https://mlsanity.com/paper/2102.13098/) (2021)
- [Adaptive Online Learning of Quantum States](https://mlsanity.com/paper/2206.00220/) (2022)
- [When Does Adaptivity Help for Quantum State Learning?](https://mlsanity.com/paper/2206.05265/) (2022)
- [Private learning implies quantum stability](https://mlsanity.com/paper/2102.07171/) (2021)
- [On the Hardness of PAC-learning Stabilizer States with Noise](https://mlsanity.com/paper/2102.05174/) (2021)
- [Lower Bounds for Learning Quantum States with Single-Copy Measurements](https://mlsanity.com/paper/2207.14438/) (2022)
- [ShadowNet for Data-Centric Quantum System Learning](https://mlsanity.com/paper/2308.11290/) (2023)
- [Efficient Tomography of Non-Interacting Fermion States](https://mlsanity.com/paper/2102.10458/) (2021)
- [Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates](https://mlsanity.com/paper/2305.13409/) (2023)
- [Quantum State Tomography using Quantum Machine Learning](https://mlsanity.com/paper/2308.10327/) (2023)
- [Certifying almost all quantum states with few single-qubit measurements](https://mlsanity.com/paper/2404.07281/) (2024)
- [Quantum Neural Estimation of Entropies](https://mlsanity.com/paper/2307.01171/) (2023)
- [Learning pure quantum states (almost) without regret](https://mlsanity.com/paper/2406.18370/) (2024)
- [Fast quantum state reconstruction via accelerated non-convex programming](https://mlsanity.com/paper/2104.07006/) (2021)
- [Hardware-efficient learning of quantum many-body states](https://mlsanity.com/paper/2212.06084/) (2022)
- [On the Role of Entanglement and Statistics in Learning](https://mlsanity.com/paper/2306.03161/) (2023)
- [Online learning of a panoply of quantum objects](https://mlsanity.com/paper/2406.04245/) (2024)
- [Stabilizer bootstrapping: A recipe for efficient agnostic tomography and magic estimation](https://mlsanity.com/paper/2408.06967/) (2024)
- [On the sample complexity of purity and inner product estimation](https://mlsanity.com/paper/2410.12712/) (2024)
- [Sample-optimal classical shadows for pure states](https://mlsanity.com/paper/2211.11810/) (2022)
- [Learning Quantum Processes with Quantum Statistical Queries](https://mlsanity.com/paper/2310.02075/) (2023)
- [Learning finitely correlated states: stability of the spectral reconstruction](https://mlsanity.com/paper/2312.07516/) (2023)
- [Unraveling Quantum Environments: Transformer-Assisted Learning in Lindblad Dynamics](https://mlsanity.com/paper/2505.06928/) (2025)
- [Provable learning of quantum states with graphical models](https://mlsanity.com/paper/2309.09235/) (2023)
- [An optimal tradeoff between entanglement and copy complexity for state tomography](https://mlsanity.com/paper/2402.16353/) (2024)
- [Optical Quantum Mixed-State Reconstruction With Multiple Deep Learning Approaches](https://mlsanity.com/paper/2407.01734/) (2024)

## Abstract (arXiv)

Following [OW16], we continue our analysis of: (1) "Quantum tomography", i.e., learning a quantum state, i.e., the quantum generalization of learning a discrete probability distribution; (2) The distribution of Young diagrams output by the RSK algorithm on random words. Regarding (2), we introduce two powerful new tools: (i) A precise upper bound on the expected length of the longest union of k disjoint increasing subsequences in a random length-n word with letter distribution α1 ≥ α2 ≥ cdots ≥ αd; (ii) A new majorization property of the RSK algorithm that allows one to analyze the Young diagram formed by the lower rows λk, λk+1, dots of its output. These tools allow us to prove several new theorems concerning the distribution of random Young diagrams in the nonasymptotic regime, giving concrete error bounds that are optimal, or nearly so, in all parameters. As one example, we give a fundamentally new proof of the fact that the expected length of the longest increasing sequence in a random length-n permutation is bounded by 2√n. This is the k = 1, αi equiv frac1d, d → ∞ special case of a much more general result we prove: the expected length of the kth Young diagram row produced by an α-random word is αk n ± 2√αkd n. From our new analyses of random Young diagrams we derive several new results in quantum tomography, including: (i) Learning the eigenvalues of an unknown state to ε-accuracy in Hellinger-squared, chi-squared, or KL distance, using n = O(d2/ε) copies; (ii) Learning the optimal rank-k approximation of an unknown state to ε-fidelity (Hellinger-squared distance) using n = widetildeO(kd/ε) copies.