Learning and testing quantum states via probabilistic combinatorics and representation theory
Ryan O’Donnell, John Wright
In this survey, we give an introduction to the problem of learning and testing quantum states from multiple copies.Special attention is paid to the tasks of estimating the eigenvalues of an unknown state, testing whether a state is maximally mixed, and performing full quantum state tomography.We focus on the representation theory-based approached, developed in [ARS88, KW01, HM02, Har05, Key06, CM06, Chr06, CHW07, MW16, OW21, OW16, HHJ + 17, OW17, BOW19, CLM + 21, AISW19] and elsewhere.Examining this approach also leads to interesting new developments regarding the probabilistic combinatorics of longest increasing subsequences.Note: Modulo minor revisions, Sections 1 to 12 were written jointly with John Wright (Berkeley), and a somewhat condensed version of these sections appeared under the title A primer on the statistics of longest increasing subsequences and quantum states in the Sept. 2017 edition of SIGACT News.Contents 1. Spanish cryptograms 44 2. Quantum contraptions 46 3. Longest increasing subsequences: Robinson, Schensted, Knuth 48 4. Symmetric properties of probabilities: classical vs. quantum 51 5.The RSK bijection and Schur symmetric polynomials 53 6.Two majorization theorems for the RSK algorithm 56 7. Probabilistic combinatorics of longest increasing subsequences 58 8. Mechanics of quantum mechanics 61 9. Noncommutative probability 65 10.Testing for the uniform distribution/maximally mixed state 67 11.Representation theory gives a nice basis for observables 71 12. Symmetric group characters on small conjugacy classes 75
Current Developments in Mathematics•Jan 1, 2021•2 citations