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
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
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 kth Young diagram row produced by an α-random word is αk n ± 2√αkd n.
In this work, we study the problem of testing properties of the spectrum of a mixed quantum state. Here one is given n copies of a mixed state ρ∈Cd×d and the goal is to distinguish whether ρ's spectrum satisfies some property P or is at least ε-far in ℓ1-distance from satisfying P. This problem was promoted in the survey of Montanaro and de Wolf under the name of testing unitarily invariant properties of mixed states. It is the natural quantum analogue of the classical problem of testing symmetric properties of probability distributions. Here, the hope is for algorithms with subquadratic copy complexity in the dimension d. This is because the "empirical Young diagram (EYD) algorithm" can estimate the spectrum of a mixed state up to ε-accuracy using only O(d2/ε2) copies. In this work, we show that given a mixed state ρ∈Cd×d: (i) Θ(d/ε2) copies are necessary and sufficient to test whether ρ is the maximally mixed state, i.e., has spectrum (d1,...,d1); (ii) Θ(r2/ε) copies are necessary and sufficient to test with one-sided error whether ρ has rank r, i.e., has at most r nonzero eigenvalues; (iii) Θ(r2/Δ) copies are necessary and sufficient to distinguish whether ρ is maximally mixed on an r-dimensional or an (r+Δ)-dimensional subspace; and (iv) The EYD algorithm requires Ω(d2/ε2) copies to estimate the spectrum of ρ up to ε-accuracy, nearly matching the known upper bound. In addition, we simplify part of the proof of the upper bound. Our techniques involve the asymptotic representation theory of the symmetric group; in particular Kerov's algebra of polynomial functions on Young diagrams.
Pattern recognition is a central topic in learning theory, with numerous applications such as voice and text recognition, image analysis and computer diagnosis. The statistical setup in classification is the following: we are given an i.i.d. training set ( X 1 , Y 1 ), ... , ( X n , Y n ), where X i represents a feature and Y i ∊{0, 1} is a label attached to that feature. The underlying joint distribution of ( X , Y ) is unknown, but we can learn about it from the training set, and we aim at devising low error classifiers f: X → Y used to predict the label of new incoming features. In this paper, we solve a quantum analogue of this problem, namely the classification of two arbitrary unknown mixed qubit states. Given a number of 'training' copies from each of the states, we would like to 'learn' about them by performing a measurement on the training set. The outcome is then used to design measurements for the classification of future systems with unknown labels. We found the asymptotically optimal classification strategy and show that typically it performs strictly better than a plug-in strategy, which consists of estimating the states separately and then discriminating between them using the Helstrom measurement. The figure of merit is given by the excess risk equal to the difference between the probability of error and the probability of error of the optimal measurement for known states. We show that the excess risk scales as n −1 and compute the exact constant of the rate.
Gaussian states are widely regarded as one of the most relevant classes of continuous-variable (CV) quantum states, as they naturally arise in physical systems and play a key role in quantum technologies. This motivates a fundamental question: given copies of an unknown CV state, how can we efficiently test whether it is Gaussian? We address this problem from the perspective of representation theory and quantum learning theory, characterizing the sample complexity of Gaussianity testing as a function of the number of modes. For pure states, we prove that just a constant number of copies is sufficient to decide whether the state is exactly Gaussian. We then extend this to the tolerant setting, showing that a polynomial number of copies suffices to distinguish states that are close to Gaussian from those that are far. In contrast, we establish that testing Gaussianity of general mixed states necessarily requires exponentially many copies, thereby identifying a fundamental limitation in testing CV systems. Our approach relies on rotation-invariant symmetries of Gaussian states together with the recently introduced toolbox of CV trace-distance bounds.
We describe a procedure that simultaneously reduces the dimensions of many, potentially distinct quantum states while preserving properties invariant under the tensor power action of an isometry. This serves as a black-box method to replace the dimension with the maximum rank in the sample complexity of learning symmetric properties, even those depending on multiple input states. Combined with full state tomography, random dimension reduction yields improved upper bounds for estimating distances, fidelities, and relative entropies between pairs of states.
Expressing the action of this procedure through the Choi--Jamiołkowski isomorphism reveals an intimate connection with the recently introduced random purification channel by Tang, Wright, and Zhandry. With this new perspective, we obtain a simple description of the rank-dependent version of the random purification channel and give an end-to-end analysis of sample-optimal tomography without requiring a reference to the Schur transform or Schur polynomials. Finally, we prove that there does not exist a random purification channel that simultaneously purifies copies of multiple, potentially different input states. Hence, the procedure is related to, but distinct from, random purification.
The main topic of this compilation thesis is the investigation of multipartite entanglement of finite dimensional systems. We developed a numerical algorithm that detects if a multipartite state is entangled or separable in a finite number of steps of a semi-definite optimization task. This method is an extension of previously known semi-definite methods, which are inconclusive when the state is separable. In our case, if the state is separable, an explicit decomposition into a mixture of separable states can be extracted. This was achieved by mapping the entanglement problem onto the mathematically well studied truncated moment problem. Additionally, a new way of writing the partially transposed state for symmetric multi-qubit states was developed which simplifies many results previously known in entanglement theory. This new way of writing the partial transpose criterion unifies different interpretations and alternative formulations of the partial transpose criterion and it is also a part in the aforementioned semi-definite algorithm. The geometric properties of entangled symmetric states of two qubits were studied in detail: We could answer the question of how far a given pure state is from the convex hull of symmetric separable states, as measured by the Hilbert-Schmidt distance, by giving an explicit formula for the closest separable symmetric state. For mixed states we could provide a numerical upper and analytical lower bound for this distance. For a larger number of qubits we investigated the ball of absolutely classical states, i.e. symmetric multi-qubit states that stay separable under any unitary transformation. We found an analytical lower bound for the radius of this ball around the maximally mixed symmetric state and gave a numerical upper bound on this radius, by searching for an entangled state as close as possible to the maximally mixed symmetric state. The tensor representation of a symmetric multi-qubit state, or spin-j state, allowed us to study entanglement properties based on the spectrum of the tensor via tensor eigenvalues. The definiteness of this tensor relates to the entanglement of the state it represents and, hence, the smallest tensor eigenvalue can be used to detect entanglement. However, the tensor eigenvalues are more difficult to determine than the familiar matrix eigenvalues which made the investigation computationally more challenging. The relationship between the value of the smallest tensor eigenvalue and the amount of entanglement in the state was also investigated. It turned out that they are strongly correlated for small system sizes, i.e. for up to six qubits. However, to investigate this correlation we needed an independent way to gauge the amount of entanglement of a state and in order to do so we improved existing numerical methods to determine the distance of a state to the set of separable symmetric states, using a combination of linear and quadratic programming. The tensor representation of symmetric multi-qubit states was also used to formally define a new tensor class of regularly decomposable tensors that corresponds to the set of separable symmetric multi-qubit states.