Current Developments in Mathematics

Volume 2021

Learning and testing quantum states via probabilistic combinatorics and representation theory

Pages: 43 – 94

DOI: https://dx.doi.org/10.4310/CDM.2021.v2021.n1.a2

Authors

Ryan O’Donnell (Department of Computer Science, Carnegie Mellon University, Pittsburgh, Pennsylvania, U.S.A.)

John Wright (University of California, Berkeley, Calif., U.S.A.)

Abstract

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 $\href{https://doi.org/10.1063/1.527958}{\textrm{ARS88}}$, $\href{https://doi.org/10.1103/PhysRevA.64.052311}{\textrm{KW01}}$, $\href{https://doi.org/10.1103/PhysRevA.66.022311}{\textrm{HM02}}$, $\href{https://doi.org/10.48550/arXiv.quant-ph/0512255}{\textrm{Har05}}$, $\href{https://doi.org/10.1142/S0129055X06002565}{\textrm{Key06}}$, $\href{https://www.math.tamu.edu/~jml/christandlmitchison.pdf}{\textrm{CM06}}$, $\href{https://arxiv.org/abs/quant-ph/0604183v1}{\textrm{Chr06}}$, $\href{https://arxiv.org/abs/quant-ph/0609110}{\textrm{CHW07}}$, $\href{https://arxiv.org/abs/1310.2035}{\textrm{MW16}}$, $\href{https://doi.org/10.1145/2746539.2746582}{\textrm{OW21}}$, $\href{https://doi.org/10.1145/2897518.2897544}{\textrm{OW16}}$, $\href{https://doi.org/10.1145/2897518.2897585}{\textrm{HHJ+17}}$, $\href{https://doi.org/10.1145/3055399.3055454}{\textrm{OW17}}$, $\href{https://doi.org/10.1145/3313276.3316344}{\textrm{BOW19}}$, $\href{https://felixleditzky.info/files/pbt_banff.pdf}{\textrm{CLM+21}}$, $\href{https://doi.org/10.1109/ISIT.2019.8849572}{\textrm{AISW19}}$ and elsewhere. Examining this approach also leads to interesting new developments regarding the probabilistic combinatorics of longest increasing subsequences.

Full Text (PDF format)

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.

Published 2 August 2023