Efficient quantum tomography II

We continue our analysis of: (i) "Quantum tomography", i.e., learning a quantum state, i.e., the quantum generalization of learning a discrete probability distribution; (ii) The distribution of Young diagrams output by the RSK algorithm on random words. Regarding (ii), we introduce two powerful new tools: first, 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 ≥ … ≥ α d . Our bound has the correct main term and second-order term, and holds for all n , not just in the large- n limit. Second, a new majorization property of the RSK algorithm that allows one to analyze the Young diagram formed by the lower rows λ k , λ k +1 , … 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 celebrated 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 ≡ 1/ d , d → ∞ special case of a much more general result we prove: the expected length of the k th Young diagram row produced by an α-random word is α k n ± 2√α k d 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 ( d 2 /ε) copies; (ii) learning the top- k eigenvalues of an unknown state to ε-accuracy in Hellinger-squared or chi-squared distance using n = O ( kd /ε) copies or in ℓ 2 2 distance using n = O ( k /ε) copies; (iii) learning the optimal rank- k approximation of an unknown state to ε-fidelity (Hellinger-squared distance) using n = O ( kd /ε) copies. We believe our new techniques will lead to further advances in quantum learning; indeed, they have already subsequently been used for efficient von Neumann entropy estimation.

Authors

• Ryan O'Donnell
• John Wright 0004

Keywords

• Quantum tomography
• Robinson-Schensted-Knuth algorithm
• Schur-Weyl duality
• longest increasing subsequences
• quantum spectrum estimation