PHYSICAL REVIEW X 9, 041029 (2019) Unsupervised Classification of Quantum Data Gael Sentís,1 Alex Monràs,2 Ramon Muñoz-Tapia,2 John Calsamiglia,2 and Emilio Bagan2,3 1 Naturwissenschaftlich-Technische Fakultät, Universität Siegen, 57068 Siegen, Germany 2 Física Teòrica: Informació i Fenòmens Quàntics, Departament de Física, Universitat Autònoma de Barcelona, 08193 Bellaterra (Barcelona), Spain 3 Department of Computer Science, The University of Hong Kong, Pokfulam Road, Hong Kong (Received 19 March 2019; revised manuscript received 4 July 2019; published 8 November 2019) We introduce the problem of unsupervised classification of quantum data, namely, of systems whose quantum states are unknown. We derive the optimal single-shot protocol for the binary case, where the states in a disordered input array are of two types. Our protocol is universal and able to automatically sort the input under minimal assumptions, yet partially preserves information contained in the states. We quantify analytically its performance for an arbitrary size and dimension of the data. We contrast it with the performance of its classical counterpart, which clusters data that have been sampled from two unknown probability distributions. We find that the quantum protocol fully exploits the dimensionality of the quantum data to achieve a much higher performance, provided the data are at least three dimensional. For the sake of comparison, we discuss the optimal protocol when the classical and quantum states are known. DOI: 10.1103/PhysRevX.9.041029 Subject Areas: Quantum Information, Statistical Physics I. INTRODUCTION [13], and classifying quantum states [14–17]. These works fall under the broad category of supervised learning Quantum-based communication and computation tech- nologies promise unprecedented applications and unfore- [18,19], where the aim is to learn an unknown conditional seen speed-ups for certain classes of computational probability distribution PrðyjxÞ from a number of given problems. In origin, the advantages of quantum computing samples xi and associated values or labels yi , called are exemplary showcased through instances of problems training instances. The performance of a trained learning that are hard to solve in a classical computer, such as integer algorithm is then evaluated by applying the learned factorization [1], unstructured search [2], discrete optimi- function over new data x0i called test instances. In the zation [3,4], and simulation of many-body Hamiltonian quantum extension of supervised learning [20], the training dynamics [5]. In recent times, the field ventures one step instances are quantum—say, copies of the quantum state further: Quantum computers are now also envisioned as templates, or a potential anomalous state, or a number of nodes in a network of quantum devices, where connections uses of an unknown unitary transformation. The separation are established via quantum channels, and data are quantum between training and testing steps is sometimes not as systems that flow through the network [6,7]. The design sharp: In reinforcement learning, training occurs on an of future quantum networks, in turn, brings up new theo- instance basis via the interaction of an agent with an retical challenges, such as devising universal information- environment, and the learning process itself may alter the processing protocols optimized to work with generic underlying probability distribution [21]. quantum inputs, without the need of human intervention. In contrast, unsupervised learning aims at inferring Quantum learning algorithms are by design well suited structure in an unknown distribution PrðxÞ given random, for this class of automated tasks [8]. Generalizing classical unlabeled samples xi . Typically, this inference is done by machine-learning ideas to operate with quantum data, some grouping the samples in clusters, according to a preset algorithms have been devised for quantum template match- definition of similarity. Unsupervised learning is a versatile ing [9], quantum anomaly detection [10,11], learning form of learning, attractive in scenarios where appropri- unitary transformations [12] and quantum measurements ately labeled training data are not available or too costly. But it is also—generically—a much more challenging problem [22,23]. To our knowledge, a quantum extension of unsupervised learning in the sense described above is not Published by the American Physical Society under the terms of yet considered in the literature. In this paper, we take a first the Creative Commons Attribution 4.0 International license. Further distribution of this work must maintain attribution to step into this branch of quantum learning by introducing the author(s) and the published article’s title, journal citation, the problem of unsupervised binary classification of quan- and DOI. tum states. We consider the following scenario: A source 2160-3308=19=9(4)=041029(22) 041029-1 Published by the American Physical Society GAEL SENTÍS et al. PHYS. REV. X 9, 041029 (2019) versatility of the clustering device, in a similar spirit to programable quantum processors [24]. Feature (ii) allows us to assess the performance of the device purely in terms of the accuracy of the clustering, which, in turn, facilitates the comparison with classical clustering strategies. Also due to (ii), we can justifiably say that the device has not only performed the clustering task but also “learned” that the input is (most likely) partitioned as specified by the output description. Note that relaxing feature (ii), in principle, opens the door to a more general class of sorting quantum devices, where the goal could be, e.g., to minimize the distance (under some norm) between the global output state and the state corresponding to perfect clustering of the FIG. 1. Pictorial representation of the clustering device for an input. Such devices, however, fall beyond the scope of input of eight quantum states. States of the same type have the unsupervised learning. same color. States are clustered according to their type by Requiring the description of the clusters as a classical performing a suitable collective measurement, which also pro- outcome induces structure in the device. To generate this vides a classical description of the clustering. information, a quantum measurement shall be performed over all N systems with as many outcomes as possible clusterings. Then, the systems will be sorted according to prepares quantum systems in two possible pure states this outcome (see Fig. 1). Depending on the context, e.g., that are completely unknown; after some time, N such on whether or not the systems will be further used after the systems are produced, and we ask ourselves whether there exists a quantum device that is able to cluster them in two clustering, different figures of merit shall be considered in groups according to their states (see Fig. 1). This scenario the optimization of the device. In this paper, we focus on represents a quantum clustering task in its simplest form, the clustering part: Our goal is to find the quantum where the single feature defining a cluster of quantum measurement that maximizes the success probability of a systems is that their states are identical. While clustering correct clustering. classical data under this definition of a cluster—a set of Features (i) and (ii) allow us to formally regard quantum equal data instances—yields a trivial algorithm, merely clustering as a state discrimination task [25–30], albeit observing such a simple feature in a finite quantum dataset with important differences with respect to the standard involves a nontrivial stochastic process and gives rise to a setting. In quantum state discrimination [25], we want to primitive of operational relevance for quantum information. determine the state of a quantum system among a set of Moreover, in some sense, our scenario actually contains a known hypotheses (i.e., classical descriptions of quantum classical binary clustering problem: If we were to measure states). We can phrase this problem in machine-learning each quantum system separately, we would obtain a set of terminology as follows. We have a test state (or several N data points (the measurement outcomes). The points copies of it [29]), and we decide its label based on infinite would be effectively sampled from the two probability training data. In other words, we have full knowledge distributions determined by the quantum states and the about the meaning of the possible labels. Supervised choice of measurement. The task would then be to identify quantum learning algorithms for quantum state classifica- which points are sampled from the same distribution. tion [14–17] consider the intermediate scenario with limited Reciprocally, we can interpret our quantum clustering task training data. In this case, no description of the states is as a natural extension of a classical clustering problem available. Instead, we are provided with a finite number of with completely unstructured data, where the only single copies of systems in each of the possible quantum states, feature that identifies a cluster is that the data points and thus we have only partial classical knowledge about the are sampled from a fixed, but arbitrary, categorical prob- labels. Extracting the label information from the quantum ability distribution (i.e., with no order nor metric in the training data then becomes a key step in the protocol. underlying space). The quantum generalization is then to Following this line of thought, the problem we consider in consider (noncommuting) quantum states instead of prob- this paper is a type of unsupervised learning, that is, one ability distributions. with no training. There is no information whatsoever about We require two important features in our quantum what state each label represents. clustering device: (i) It has to be universal—that is, it We obtain analytical expressions for the performance of should be designed to take any possible pair of types the optimal clustering protocol for arbitrary values of the of input states—and (ii) it has to provide a classical local dimension d of the systems in the cases of a finite description of the clustering, that is, which particles belong number of systems N and in the asymptotic limit of many to each cluster. Feature (i) ensures general-purpose use and systems. We show that, in spite of the fact that the number 041029-2 UNSUPERVISED CLASSIFICATION OF QUANTUM DATA PHYS. REV. X 9, 041029 (2019) of possible clusterings grows exponentially with N, the success probability decays only as Oð1=N 2 Þ. Furthermore, we contrast these results with an optimal clustering algorithm designed for the classical version of the task. We observe a striking phenomenon when analyzing the performance of the two protocols for d > 2: Whereas increasing the local dimension has a rapid negative impact in the success probability of the classical protocol (cluster- ing becomes, naturally, harder), it turns out to be beneficial for its quantum counterpart. We also see, through a numerical analysis, that the FIG. 2. All possible clusterings of N ¼ 4 systems when each quantum measurement that maximizes the success proba- can be in one of two possible states, depicted as blue and red. The bility is also optimal for a more general class of cost pair of indices ðn; σÞ identifies each clustering, where n is the size functions that are more natural for clustering problems, of the smallest cluster and σ is a permutation of the reference clusterings (those on top of each box), wherein the smallest including the Hamming distance. In other words, this cluster falls on the right. The symbol e denotes the identity observation provides evidence that our entire analysis does permutation, and ðijÞ the transposition of systems in positions i not depend strongly on the chosen figure of merit but rather and j. Note that the choice of σ is not unique. on the structure of the problem itself. Measuring the systems will, in principle, degrade the information encoded in their states; hence, intuitively, there red and blue balls. Since the individual states of the should be a trade-off between how good a clustering is and systems are unknown, what is labeled as “red” or “blue” how much information about the original states is left in the is arbitrary; thus, interchanging the labels leads to an clusters. Remarkably, our analysis reveals that the meas- equivalent clustering. For arbitrary N, there are 2N−1 such urement that clusterizes optimally actually preserves infor- clusterings. Figure 2 also illustrates a natural way to label mation regarding the type of states that form each cluster. each clustering as ðn; σÞ. The index n counts the number This feature adds to the usability of our device as a of systems in the smallest cluster. The index σ is a universal quantum data sorting processor. It can be permutation that brings a reference clustering, defined as regarded as the quantum analog of a sorting network (or that in which the systems belonging to the smallest cluster sorting memory) [31], used as a fixed network architecture fall all on the right, into the desired form. To make this that automatically orders generic inputs coming from an labeling unambiguous, σ is chosen from a restricted set aggregated data pipeline. The details of this second step S n ⊂ SN , where SN stands for the permutation group of N are, however, left for a subsequent publication. elements and e denotes its unity element. We see that the The paper is organized as follows. In Sec. II, we optimal clustering procedure consists in measuring first the formalize the problem and derive the optimal clustering value of n and, depending on the outcome, performing a protocol and its performance. In Sec. III, we consider a second measurement that identifies σ among the relevant classical clustering protocol and contrast it with the optimal permutations with a fixed n. one. We present the proofs of the main results of our work Thus, unsupervised clustering is cast as a multihypo- and the necessary theoretical tools to derive them in Sec. IV. thesis discrimination problem, which can be solved for an We end in Sec. V discussing the features of our quantum arbitrary number of systems N with local dimension d. clustering device and other cost functions and giving an Below, we outline the derivation of our main result: the outlook on future extensions. expression of the maximum average success probability achievable by a quantum clustering protocol. In the limit of II. CLUSTERING QUANTUM STATES large N and for arbitrary d (not necessarily constant with N), we show that this probability behaves as Let us suppose that a source prepares quantum systems randomly in one of two pure d-dimensional states jϕ0 i and jϕ1 i with equal prior probabilities. Given a sequence of N 8ðd − 1Þ Ps ∼ : ð1Þ systems produced by the source, and with no knowledge of ð2d þ NÞN the states jϕ0=1 i, we are required to assign labels “0” or “1” to each of the systems. The labeling can be achieved via a (The symbol ∼ stands for “asymptotically equivalent to”, as generalized quantum measurement that tries to distinguish in Ref. [32].). Naturally, Ps goes to zero with N, since the among all the possible global states of the N systems. Each total number of clusterings increases exponentially and it outcome of the measurement is then associated to a becomes much harder to discriminate among them. What possible label assignment, that is, to a clustering. may perhaps come as a surprise is that, despite this Consider the case of four systems. All possible cluster- exponential growth, the scaling of Ps is only of the order ings that we may arrange are depicted in Fig. 2 as strings of of Oð1=N 2 Þ. (It is also interesting to see how far one can 041029-3 GAEL SENTÍS et al. PHYS. REV. X 9, 041029 (2019) improve this result. By letting d scale with N, e.g., by shape of Young diagrams (or partitions of N). A pair of substituting d ∼ sN γ for some s > 0, γ > 1 in Eq. (1), we parentheses () [braces fg], surrounding the subscript λ, e.g., obtain the absolute maximum Ps ∼ 4=N.) Furthermore, in Eq. (3), are used when λ refers exclusively to irreps of increasing the local dimension yields a linear improvement SUðdÞ [SN ]; we stick to this convention throughout the in the asymptotic success probability. As we later see, paper. Note that averaging over all SUðdÞ transformations whereas the asymptotic behavior in N is not an exclusive erases the information contained in the representation feature of the optimal quantum protocol—we observe the subspace (λ). It also follows from Eq. (3) and the rules same scaling in its classical counterpart, albeit only when of the Clebsch-Gordan decomposition that (i) only two-row d ¼ 2—the ability to exploit extra dimensions to enhance Young diagrams (partitions of length two) show up in the distinguishability is. direct sum above, and (ii) the operators Ωn;σ fλg are rank-1 Let us present an outlined derivation of the optimal projectors (see Appendix B). They carry all the information quantum clustering protocol. Each input can be described relevant for the clustering and are understood to be zero for by a string of 0’s and 1’s x ¼ ðx1 …xN Þ, so that the global irreps λ outside the support of ρn;σ . state of the systems entering the device is jΦx i ¼ jϕx1 i ⊗ With Eq. (3) at hand, the optimal clustering protocol can jϕx2 i ⊗    ⊗ jϕxN i. The clustering device can generically be succinctly described as two successive measurements— be defined by a positive operator valued measure P (POVM) we state the result here and present an optimality proof in with elements fEx g, fulfilling Ex ≥ 0 and x Ex ¼ 1, Sec. IVA. The first measurement is a projection onto the where each operator Ex is associated to the statement irrep subspaces λ, described by the set f1ðλÞ ⊗ 1fλg g. The “the measured global state corresponds to the string x.” outcome of this measurement provides an estimate of n, as λ We want to find a POVM Rthat maximizes P the average is one to one related to the size of the clusters. More success probability Ps ¼21−N dϕ0 dϕ1 x trðjΦx ihΦx jEx Þ, precisely, we have from (i) that λ ¼ ðλ1 ; λ2 Þ, where λ1 and λ2 where we assume that each clustering is equally likely at the are non-negative integers such that λ1 þ λ2 ¼ N and input and we are averaging over all possible pairs of states λ1 ≥ λ2 . Then, given the outcome λ ¼ ðλ1 ; λ2 Þ of this first fjϕ0 i; jϕ1 ig and strings x. Since our goal is to design a measurement, the optimal guess turns out to be n ¼ λ2 . Very universal clustering protocol, the operators Ex cannot roughly speaking, the “asymmetry” in the subspace λ ¼ depend on jϕ0;1 i, and we can take the integral inside the ðλ1 ; λ2 Þ increases with λ2 . We recall that λ ¼ ðN; 0Þ is the trace. The clustering problem can then be regarded as the fully symmetric subspace of ðd; CÞN . Naturally, ρ0;σ has optimization of a POVM that distinguishes between effec- support only in this subspace, as all states in the data are of tive density operators of the form one type. As λ2 increases from zero, more states of the Z alternative type are necessary to achieve the increasing ρx ¼ dϕ0 dϕ1 jΦx ihΦx j: ð2Þ asymmetry of λ ¼ ðλ1 ; λ2 Þ. Hence, for a given λ2 , there is a minimum value of n for which ρn;σ can have support in the It now becomes apparent that ρx ¼ ρx̄ , where x̄ is the subspace λ ¼ ðλ1 ; λ2 Þ. This minimum n is the optimal guess. complementary string of x (i.e., the values 0 and 1 are Once we obtain a particular λ ¼ λ as an outcome (and exchanged). guess n), a second measurement is performed over the The key that reveals the structure of the problem subspace fλ g to produce a guess for σ. Since the states ρn;σ and allows us to deduce the optimal clustering protocol are covariant under SN , the optimal measurement to guess resides in computing the integral in Eq. (2). Averaging over the permutation σ is also covariant, and its seed is the  the states leaves out only the information relevant to rank-1 operator Ωn;e fλ g, where λ ¼ ðN − n; nÞ. Put together, identify a clustering, that is, n and σ. Certainly, identifying these two successive measurements yield a joint optimal x ≡ ðn; σÞ, we can rewrite ρx as POVM whose elements take the form † ρn;σ ¼ cn U σ ð1sym n ⊗ 1sym N−n ÞU σ En;σ ¼ ξnλ ð1ðλ Þ ⊗ Ωn;σ fλ g Þ; ð4Þ ¼ cn ⨁1ðλÞ ⊗ Ωn;σ fλg : ð3Þ λ where ðn; σÞ is the guess for the cluster and ξnλ is By applying the Schur lemma, one readily obtains the some P coefficient that guarantees the POVM condition first line, where 1sym k is a projector onto the completely n;σ n;σ ¼ 1. E symmetric subspace of k systems, cn is a normalization The success probabilityPof the optimal protocol can factor, and U σ is a unitary matrix representation of σ. be computed as Ps ¼ 21−N n;σ trðρn;σ En;σ Þ (see Sec. IVA). The second line follows from using the Schur basis (see It reads Sec. IVA), in which the states ρn;σ are block diagonal. Here, λ labels the irreducible representations—irreps for X bN=2c N  ðd − 1ÞðN − 1 − 2iÞ2 short—of the joint action of the groups SUðdÞ and SN over Ps ¼ 21−N ; ð5Þ i ðN − 1 þ d − iÞði þ 1Þ2 the vector space ðd; CÞ⊗N and is usually identified with the i¼0 041029-4 UNSUPERVISED CLASSIFICATION OF QUANTUM DATA PHYS. REV. X 9, 041029 (2019) from which the asymptotic limit Eq. (1) follows (see same projective measurement on each individual quantum Appendix C). state jϕxi i of our original problem. Furthermore, such local Before closing this section, we briefly discuss the case measurements can also be interpreted as a decoherence when some information about the possible states jϕ0 i and process affecting the pure quantum states at the input, jϕ1 i is available. A clustering device that incorporates whereby they decay into classical probability distributions this information into its design should succeed with a over a fixed basis. We might think of this as the semi- probability higher than Eq. (5), at the cost of universality. classical analog of our original problem, since quantum To explore the extent of this performance enhancement, we resources are not fully exploited. study the extreme case where we have full knowledge of the Let us first lay out the problem in the special case of states jϕ0 i and jϕ1 i. We find that in the large N limit the d ¼ 2, where the underlying distributions are Bernoulli, maximum improvement is by a factor of N. The optimal and we can write P ¼ fp; 1 − pg, Q ¼ fq; 1 − qg. Given success probability scales as an N-length string of samples s, our intuition tells us that the best we can do is to assign the same underlying 4ðd − 1Þ probability distribution to equal values in s. So if, e.g., Ps ∼ ð6Þ N s ¼ ð00101…Þ, we guess that the underlying sequence of distributions is x̂ ¼ ðPPQPQ…Þ [or, equivalently, the (see Sec. IV B for details). complementary sequence x̂ ¼ ðQQPQP…Þ]. Thus, data points are clustered according to their value 0 or 1. The III. CLUSTERING CLASSICAL STATES optimality of this guessing rule is a particular case of the To grasp the significance of our quantum clustering result for d-dimensional random variables in Appendix F. protocol, a comparison with a classical analog is called The probability that a string of samples s, with l zeros for. First, in the place of a quantum system whose state is and N − l ones, arises from the guessed sequence x̂ is either jϕ0 i or jϕ1 i, an input would be an instance of a given by d-dimensional random variable sampled from either one Z 1 Z 1 1 of two categorical probability distributions: P ¼ fps gds¼1 Prðsjx ¼ x̂Þ ¼ dp dqpl qN−l ¼ : 0 0 ðl þ 1ÞðN − l þ 1Þ and Q ¼ fqs gds¼1 . Then, given a string of samples s ¼ ðs1 …sN Þ, si ∈ f1; …; dg, the clustering task would consist ð7Þ in grouping the data points si in two clusters so that all points in a cluster have a common underlying probability The average success P probability can then be readily distribution. computed as Pcls ¼ 2 x;s δx;x̂ PrðxÞ PrðsjxÞ (recall that Second, in analogy with the quantum protocol, our goal x̂ depends on s), where PrðxÞ ¼ 2−N is the prior probability would be to find the optimal universal (i.e., independent of of the sequence x, which we assume to be uniform. The P and Q) protocol that performs this task. Here, optimality factor 2 takes into account that guessing the complementary means attaining the maximum average success probability, sequence leads to the same clustering. It is now quite where the average is over all N-length sequences x of straightforward to derive the asymptotic expression of Pcls distributions P and Q from which the string s is sampled for large N. In this limit, x typically has the same number and over all such distributions. of P and Q distributions, so the guess x̂ is right if It should be emphasized that this is a very hard classical l ¼ N=2. Then, clustering problem, with absolute minimal assumptions, where there is no metric in the domain of the random 1 8 Pcls ∼ 2 2 ∼ 2: ð8Þ variables and, in consequence, no exploitable notion of ðN=2 þ 1Þ N distance. Therefore, one should expect the optimal algo- rithm to have a rather low performance and to differ This expression coincides with the quantum asymptotic significantly from well-known algorithms for classical result in Eq. (1) for d ¼ 2. As we now see, this coincidence unsupervised classification problems. is, however, a particularity of Bernoulli distributions. As a further remark, we note that a choice of prior is The derivation for d > 2 is more involved, since the required to perform the average over P and Q. We assume optimal guessing rule is not so obvious (see Appendix F for that the two are uniformly distributed over the simplex on details). Loosely speaking, we should still assign samples which they are both defined. This assumption reflects our with the same value to the same cluster. By doing so, we lack of knowledge about the distributions underlying the obtain up to d preliminary clusters. We next merge them string of samples s. into two clusters in such a way that their final sizes are as Under all these specifications, the classical clustering balanced as possible. This last step, known as the partition problem we just defined naturally connects with the problem [33], is weakly NP complete. Namely, its com- quantum scenario in Sec. II as follows. We can interpret plexity is polynomial in the magnitudes of the data involved s as a string of outcomes obtained upon performing the (the size of the preliminary clusters, which depends on N) 041029-5 GAEL SENTÍS et al. PHYS. REV. X 9, 041029 (2019) but nonpolynomial in the input size (the number of such the optimal POVM and compute the minimum cost. Basic clusters, determined by d). The complexity of this last step notions of the representation theory that we use in the proof implies that the classical and semiclassical protocols cannot are covered in Appendixes A and B. We close the methods be implemented efficiently for arbitrary d. In the asymptotic section proving Eq. (6) for the optimal success probability limit of large N and for arbitrary fixed values of d, we of clustering known quantum states. obtain  d A. Clustering quantum states: Unknown input states 2 ð2d − 2Þ! Ps ∼ cl : ð9Þ In this section, we obtain the optimal POVM for N ðd − 2Þ! quantum clustering and compute the minimum cost. First, we present a formal optimality proof for an arbitrary There is a huge difference between this result and Eq. (1). cost function fðx; x0 Þ, which specifies the penalty for Whereas increasing the local dimension provides an guessing x if the input is x0 . Second, we particularize to asymptotic linear advantage in the optimal quantum clus- the case of success probability, as discussed in the main tering protocol—states become more orthogonal—it has text, for which explicit expressions are obtained. the opposite effect in its classical and semiclassical analogs, as it reduces exponentially the success probability. 1. Generic cost functions In the opposite regime, i.e., for d asymptotically large and fixed values of N, the optimal classical and semi- We say a POVM is optimal if it minimizes the average classical strategies provide no improvement over random cost guessing, and the clustering tasks become exceedingly Z X hard and somewhat uninteresting. This fact follows from f̄ ¼ dϕ0 dϕ1 ηx fðx; x̂Þ Prðx̂jxÞ; ð10Þ observing that the guessing rule relies on grouping repeated x;x̂ data values. In this regime, the typical string of samples s has no repeated elements; thus, we are left with no where ηx is the prior probability of input string x and alternative but to randomly guess the right clustering of Prðx̂jxÞ ¼ trðjΦx ihΦx jEx̂ Þ is the probability of obtaining the data and Pcls ∼ 21−N . measurement outcome (and guess) x̂ given input x; recall To complete the picture, we end this section by consid- that jΦx i ¼ jϕx1 i ⊗ jϕx2 i ⊗ … ⊗ jϕxN i, xk ¼ 0, 1, and an ering known classical probability distributions. Akin to the average is taken over all possible pairs of states fjϕ0 i; jϕ1 ig; quantum case, one expects an increase in the success hence, x and its complementary x̄ define the same cluster- probability of clustering. An immediate consequence of ing. A convenient way to identify the different clusterings is knowing the distributions P and Q is that the rule for by counting the number n, 0 ≤ n ≤ bN=2c, of zeros in x (so, assigning a clustering given a string of samples s becomes strings with more 0’s than 1’s are discarded) and giving a trivial. Each symbol si ∈ f1; …; dg is assigned to the most unique representative σ of the equivalence class of permu- likely distribution, that is, to P (Q) if psi > qsi (psi < qsi ). tations that turn the reference string ð0n 1n̄ Þ, n̄ ¼ N − n, into It is clear that knowing P and Q helps to better classify the x. We denote the subset of these representatives by S n ⊂ SN data, which becomes apparent by considering the example and the number of elements in each equivalence class by bn. of two three-dimensional distributions and the data string A simple calculation gives us bn ¼ 2ðn!Þ2 if n ¼ n̄, and s ¼ ð112Þ. If the distributions are unknown, such a bn ¼ n!n̄! otherwise. sequence leads to the guess x̂ ¼ ðPPQÞ [or, equivalently, As discussed in the main text, the clustering problem to x̂ ¼ ðQQPÞ]. In contrast, if P and Q are known and, e.g., above is equivalent to a multihypothesis discrimination p1 > q1 and p2 > q2 , the same sequence leads to the better problem, where the hypotheses are given by guess x̂ ¼ ðPPPÞ. The advantage of knowing the distri- Z bution, however, vanishes in the large N limit, and the ρx ¼ dϕ0 dϕ1 jΦx ihjΦx j asymptotic performance of the optimal clustering algorithm is shown to be given by Eq. (9). The interested reader can † ¼ cn Uσ ð1sym n ⊗ 1sym n̄ ÞU σ ; ð11Þ find the details of the proof in Appendix G. and we have used the Schur lemma to compute the integral. IV. METHODS Here, U σ is a unitary matrix representation of the permu- Here, we give the full proof of optimality of our quantum tation σ, 1sym k is a projector onto the completely symmetric clustering protocol and device, which leads to our main subspace of k systems, and cn ¼ 1=ðDsym sym n Dn̄ Þ, where sym result in Eq. (1). The proof relies on the representation Dk ¼ sðk;0Þ [see Eq. (B6)] is the dimension of symmetric theory of the special unitary and the symmetric groups. In subspace of k qudits. particular, the Schur-Weyl duality is used to efficiently The states (11) are block diagonal in the Schur basis, represent the structure of the input quantum data and the which decouples the commuting actions of the groups action of the device. We then leverage this structure to find SUðdÞ and SN over product states of the form of jΦx i. More 041029-6 UNSUPERVISED CLASSIFICATION OF QUANTUM DATA PHYS. REV. X 9, 041029 (2019) precisely, Schur-Weyl duality states that the representations So far, we have analyzed the structure that the sym- of the two groups acting on the common space ðd; CÞ⊗N are metries of the problem impose on the states ρn;σ and the each other’s commutant. Moreover, it provides a decom- measurements. We have learned that, for any choice of position of this space into decoupled subspaces associated operators Ξnfλg that fulfill Eq. (15), the set of operators (13) to irreps of both SUðdÞ and SN . We can then express the defines a valid POVM, but it need not be optimal. So, we states ρx , where x is specified as ðn; σÞ [x ¼ ðn; σÞ for now proceed to derive optimality conditions for Ξnfλg. Those short], in the Schur basis as are provided by the Holevo-Yuen-Kennedy-Lax [35,36] necessary and sufficient conditions for minimizing the ρn;σ ¼ cn ⨁1ðλÞ ⊗ Ωn;σ fλg : ð12Þ λ average cost. For our clustering problem in Eq. (10), they read In this direct sum, λ is a label attached to the irreps of the joint action of SUðdÞ and SN and is usually identified ðW x − ΓÞEx ¼ Ex ðW x − ΓÞ ¼ 0; ð16Þ with a partition of N or, equivalently, a Young diagram. As explained in the main text, a pair of parentheses W x − Γ ≥ 0: ð17Þ surrounding this type of label, like in (λ), means that it P refers specifically to irreps of SUðdÞ. Likewise, a pair of They must hold for Pall x, where Γ ¼ x W x Ex ¼ P braces, e.g., fλg, indicates that the label refers to irreps x Ex W x , and W x ¼ 0 x0 fðx; x Þηx0 ρx0 . We assume that of SN . In accordance with this convention, Schur-Weyl the prior distribution ηx is flat and that the cost function duality implies that Ωn;σ λ n;e λ † λ fλg ¼ U σ Ωfλg ðU σ Þ , where U σ is the is non-negative and covariant with respect to the permu- matrix of the irrep λ that represents σ ∈ SN and e denotes tation group, i.e., fðx; x0 Þ ¼ fðτx; τx0 Þ for all τ ∈ SN . the identity permutation (for simplicity, we omit the index e Then, W τx ¼ Uτ W x U†τ , and we need only to ensure that when no confusion arises). In other words, the family conditions (16) and (17) are met for reference strings, for of states ρn;σ is covariant with respect to SN . One can which x ¼ ðn; eÞ. In the Schur basis, their corresponding easily check that Ωn;σfλg is always a rank-1 projector (see operators, which we simply call W n , and the matrix Γ take Appendix B). In Eq. (12), it is understood that Ωn;σ fλg ¼ 0 the form, respectively, outside of the range of ρn;σ . With no loss of generality, the optimal measurement that W n ¼ ⨁1ðλÞ ⊗ ωnfλg ; ð18Þ λ discriminates the states ρn;σ can be represented by a POVM whose elements have the form shown in Eq. (12). Γ ¼ ⨁kλ 1ðλÞ ⊗ 1fλg ; ð19Þ Moreover, we can assume it to be covariant under SN λ [34]. So, such POVM elements can be written as where we use P the Schur lemma to obtain Eq. (19) and En;σ ¼ ⨁1ðλÞ ⊗ U λσ Ξnfλg ðUλσ Þ† ; ð13Þ define kλ ≡ n N!trðωnfλg Ξnfλg Þ=ðbn νλ Þ. Note that Γ is a λ diagonal matrix, in spite of the fact that ωnfλg are, at this where Ξnfλg is some positive operator. The resolution of point, arbitrary full-rank positive operators. the identity condition imposes constraints on them. The With Eqs. (18) and (19), the optimality conditions (16) condition reads and (17) can be made explicit. First, we note that the subspace (λ) is irrelevant in this calculation and that there is X X1 X an independent condition for each irrep λ. Taking into En;σ ¼ ⨁ 1ðλÞ ⊗ Uλσ Ξnfλg ðU λσ Þ† account these considerations, Eq. (16) now reads n;σ n bn σ∈S λ N ¼ ⨁1ðλÞ ⊗ 1fλg ; ð14Þ ωnfλg Ξnfλg ¼ Ξnfλg ωnfλg ¼ kλ Ξnfλg ∀ n; λ: ð20Þ λ where we use the factor bn to extend the sum over S n to the This equation tells us two things: (i) Since the matrices ωnfλg entire group SN and apply the Schur lemma. Taking the and Ξnfλg commute, they have a common eigenbasis, and trace on both sides of the equation, we find the POVM (ii) Eq. (20) is a set of eigenvalue equations for ωnfλg with a constraint to be common eigenvalue kλ , one equation for each eigenvector X N! of Ξnfλg . Therefore, the support of Ξnfλg is necessarily trðΞnfλg Þ ¼ νλ ∀ λ; ð15Þ restricted to a single eigenspace of ωnfλg . Denoting by n bn ϑnλ;a , a ¼ 1; 2; …, the eigenvalues of ωnfλg sorted in increas- where νλ is the dimension of 1fλg or, equivalently, the ing order, we have kλ ¼ ϑnλ;a for some a, which may depend multiplicity of the irrep λ of SUðdÞ [see Eq. (B5)]. on λ and n, or else Ξnfλg ¼ 0. 041029-7 GAEL SENTÍS et al. PHYS. REV. X 9, 041029 (2019) The second Holevo condition (17), under the same From this expression, one can easily derive the explicit considerations regarding the block-diagonal structure, forms of ϑnλ;1 and nðλÞ. We just need to consider the leads to maximum eigenvalue of the rank-one projector Ωnfλg, which can be either one or zero depending on whether or not the ωnfλg ≥ kλ 1fλg ∀ n; λ: ð21Þ input state ρn;σ has support in the irrep λ space. So, among the values of n for which ρn;σ does have support there, nðλÞ is This condition further induces more structure in the POVM. one that maximizes cn . Since cn is a decreasing function of n Given λ, Eq. (21) has to hold for every value of n. In in its allowed range (recall that n ≤ bN=2c), nðλÞ is the 0 particular, we must have minn0 ϑnλ;1 ≥ kλ . Therefore, smallest such value. 0 minn0 ϑnλ;1 ≥ ϑnλ;a for some a, or else Ξnfλg ¼ 0. Since Ξnfλg For the problem at hand, the irreps in the direct sum can cannot vanish for all n because of Eq. (15), we readily be labeled by Young diagrams of at most two rows or, see that equivalently, by partitions of N of length at most two (see Appendix B); hence, λ ¼ ðλ1 ; λ2 Þ, where λ1 þ λ2 ¼ N ( ξnλ Π1 ðωnfλg Þ if n ¼ nðλÞ; and λ2 runs from 0 to bN=2c. Given λ, only states ρn with nðλÞ kλ ¼ ϑλ;1 ; Ξnfλg ¼ ð22Þ n ¼ λ2 ; …; bN=2c have support on the irrep λ space, as 0 otherwise; readily follows from the Clebsch-Gordan decomposition rules. Then, where nðλÞ ¼ argminn ϑnλ;1 , Π1 ðωnfλg Þ is a projector onto the eigenspace of ωnfλg (not necessarily the whole subspace) nðλÞ nðλÞ ¼ λ2 ; ϑλ;1 ¼ μλ − ηcnðλÞ : ð26Þ corresponding to the minimum eigenvalue ϑnλ;1 , and ξnλ is a suitable coefficient that can be read off from Eq. (15): Equation (26) gives the optimal guess for the size n of the νλ bn smallest cluster. The rule is in agreement with our intuition. ξnλ ¼ ; ð23Þ The irrep ðN; 0Þ, i.e., λ2 ¼ 0, corresponding to the fully Dnλ N! symmetric subspace, is naturally associated with the value n ¼ 0, i.e., with all N systems being in the same state or where Dnλ ¼ dim ½Π1 ðωnfλg Þ, which completes the con- cluster; the irrep with one antisymmetrized index has struction of the optimal POVM. λ2 ¼ 1 and hints at a system being in a different state than For a generic cost function, we can now write down a the others, i.e., at a cluster of size one, and so on. closed, implicit formula for the minimum average cost We now have all the ingredients to compute the optimal achievable by any quantum clustering protocol. It reads success probability from Eq. (24). It reads X nðλÞ X f̄ ¼ trΓ ¼ sλ νλ ϑλ;1 ; ð24Þ Ps ¼ η cnðλÞ sλ νλ λ λ where sλ is the dimension of 1ðλÞ or, equivalently, the 1 X bN=2c  N ðd − 1ÞðN − 2i þ 1Þ2 multiplicity of the irrep λ of SN [see Eq. (B6)]. The only ¼ ; ð27Þ 2N−1 i¼0 i ðd þ i − 1ÞðN − i þ 1Þ2 object that remains to be specified is the function nðλÞ, which depends ultimately on the choice of the cost P function fðx; x0 Þ. P we use the relation λ sλ νλ μλ ¼ 1 that follows from where tr x ηx ρx ¼ 1 and the expressions of νλ and sλ from Eqs. (B5) and (B6) in Appendix B. 2. Success probability We now make Eq. (24) explicit by considering the success B. Clustering quantum states: Known input states probability Ps as a figure of merit; that is, we choose If the two possible states jϕ0 i and jϕ1 i are known, the fðx; x0 Þ ¼ 1 − δx;x0 and, hence, Ps ¼ 1 − f̄. We also optimal clustering protocol must use this information. It is assume that the source that produces the input sequence then expected that the average performance will be much is equally likely to prepare either state; thus, each string x has higher than for the universal protocol. It is natural in this the same prior probability, ηx ¼ 21−N ≡ η. In this case, W n context not to identify a given string x with its comple- takes the simple form mentary x̄ (we stick to the notation in the main text), since mistaking one state for the other should clearly count W n ¼ ⨁1ðλÞ ⊗ ðμλ 1fλg − ηcn Ωnfλg Þ; ð25Þ as an error if the two preparations are specified. In this λ case, then, clustering is equivalent to discriminating the where μλ are positive coefficients and we recall that the 2N known pure states jΦx i ¼ jϕx1 i ⊗ jϕx2 i ⊗    ⊗ jϕxN i expression in parentheses corresponds to ωnfλg in Eq. (18). (hypotheses), where with no loss of generality we can write 041029-8 UNSUPERVISED CLASSIFICATION OF QUANTUM DATA PHYS. REV. X 9, 041029 (2019) rffiffiffiffiffiffiffiffiffiffiffi rffiffiffiffiffiffiffiffiffiffiffi Z 1þc 1−c Ps ¼ dϕ0 dϕ1 Ps ðcÞ jϕ0=1 i ¼ j0i  j1i ð28Þ 2 2 Z Z 1 for a convenient choice of basis. Here, c ¼ jhϕ0 jϕ1 ij is the ¼ dc Ps ðcÞ dϕ0 dϕ1 δðjhϕ0 jϕ1 ij2 − c2 Þ 2 0 overlap of the two states. Z 1 Z The Gram matrix G encapsulates all the information ¼ dc Ps ðcÞ dϕ1 δðjh0jϕ1 ij2 − c2 Þ 2 0 needed to discriminate the states of the set. It is defined as Z 1 having elements Gx;x0 ¼ hΦx jΦx0 i. It is known that when ¼ dc2 μðc2 ÞPs ðcÞ; ð34Þ the pffiffiffiffidiagonal elements of its square root are all equal, i.e., 0 ð GÞx;x ≡ S for all x, then the square root measurement is R optimal [37,38] and the probability of successful identi- where we insert the identity 1 ¼ 01 dc2 δða2 − c2 Þ, for 0 < a ≡ jhϕ0 jϕ1 ij < 1, and use the invariance of the fication reads simply Ps ¼ S2. Notice that we implicitly measure dϕ under SUðdÞ transformations. The marginal assume uniformly distributed hypotheses. For the case at hand, distribution is μðc2 Þ ¼ ðd − 1Þð1 − c2 Þd−2 (see Appendix E). Using this result, the asymptotic behavior of the last integral is Gx;x0 ¼ ðhϕx1 j ⊗    ⊗ hϕxN jÞðjϕx01 i ⊗    ⊗ jϕx0N iÞ Y N 4ðd − 1Þ ¼ hϕxi jϕx0i i ¼ ðG⊗N Þx;x0 ; ð29Þ Ps ∼ : ð35Þ N i¼1 As expected, knowing the two possible states in the input where string leads to a better behavior of the success probability:   It decreases only linearly in 1=N, as compared to the best 1 c universal quantum clustering protocol, which exhibits a G¼ ð30Þ c 1 quadratic decrease. To do a fairer comparison with universal quantum pffiffiffiffi pffiffiffi is the Gram matrix of fjϕ0 i; jϕ1 ig. Thus, G ¼ ð GÞ⊗N , clustering, guessing the complementary string x̄ instead with of x is now counted as a success; that is, now the clusterings are defined by the states 0 pffiffiffiffiffiffi pffiffiffiffiffiffi 1 pffiffiffiffiffiffi pffiffiffiffiffiffi pffiffiffi 1þcþ 1−c 1þc− 1−c B 2 2 C jΦx ihΦx j þ jΦx̄ ihΦx̄ j G¼ @ pffiffiffiffiffiffi pffiffiffiffiffiffi pffiffiffiffiffiffi pffiffiffiffiffiffi A: ð31Þ ρx ¼ : ð36Þ 1þc− 1−c 1þcþ 1−c 2 2 2 For this variation of the problem, the optimal measurement pffiffiffiffi As expected, the diagonal terms of G are all equal, and is still local and given by a POVM with elements the success probability is given by Ex ¼ jΨx ihΨx j þ jΨx̄ ihΨx̄ j; ð37Þ pffiffiffiffiffiffiffiffiffiffi pffiffiffiffiffiffiffiffiffiffi2N  pffiffiffiffiffiffiffiffiffiffiffiffiN 1þcþ 1−c 1 þ 1 − c2 Ps ðcÞ ¼ ¼ : ð32Þ where jΨx i ¼ jψ x1 i ⊗ jψ x2 i ⊗    ⊗ jψ xN i and where we 2 2 recall that fjψ 0 i; jψ 1 ig is the (local) Helstrom measurement basis in Eq. (33). Note that fEx g are orthogonal projectors. We call the reader’s attention to the fact that one could To prove the statement in the last paragraph, we show attain the very same success probability by performing an that the Holevo-Yuen-Kennedy-Lax conditions [Eq. (16)] individual Helstrom measurement [25], with basis hold (recall that the Gram matrix technique does not apply to mixed states). For the success probability and assuming j0i  j1i jψ 0=1 i ¼ pffiffiffi ; ð33Þ equal priors, these conditions take the simpler form 2 X X Ex ρx ¼ ρx Ex ≡ Γ; ð38Þ on each state of the input sequence and guess that the x x label of that state is the outcome value. In other words, for the problem at hand, global quantum measurements Γ − ρx ≥ 0 ∀ x; ð39Þ do not provide any improvement over individual fixed measurements. where we drop the irrelevant factor η ¼ 21−N . Condition In order to compare with the results of the main text, we (38) is trivially satisfied. To check that condition (39) also compute the average performance for a uniform distribu- holds, we recall the Weyl inequalities for the eigenvalues of tion of states jϕ0 i and jϕ1 i, i.e., the average Hermitian n × n matrices A, B [39]: 041029-9 GAEL SENTÍS et al. PHYS. REV. X 9, 041029 (2019) ϑi ðA þ BÞ ≤ ϑiþj ðAÞ þ ϑn−j ðBÞ; ð40Þ V. DISCUSSION Unsupervised learning, which assumes virtually nothing for j ¼ 0; 1; …; n − i, where the eigenvalues are labeled in about the distributions underlying the data, is already a hard increasing order ϑ1 ≤ ϑ2 ≤ … ≤ ϑn. We use Eq. (40) to problem [22,23]. Lifting the notion of classical data to write quantum data (i.e., states) factors in additional obstacles, ϑ1 ðΓÞ ≤ ϑ3 ðΓ − ρx Þ þ ϑ2N −2 ðρx Þ ð41Þ such as the impossibility to repeatedly operate with the quantum data without degrading it. Most prominent (note that effectively all these operators act on the 2N - classical clustering algorithms heavily rely on the iterative dimensional subspace spanned by fj0i; j1ig⊗N ). As proved evaluation of a function on the input data (e.g., pairwise below, Γ > 0, which implies that ϑ1 ðΓÞ > 0. We note that distances between points in a feature vector space, as in ρx has rank two; i.e., it has only two strictly positive k-means [44]); hence, they are not equipped to deal with eigenvalues, so ϑ2N −2 ðρx Þ ¼ 0. Then, Eq. (41) implies degrading data and expectedly fail in our scenario. The unsupervised quantum classification algorithm we present ϑ3 ðΓ − ρx Þ ≥ ϑ1 ðΓÞ > 0: ð42Þ is thus, by necessity, far away from its classical analogs. In Finally, notice that Γ − ρx has two null eigenvalues, with particular, since we are concerned with the optimal quan- eigenvectors jΨx i and jΨx̄ i. Hence, ϑ1 ðΓ−ρx Þ¼ϑ2 ðΓ−ρx Þ¼ tum strategy, we need to consider the most general 0, and it follows from Eq. (42) that condition (39) must hold. collective measurement, which is inherently single shot: To show the positivity of Γ, which is assumed in the It yields a single sample of a stochastic action, namely, a previous paragraph, we use Eqs. (28) and (33) to write posterior state and an outcome of a quantum measurement, where the latter provides the description of the clustering.  ⊗N  ⊗N  The main lesson stemming from our investigation is that, 1 a1 0 b1 0 Γ¼ þ ; ð43Þ despite these limitations, clustering unknown quantum 2 0 a2 0 b2 states is a feasible task. The optimal protocol that solves it showcases some interesting features. where pffiffiffiffiffiffiffiffiffiffiffiffiffi It does not completely erase the information about a 1  c þ 1 − c2 a1=2 ¼ ; given preparation of the input data after clustering.—This 2 pffiffiffiffiffiffiffiffiffiffiffiffiffi result is apparent from Eq. (4), since the action of the 1  c − 1 − c2 POVM on the subspaces (λ) is the identity. After the input b1=2 ¼ : ð44Þ data string in the global state jΦx i is measured and outcome 2 λ is obtained (recall that λ gives us information about Notice that a1 > b1 and a2 > jb2 j. Thus, if 0 ≤ c < 1, we the size of the clusters), information relative to the parti- have ϑk > 0 for k ¼ 1; 2; …; 2N . The special case c ¼ 1 is cular states jϕ0=1 i remains in the subspace ðλ Þ of the global degenerate. Equation (39) is trivially saturated, rendering postmeasured state. Therefore, one could potentially use Ps ¼ 21−N , as it should be. further the posterior (clustered) states down the line as The maximum success probability can now be computed approximations of the two classes of states, which opens by recalling that Ps ðcÞ ¼ 21−N trΓ. We obtain the door for our clustering device to be used as an inter-  pffiffiffiffiffiffiffiffiffiffiffiffiffi  pffiffiffiffiffiffiffiffiffiffiffiffiffi mediate processor in a quantum network. This notwith- 1 þ 1 − c2 N 1 − 1 − c2 N standing, the amount of information that can be retrieved Ps ðcÞ ¼ þ ; ð45Þ 2 2 after optimal clustering is currently under investigation. It outbeats the classical and semiclassical protocols.—If where the first term corresponds to guessing correctly all the local dimension of the quantum data is larger than two, the states in the input string, whereas the second one results the dimensionality of the symmetric subspaces spanned by from guessing the other possible state all along the string. the global states of the strings of data can be exploited by One can easily check that the average over c of the second means of collective measurements with a twofold effect: term vanishes exponentially for large N, and we end up enhanced distinguishability of states, resulting in improved with a success probability given again by Eq. (35). clustering performance (exemplified by a linear increase Finally, we mention that one could consider a simple in the asymptotic success probability), and information- unambiguous protocol [40–43] whereby each state of the preserving data handling (to some extent, as discussed input string is identified with no error with probability above). This effect should be contrasted with the semi- Ps ðcÞ ¼ 1 − c; i.e., the protocol gives an inconclusive classical protocol, which essentially obliterates the infor- answer with probability 1 − Ps ¼ c. Therefore, the average mation content of the data (as a von Neumann measurement unambiguous probability of sorting the data is is performed on each system) and whose success proba- Z bility vanishes exponentially with the local dimension. 1 2ðd − 1Þ Ps ¼ 2 dccμðc2 Þð1 − cÞN ∼ : ð46Þ In addition, the optimal classical and semiclassical proto- 0 N2 cols require solving an NP-complete problem, and their 041029-10 UNSUPERVISED CLASSIFICATION OF QUANTUM DATA PHYS. REV. X 9, 041029 (2019) implementation is thus inefficient. In contrast, we observe algorithm then aims to identify, within a set of unknown that the first part of the quantum protocol, which consists in processes, which ones are causally connected. Identifying guessing the size of the clusters n, runs efficiently on a causal structures has recently attracted attention among the quantum computer: This step involves a Schur transform quantum information community [55]. that runs in polynomial time in N and log d [45,46], followed by a projective measurement with no computa- ACKNOWLEDGMENTS tional cost. The second part, guessing the permutation σ, requires implementing a group-covariant POVM. The We acknowledge the financial support of the Spanish complexity of this step, and, hence, the overall computa- MINECO, Ref. FIS2016-80681-P (AEI/FEDER, UE), and tional complexity of our protocol, is still an open question Generalitat de Catalunya CIRIT, Ref. 2017-SGR-1127. G. S. thanks the support of the Alexander von Humboldt currently under investigation. It is optimal for a range of different cost functions.— Foundation. E. B. also thanks the hospitality of Computer Science Department of the University of Hong Kong during There are various cost functions that could arguably be his stay. better suited to quantum clustering, e.g., the Hamming distance between the guessed and the true clusterings or, likewise, the trace distance or the infidelity between the APPENDIX A: PARTITIONS corresponding effective states ρn;σ and ρn0 ;σ 0 . They are, Partitions play an important role in the representation however, hard to deal with analytically. The question arises theory of groups and are central objects in combinatorics. as to whether our POVM is still optimal for such cost Here, we collect a few definitions and results that are used functions. To answer this question, we formulate an in the next appendixes, particularly in Appendix B. optimality condition that can be checked numerically for A partition λ ¼ ðλ1 ; λ2 ; …; λr ; …Þ is a sequence of non- problems of a finite size (see Appendix D). Our numerics negative integers in nonincreasing order. The length of λ, show that the POVM remains optimal for all these denoted lðλÞ, is the number of nonzero elements in λ. We examples. This result is an indication that the optimality of our protocol stems from the structure of the problem, denoteP by λ⊢N a partition λ of the integer N, where N ¼ i λi . A natural way of ordering partitions is by independently of the cost function. inverse lexicographic order; i.e., given two partitions λ and It stands a landmark in multihypothesis state dis- λ0 , we write λ > λ0 iff the first nonzero difference λi − λ0i is crimination.—Analytical solutions to multihypothesis positive. state discrimination exist only in a few specific cases The total number of partitions of an integer N is denoted [26–28,30,38,47]. Our set of hypotheses arises arguably by PN [56], and the number of partitions such that lðλÞ ≤ r from the minimal set of assumptions about a pure state ð≤rÞ by PN . Similarly, the number of partitions of length r is source: It produces two states randomly. Variants of this ðrÞ problem with much more restrictive assumptions are denoted by PN . There exists no closed expression for any considered in Refs. [11,48,49]. of these numbers, but there are widely known results (some Our clustering protocol departs from other notions of of them by Hardy and Ramanujan are very famous [57]) quantum unsupervised machine learning that can be found concerning their asymptotic behavior for large N. The one in the literature [50–53]. In these references, data coming we later use in Appendix F is from a classical problem are encoded in quantum states that ð≤rÞ N r−1 are available on demand via a quantum random access PN ∼ ; ðA1Þ memory [54]. The goal is to surpass classical performance r!ðr − 1Þ! in the number of required operations. In contrast, we deal with unprocessed quantum data as input and aim at which gives the dominant contribution for large N. Note ðrÞ ð≤rÞ ð≤r−1Þ performing a task that is genuinely quantum. This scenario that, from the obvious relation PN ¼ PN − PN , it ðrÞ is notably harder, where known heuristics for classical follows that the same asymptotic expression holds for PN . algorithms simply cannot work. Partitions are conveniently represented by Young dia- Other extensions of this work currently under inves- grams. The Young diagram associated to the partition λ⊢N tigation are clustering systems whose states can be of more is an arrangement of N empty boxes in lðλÞ rows, with λi than two types, where we expect a similar two-step boxes in the ith row. This association is one to one; hence, λ measurement for the optimal protocol, and clustering of can be used to label Young diagrams as well. A Young quantum processes, where the aim is to classify instances tableau of d entries is a Young diagram filled with integers of unknown processes by letting them run on some input from 1 up to d, one in each box. There are two types of test state of our choice (see Ref. [11] for related work on tableaux: A standard Young tableau (SYT) of shape λ⊢N is identifying malfunctioning devices). In this last case, an one where d ¼ N and such that the integers in each row interesting application arises when considering causal increase from left to right and from top to bottom in relations as the defining feature of a cluster. A clustering each column (hence, each integer appears exactly once). 041029-11 GAEL SENTÍS et al. PHYS. REV. X 9, 041029 (2019) A semistandard Young tableau (SSYT) of shape λ⊢N and that may arise, we write λ in parentheses, (λ), when it refers d entries, d ≥ lðλÞ, is one such that integers in each row are to the irreps of SUðdÞ or in braces, fλg, when it refers to nondecreasing from left to right and increasing from top to those of SN . Equation (B1) tells us that the dimension of bottom in each column. (λ), sλ , coincides with the multiplicity of fλg, and, con- The number of different SYTs of shape λ⊢N is given by versely, the dimension of fλg, νλ , coincides with the the hook-length formula multiplicity of (λ). This block-diagonal structure provides a decomposi- νλ ¼ Q N! ; ðA2Þ tion of Hilbert space H⊗N ¼ ðd; CÞ⊗N into subspaces that ði;jÞ∈λ hij are invariant under the action of SUðdÞ and SN , as H⊗N ¼ ⨁Hλ , and, in turn, Hλ ¼ HðλÞ ⊗ H fλg . The basis where ði; jÞ denotes the box located in the ith row and the λ jth column of the Young diagram and hij is the hook length in which H⊗N has this form is known as the Schur basis, of the box ði; jÞ, defined as the number of boxes located and the unitary transformation that changes from the beneath or to the right of that box in the Young diagram, computational to the Schur basis is called the Schur counting the box itself. Likewise, the number of SSYTs of transform. shape λ⊢N and d entries is given by the formula To conclude this Appendix, let us recall the rules for reducing the tensor product of two SUðdÞ representations as a Clebsch-Gordan series of the form Δðλ1 þ d − 1; λ2 þ d − 2; …; λd Þ sλ ¼ ; ðA3Þ Δðd − 1; d − 2; …; 0Þ 0 Rλ ⊗ Rλ ¼ ⨁Rλ ⊗ 1λ 00 00 ∀ R ∈ SUðdÞ; ðB2Þ λ00 Q where Δðx1 ; x2 ; …; xd Þ ¼ i 1. In this case, d is the leading contri- effective states ρn;σ (hypotheses). bution in the second factor in the denominator of Eq. (C1). Here, we conjecture that the choice Ξnfλg ¼ Ωnfλg δn;nðλÞ is Accordingly, we have still optimal for a large class of cost functions fðx; x0 Þ, albeit with varying guessing rules nðλÞ. If the conjecture Z ∞ 4x2 2e−mx 2 holds, given fðx; x0 Þ, one has only to compute nðλÞ ¼ Ps ∼ ðd − 1Þm dx pffiffiffiffiffiffiffi argminn ϑnλ;1 to obtain the optimal POVM. The minimum 0 ð1 þ xÞ2 d mπ Z 2 average cost can then be computed via Eq. (24). We now ∞ 2xe−mx 2 ∼ 4m dxx pffiffiffiffiffiffiffi ¼ ; ðC7Þ formulate this conjecture precisely as a testable mathemati- 0 mπ m cal condition. For any cost function (distance) such that fðx; x0 Þ ≥ 0 and the asymptotic expression becomes and fðx; x0 Þ ¼ 0 iff x ¼ x0 , we can always find some 4 constant t > 0 such that Ps ∼ ; ðC8Þ N tfðx; x0 Þ ≥ δ̄x;x0 ≡ 1 − δx;x0 ∀ x; x0 : ðD1Þ independently of d. Finally, let us assume that d scales exactly as N and write We can then rescale the cost function f ↦ t−1 f and assume d ¼ sN, s > 0. The success probability can be cast as with no loss of generality that fðx; x0 Þ ≥ δ̄x;x0 . We have Z 2 ∞ 4x2 2e−mx W x ¼ W̄ x þ Δx ; ðD2Þ Ps ∼ ðd − 1Þ dx pffiffiffiffiffiffiffi : ðC9Þ 0 ð1 þ xÞ2 ð1 þ 2s − xÞ mπ where we use the definition of W x after Eq. (16) and Proceeding as above, we obtain similarly define W̄ x for the minimal cost δ̄x;x0 . As in Sec. IVA, it suffices to consider x ¼ ðn; eÞ. Then, 2ðd − 1Þ X Ps ∼ : ðC10Þ ð2s þ 1Þm2 Δx ¼ ηx0 ½fðx; x0 Þ − δ̄x;x0 ρx 0 ≥ 0: ðD3Þ x0 Thus, Using the same notation as in Eq. (18), Eq. (D3) is 8s equivalent to Ps ∼ : ðC11Þ ð2s þ 1ÞN ωnfλg − ω̄nfλg ≥ 0: ðD4Þ The three expressions, Eqs. (C6), (C8), and (C11), can be combined into a single one as We now recall the meaning of Eqs. (20) and (21): The 8ðd − 1Þ operators Ξnfλg must be projectors onto the eigenspace of the Ps ∼ : ðC12Þ minimal eigenvalue of ωnfλg . Then, according to Eq. (22), ð2d þ NÞN the choice Ξnfλg ¼ Ωnfλg δn;nðλÞ is also optimal for arbitrary cost functions if it holds that APPENDIX D: OPTIMAL POVM FOR GENERAL COST FUNCTIONS ? suppðΩnfλg Þ ¼ V 1 ðω̄nfλg Þ⊂V 1 ðωnfλg Þ; ðD5Þ This Appendix deals with the optimization of quantum clustering assuming other cost functions. We introduce a where V 1 ðXÞ is the eigenspace of the minimal eigenvalue of sufficient condition under which the type of POVM we use X and the equality follows from Eq. (25). 041029-14 UNSUPERVISED CLASSIFICATION OF QUANTUM DATA PHYS. REV. X 9, 041029 (2019) correspondence with optimal guesses for n. In Table I, we show values of nðλÞ for our four cost functions and N ¼ 4; …; 8. In contrast to the case of the success probability (the cost function δ̄x;x0 ), we note that in some cases it is actually optimal to map several irreps to the same guess while never guessing certain cluster sizes. Performing the Schur transform is computationally inefficient on a classical computer (In contrast, as men- tioned in the main text, there exist efficient quantum circuits able to implement the Schur transform in a quantum computer. A circuit based on the Clebsch- Gordan transform achieves polynomial time in N and d [45]. Recently, an alternative method based on the repre- sentation theory of the symmetric group was shown to reduce the dimension scaling to polyðlog dÞ [46].), which sets a limit on the size of the data one can test—in our case it is N ¼ 8. However, it is worth mentioning that this FIG. 3. Heat map of the Hamming distances hðx; x0 Þ between difficulty might actually be overcome. The fundamental clusterings for N ¼ 8. The clusterings are grouped by the size of the smallest cluster n ¼ 0, 1, 2, 3, 4. Each group contains all objects needed for testing Eq. (D5) are the operators Ωnfλg . nontrivial permutations σ for a given n. A brighter color means a Their computation does, in principle, not require the full smaller Hamming distance. Schur transform, as they can be expressed in terms of generalized Racah coefficients, which give a direct relation between Schur bases arising from different coupling Our conjecture is that Eq. (D5) holds true for the class of schemes of the tensor product space. It is indeed possible “reasonable” cost functions considered in this paper, to calculate generalized Racah coefficients directly without namely, for those that are non-negative and covariant going through a Clebsch-Gordan transform [60], and, and satisfy the distance property stated before Eq. (D1). should this method be implemented, clustering problems We check its validity for problems of size up to N ¼ 8, of larger sizes might be tested. However, an extensive local dimension d ¼ 2, and uniform prior probabilities numerical analysis is not the aim of this paper. for the following cost functions: Hamming distance hðx; x0 Þ ¼ minfjx − x0 j; jx − x̄0 jg (xi ¼ 0, 1), trace dis- APPENDIX E: PRIOR DISTRIBUTIONS tance Tðx; x0 Þ ¼ jjρx − ρx0 jj1 , and infidelity Iðx; x0 Þ ¼ 1− pffiffiffiffiffi pffiffiffiffiffi tr2 ½ð ρx ρx0 ρx Þ1=2 . In the interest of making this paper self-contained, in this The above examples induce a much richer structure in Appendix we include the derivation of some results about the problem at hand. To illustrate this added complexity, in the prior distributions P used in the paper. Fig. 3 we show a heat map of the Hamming distances Let Sd ¼ fps ≥ 0j ds¼1 ps ¼ 1g denote the standard hðx; x0 Þ between all pairs of clusterings for N ¼ 8. The (d − 1)-dimensional (probability) simplex. Every categorical figure shows that the largest values of hðx; x0 Þ can occur for distribution (CD) P ¼ fps gds¼1 is a point in Sd . The flat two clusterings with equal cluster size n and that hðx; x0 Þ is distribution of CDs is the volume element divided by the extremely dependent on the pair of permutations σ; σ 0 . As a volume of Sd , the latter denoted by V Q d. Choosing coordinates result, the guessing rule nðλÞ is completely different p1 ; …; pd−1 , the flat distribution is d−1 s¼1 dps =V d ≡ dP. from the one that maximizes the probability of success Let us compute the moments of the flat distribution; as a Ps . In particular, irreps λ are no longer in one-to-one by-product, we obtain V d . We have TABLE I. Values of nðλÞ, i.e., of the optimal guess for the size of the smallest cluster, where λ ¼ ðλ1 ; λ2 Þ are the relevant irreps, for data sizes N ¼ 4, 5, 6, 7, 8, and cost functions δ̄ðx; x0 Þ (corresponding to the success probability), Hamming distance hðx; x0 Þ, trace distance Tðx; x0 Þ, and infidelity Iðx; x0 Þ. N¼4 N¼5 N¼6 N¼7 N¼8 λ (4,0) (3,1) (2,2) (5,0) (4,1) (3,2) (6,0) (5,1) (4,2) (3,3) (7,0) (6,1) (5,2) (4,3) (8,0) (7,1) (6,2) (5,3) (4,4) δ̄ 0 1 2 0 1 2 0 1 2 3 0 1 2 3 0 1 2 3 4 h 0 2 2 0 2 2 0 3 2,3 3 0 3 3 3 0 4 4 4 4 T 1 1 2 1 1 2 1 1 2 3 1 2 2 3 1 2 3 3 4 I 0 1 2 0 1 2 0 1 2 3 0 1 3 3 0 1 3 4 4 041029-15 GAEL SENTÍS et al. PHYS. REV. X 9, 041029 (2019) Z Y Z Z Z Y Qd Q s¼1 ns ! ðd − 1Þ! ds¼1 ns ! d 1 1−p1 d Vd dP pns s ¼ dp1 dp2 … dϕ pns s ¼ ¼ : ðE5Þ Sd s¼1 0 0 s¼1 N!Dsym N ðN þ d − 1Þ! Z Pd−2 1− ps Y d × s¼1 dpd−1 pns s This equation agrees with Eq. (E2), which means that all 0 s¼1 the moments of the distribution induced from the uniform Qd distribution of pure states coincide with the moments of a s¼1 ns ! ¼ P ðE1Þ flat distribution of CDs on Sd . Since the moments uniquely ðd − 1 þ ds¼1 ns Þ! determine the distributions with compact support [61] (and Sd is compact), we conclude that they are identical. [the calculation becomes straightforward by iterating P the As a by-product, we can compute the marginal distri- change of variables pr ↦ x, where pr ¼ ð1 − r−1 s¼1 p s Þx, bution μðc2 Þ, where c is the overlap of jϕi with a fixed state r ¼ d − 2; d − 3; …; 2; 1]. In particular, setting ns ¼ 0 for jψi. Since we can always find a basis such that jψi is its all s in Eq. (E1), we obtain V d ¼ 1=ðd − 1Þ!. Then, first element, we have c ¼ jh1jϕij. Because of the results above, the marginal distribution is given by Z Q Y d ðd − 1Þ! ds¼1 ns ! Z 1−p Z 1−Pd−2 p  dP pns s ¼ ; ðE2Þ  dpd−1  1 s¼1 s 2 Sd ðd − 1 þ NÞ! μðc Þ ¼ dp2 … s¼1 0 0 2 p1 ¼c P ¼ ðd − 1Þð1 − c Þ 2 d−2 ; ðE6Þ where N ¼ ds¼1 ns . Next, we provide a simple proof that any fixed von in agreement with Ref. [62]. Neumann measurement on a uniform distribution of pure states in ðd; CÞ gives rise to CDs whose probability distribution is flat. As a result, the classical and semi- APPENDIX F: OPTIMAL CLUSTERING classical strategies discussed in the main text have the same PROTOCOL FOR UNKNOWN success probability. CLASSICAL STATES Take jϕi ∈ ðd; CÞ and let fjsigds¼1 be an orthonormal In this Appendix, we provide details on the derivation of basis of ðd; CÞ. By performing the corresponding von the optimal protocol for a classical clustering problem, Neumann measurement, the probability of an outcome s analog to the quantum problem discussed in the main text. is ps ¼ jhsjϕij2 . Thus, any distribution of pure states The results here also apply to quantum systems when the induces a distribution of CDs fps ¼ jhsjϕij2 gds¼1 on Sd . measurement performed on each of them is restricted to be Let us compute the moments of the induced distribution, local, projective, d dimensional, and fixed. We call this type namely, of protocol semiclassical. Here, we envision a device that takes input strings of N Z Y d Z data points s ¼ ðs1 s2 …sN Þ, with the promise that each si is d dϕ pns s ¼ dϕtr½ ⊗ ðjsihsjÞ⊗ns ðjϕihϕjÞ⊗N  a symbol out of an alphabet of d symbols, say, the set s¼1 s¼1 f1; 2; …; dg, and is drawn from either roulette P or from 1 d ⊗ns sym roulette Q, with corresponding categorical probability ¼ sym tr½ ⊗ ðjsihsjÞ 1N ; ðE3Þ DN s¼1 distributions P ¼ fps gds¼1 and Q ¼ fqs gds¼1 . To simplify the notation, we use the same symbols for the roulettes and where we recall that Dsym N (1sym N ) is the dimension of their corresponding probability distributions and for the (projector on) the symmetric subspace of ðd; CÞ⊗N and stochastic variables and their possible outcomes. Also, the we have used the Schur lemma. A basis of the symmetric range of values of the index s is always understood to be subspace is f1; 2; …; dg, unless specified otherwise. The device’s task is to group the data points in two clusters so that all points in rffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi Qd ffi either cluster have a common underlying probability dis- n ! X d tribution (either P or Q). We wish the machine to be jvn i ¼ s¼1 s Uσ ⊗ jsi⊗ns ; ðE4Þ N! σ∈S s¼1 universal, meaning that it operates without knowledge on N the distributions P and Q. Accordingly, we choose as the figure of merit the probability of correctly classifying all data where n ¼ ðn1 ; n2 ; …; nd Þ. Note that there are ðNþd−1 d−1 Þ points, averaged over every possible sequence of roulettes different strings n (weak compositions of N in d parts), x ¼ ðx1 x2 …xN Þ, xi ∈ fP; Qg, and over every possible which agrees with DsymN ¼P sðN;0Þ [recall Eq. (B6)], as it distribution P and Q. The latter are assumed to be uniformly should be. Since 1sym N ¼ n jvn ihvn j, we can easily distributed over the common probability simplex Sd on compute the trace in Eq. (E3) to obtain which they are defined. Formally, this success probability is 041029-16 UNSUPERVISED CLASSIFICATION OF QUANTUM DATA PHYS. REV. X 9, 041029 (2019) Z X Appendix. Note that all the dependence on x is through Pcls ¼ dPdQ Pr ðx̂ ∈ fx; x̄g; s; x; P; QÞ Sd x;s the occurrence numbers ms and ns . Z X According to Eq. (F2), for each string s we need to ¼2 dPdQ δx̂;x Pr ðs; x; P; QÞ; ðF1Þ maximize the joint probability Prðs; xÞ in Eq. (F4) over all Sd x;s possible sequences of roulettes x. We first note that, given a total of Ms occurrences of a symbol s in s, Prðs; xÞ is where x̂ is the guess of x emitted by the machine, which by maximized by a sequence x whereby all these occurrences the universality requirement, can depend only on the data come from the same type of roulette, in other words, by a string s. The sums are carried out over all 2N possible strings sequence x such that either ms ¼ Ms and ns ¼ 0 or else s and sequences of roulettes x. The factor of 2 in the second ms ¼ 0 and ns ¼ M s . equality takes into account that P and Q are unknown; In order to prove the above claim, we single out a hence, identifying the complementary string x̄ leads to the particular symbol r that occurs a total number of times same clustering. By emitting x̂, the device suggests a μ ¼ M r in s. We focus on the dependence of Prðs; xÞ on the classification of the N data points si in two clusters. In occurrence number t ¼ mr (so, nr ¼ μ − t) by writing the above equation, we use the notation of Appendix E for the integral over the probability simplex. aðμ − tÞ!t! Prðs; xÞ ¼ ≡ fðtÞ; ðF5Þ An expression for the optimal success probability can be ðb þ tÞ!ðc − tÞ! obtained from the trivial upper bound where the coefficients a, b, and c are defined, XZ respectively, as Pcls ¼ 2 dPdQ Pr ðs; x̂; P; QÞ d♭ !2 Y s X Z a¼ n !m !; ðF6Þ ≤2 max dPdQ Pr ðs; x; P; QÞ 2N s≠r s s x s X X ¼2 max Pr ðs; xÞ; ðF2Þ b ¼ d♭ þ ms ; ðF7Þ x s s≠r X X where Pr ðs; xÞ is the joint marginal distribution of s and x. c ¼ d♭ þ ns þ mr ¼ d♭ þ N − ms ðF8Þ This bound is attained by the guessing rule s s≠r x̂ ¼ argmax Pr ðs; xÞ: ðF3Þ and are independent of t. The function fðtÞ can be extended x to t ∈ R using the Euler gamma function and the relation Γðt þ 1Þ ¼ t!. This extension enables us to compute the For two specific distributions P and Q, the probability second derivative of fðtÞ and show that it is a convex that a given roulette sequence Q x gives rise to a particular function of t in the interval ½0; μ. Indeed, data string s is Prðsjx; P; QÞ ¼ s pns s qm s s , where ns (ms ) is the number of occurrences of symbol s in s [i.e., how many f 00 ðtÞ si ∈ s satisfy si ¼ s] arising from roulettes of type P (Q). ¼ ½H1 ðc − tÞ − H1 ðμ − tÞ − H 1 ðb þ tÞ þ H1 ðtÞ2 fðtÞ For later convenience, we define Ms ¼ ns þ ms , which gives the total number of such occurrences. Note that fMs g þ H2 ðc − tÞ − H2 ðμ − tÞ þ H2 ðb þ tÞ − H2 ðtÞ ≥ 0; is independent of x, whereas fns g and fms g are not. ðF9Þ Performing the integral over P and Q, we have where Hn ðtÞ are the generalized harmonic numbers. P For PrðsjxÞ positive integer values of t, they are Hn ðtÞ ¼ tj¼1 j−n . Prðs; xÞ ¼ P 2ZN The relation Hn ðtÞ ¼ ζðnÞ − ∞ −n P∞ −n j¼1 ðt þ jÞ , where ζðnÞ ¼ 1 ¼ N dPdQ Prðsjx; P; QÞ j¼1 j is the Riemann zeta function, allows one to 2 Q extend the domain of Hn ðtÞ to real (and complex) values 2−N d♭ !2 s ns !ms ! of t. ¼ P P ; ðF4Þ ðd♭ þ s ms Þ!ðd♭ þ s ns Þ! The positivity of f 00 ðtÞ follows from the positivity of both fðtÞ and the two differences of harmonic numbers in the where we use Eq. (E2) and in the first equality we assume second line of Eq. (F9). Note that H 2 ðxÞ is an increasing that the two types of roulette P and Q are equally probable; function P of x. Since, obviously, b þ t > t and c − t > P hence, each possible sequence x occurs with equal prior n s s ¼ s ðM s − ms Þ ≥ μ − t [as follows from the probability equal to 2−N . We also introduce the notation definition of c in Eq. (F8)], we see that the two differences d♭ ≡ d − 1 to shorten the expressions throughout this are positive. 041029-17 GAEL SENTÍS et al. PHYS. REV. X 9, 041029 (2019) The convexity of fðtÞ for t ∈ ½0; μ implies that the The subset Q that minimizes this expression determines the maximum of fðtÞ is at either t ¼ 0 or t ¼ μ. This optimal clustering. implication holds for every value of Mr and every symbol In summary (and not very surprisingly), the optimal r in the data string, so our claim holds. In summary, the guessing rule consists in first partitioning the data s in up to optimal guessing rule must assign the same type of roulette d groups according to the symbol of the data points and, to all the M s occurrences of a symbol s; i.e., it must group second, merging those groups (without splitting them) in all data points that show the same symbol in the same two clusters in such a way that their sizes are as similar as cluster, which is in full agreement with our own intuition. possible. We have stumbled upon the so-called partition The description of the optimal protocol that runs on our problem [33], which is known to be weakly NP complete. device is not yet complete. We need to specify how to reduce In particular, a large set of distinct occurrence counts fMs g the current number of clusters down to two, since at this rapidly hinders the efficiency of known algorithms, a point we may (and typically will) have up to d clusters, as situation likely to occur for large d. It follows that the many as different symbols. The reduction or merging of the optimal clustering protocol for the classical problem cannot d clusters can be based only on their relative sizes, as nothing be implemented efficiently in all instances of the problem. is known about the underlying probability distributions. To obtain the maximum success probability Pcls This restriction is quite clear: Let P be the subset of symbols [Eq. (F2)], we need to sum the maximum joint probability, (e.g., the subset of f1; 2; …; dg) for which ns ¼ M s , and let given by Eq. (F11) with x ¼ x , over all possible strings s. Q be its complement; i.e., Q contains the symbols for which Those with the same set of occurrence counts fM s g give ms ¼ Ms , and P ¼ Q̄. The claim we just proved tells us that, the same contribution. Moreover, all the dependence on in order to find the maximum of Prðs; xÞ, it is enough to fM s g is through the bias Δ. Therefore, if we define ξΔ to be consider sequences of roulettes x that comply with the the number of sets fMs g that give rise to a bias Δ, then the above conditions on the occurrence numbers (For corresponding number of data strings is ξΔ N!=Πs Ms !. We example, suppose d ¼ 3 and N ¼ 12. Assuming that s ¼ thus can write ð112321223112Þ is the string of data, the sequence of X roulettes x in the table 21−N ξΔ d♭ !2 N! Pcls ¼ : ðF13Þ Δ ðd♭ þ þ ΔÞ!ðd♭ þ N2 − ΔÞ! N 2 i 1 2 3 4 5 6 7 8 9 10 11 12 S 1 1 2 3 2 1 2 2 3 1 1 2 Equation (F13) is as far as we can go, as no explicit X P P Q Q Q P Q Q Q P P Q formula for the combinatorial factor ξΔ is likely to exist for general cases. However, it is possible to work out satisfies the conditions ms ¼ Ms or ns ¼ Ms, since the asymptotic expression of the maximum success prob- n1 ¼ M1 ¼ 5, m2 ¼ M2 ¼ 5, and m3 ¼ M3 ¼ 2. In this ability for large data sizes N. We first note that a generic case, P ¼ f1g, and Q ¼ f2; 3g. The suggested clustering is term in the sum (F13) can be written as the factor fð1; 2; 6; 10; 11Þ; ð3; 4; 5; 7; 8; 9; 12Þg). For those, the joint 22d♭ þ1 ξΔ d♭ !2 N!=ð2d♭ þ NÞ! times a binomial distribution probability Prðs; xÞ can be written as that peaks at Δ ¼ 0 for large N. Hence, the dominant a contribution in this limit is Prðs; xÞ ¼ P P ; ðF10Þ ðd♭ þ s∈Q M s Þ!ðd♭ þ s∈P M s Þ! 22d♭ þ1 d♭ !2 N! 22d−1 ðd − 1Þ!2 2−N d♭ !2 Πs Ms !. Pcls ∼ ξ0 ∼ ξ0 : ðF14Þ where a now simplifies to Thus, it just ð2d♭ þ NÞ! N 2d−2 remains to find the partition fP; Qg that maximizes this expression. It can also be written as From the definition of ξΔ , given above Eq. (F13), and a that of Δ in Eq. (F12), we readily see that ξ0 is the number Prðs; xÞ ¼ ; ðF11Þ of ordered partitions (i.e., the order matters) of N in d ðd♭ þ xÞ!ðd♭ þ N − xÞ! addends or parts [These ordered partitions are known as where we define x ¼ Σs∈Q M s . The maximum of this weak compositions of N into d parts in combinatorics, function is located at x ¼ N=2, and one can easily check where weak means that some addends (or parts) can be that it is monotonic on either side of its peak. Note that, zero; in contradistinction, the term composition is used depending on the values of the occurrence numbers fMs g, when all the parts are strictly positive.] (the occurrence the optimal value x ¼ N=2 may not be attained. In such counts M s ) such that a subset of these addends is an ordered cases, the maximum of Prðs; xÞ is located at x ¼ N=2  Δ, partition of N=2 as well. where Δ is the bias: Young diagrams come in handy to compute ξ0 . First, we draw pairs of diagrams ½λ; λ0 , each of N=2 boxes and such   1 X X  that λ ≥ λ0 (in lexicographical order; see Appendix A), and  Δ ¼ min M s − M s : ðF12Þ lðλÞ þ lðλ0 Þ ≡ r þ r0 ≤ d; i.e., the total number of rows 2 Q s∈Q s∈Q̄ should not exceed d. Next, we fill the boxes with symbols 041029-18 UNSUPERVISED CLASSIFICATION OF QUANTUM DATA PHYS. REV. X 9, 041029 (2019) APPENDIX G: OPTIMAL CLUSTERING PROTOCOL FOR KNOWN CLASSICAL STATES In this Appendix, we give a short discussion on clustering classical states under the assumption that the underlying probability distributions are known. In par- ticular, we discuss two low-dimensional cases, d ¼ 2, 3, and derive the asymptotic expression of the success FIG. 4. Use of Young diagrams for computing ξ0 . In the probability of clustering for large data string length N example, N ¼ 8 and d ¼ 4. The fraction before each pair gives and arbitrary data dimension d. We stick to the notation the number of different fillings and hints at how it is computed. introduced in Appendix F. If the underlying probability distributions are known, si (representing possible data points) so that all the boxes in a given data point s is optimally assigned to the proba- each row have the same symbol. We readily see that the bility distribution for which s is most likely. The success number of different fillings gives us ξ0 . An example is probability is thus given by maxfps ; qs g=2 (recall that the provided in Fig. 4 for clarity. data are assumed to be drawn from either P or Q with equal Although this pictorial method eases the computation of prior probability). The average success probability of ξ0 , it becomes unpractical even for relatively small values clustering over all possible strings of length N then reads of N. However, it becomes again very useful in the X N X N  1 d d asymptotic limit, since the number of Young diagrams Pcls;PQ ¼ N maxfps ;qs g þ minfps ;qs g ; with at least two rows of equal size becomes negligibly 2 s¼1 s¼1 small for large N. (Actually, the number of Young diagrams ðG1Þ of a given length with an unequal number of boxes in each row is equal to the number of Young diagrams of N − where the second term arises because assigning the ðrÞ rðr − 1Þ=2 boxes; i.e., it is equal to PN−rðr−1Þ=2 . Using the wrong probability distribution to all data points in s gives a correct clustering. In order to compare with our results for results in Appendix A, we immediately see that for large N unknown classical states, we average the success proba- ðrÞ ðrÞ one has PN−rðr−1Þ=2 =PN ∼ 1, which proves the statement.) bility over a uniform distribution of categorical probability The same conclusion applies to the whole pairs ½λ; λ0 , distributions. This average yields since, e.g., by reshuffling rows, one could merge the two Z Z members into a single diagram of N boxes and length Pcls ¼ dP dQPcls;PQ ; ðG2Þ r þ r0 . Thus, we may assume that all pairs of diagrams with Sd Sd a given total length have an unequal number of boxes in each row, which renders the counting of different fillings where the integration over the simplex Sd , shared by P and trivial: There are d!=ðd − r − r0 þ 1Þ! ways of filling each Q, is defined in Appendix E. pair of diagrams. Recalling that there is a one-to-one To perform the integral in Eq. (G2), we need to partition mapping between partitions and Young diagrams, we Sd × Sd in different regions according to whether ps ≤ qs can use Eq. (A1) and write or ps > qs for the various symbols. By symmetry, the integral can depend only on the number r of symbols for which ps ≤ qs (not on its particular value). Hence, r ¼ 1Xd−1 X d−r ðrÞ ðr0 Þ d! 1; …; d − 1 labels the different types of integral that we ξ0 ∼ PN PN need to compute to evaluate Pcls . Notice that we have the 2 r¼1 r0 ¼1 2 2 ðd − r − r0 Þ!   additional symmetry r ↔ d − r, corresponding to exchang- 1 N d−2 X d rðd − rÞd! ing ps and qs for all s. Since the value of these integrals ∼ 2 ðd − rÞ!2 does not depend on the specific value of s, we can choose 2 2 r!   r¼1 all ps with s ¼ 1; 2; …; r to satisfy ps > qs and all ps with 1 N d−2 ð2d − 2Þ! s ¼ r þ 1; r þ 2; …; d to satisfy ps ≤ qs. To shorten the ∼ : ðF15Þ 2 2 ðd − 2Þ!ðd − 1Þ!2 expressions below, we define X k X k This result, together with Eq. (F14), leads us to the desired pk ≔ ps ; qk ≔ qs : ðG3Þ asymptotic expression for the optimal success probability: s¼1 s¼1 P  d With these definitions, pd ¼ qd ¼ 1, ds¼rþ1 qs ¼ 1 − qr , 2 ð2d − 2Þ! Pd Ps ∼ cl : ðF16Þ and likewise s¼rþ1 ps ¼ 1 − pr . The integrals that we N ðd − 2Þ! need to compute are then 041029-19 GAEL SENTÍS et al. PHYS. REV. X 9, 041029 (2019) Z Z p Z p 1 1 r illustrated by the string s ¼ ð112Þ, which is labeled as PPQ I dr ≔ dP dq1 … dqr Sd Vd 0 0 (or QQP) if P and Q are unknown. However, if they are Z p −q Z p −q known and, e.g., p1 > q1 and p2 > q2 , the string is more rþ1 r d−1 d−2 × dqrþ1 … dqd−1 appropriately labeled as PPP. prþ1 pd−1 × ½ð1 þ pr − qr Þ þ ð1 þ qr − pr ÞN ; N ðG4Þ 2. Arbitrary data dimension: Large N limit and we note that, as anticipated, I dr ¼ I dd−r . The average For increasing N, however, the advantage of knowing P probability of successful clustering then reads and Q becomes less significant and vanishes asymptoti- cally, which can be checked explicitly for d ¼ 2, 3 by d−1   expanding Eqs. (G6) and (G7) in inverse powers of N. In 1 X d d Pcls ¼ N I ; ðG5Þ this regime, the average is dominated by distributions for 2 r¼1 r r which pr ≈ 1 and qr ≈ 0. Since in a typical string approx- imately half of the data come from the distribution P and where the binomial is the number of equivalent integral the other half from Q, the optimal clustering protocol regions for the given r. essentially coincides with that for unknown distributions; i.e., it collects the data points showing the same symbol in 1. Low data dimension the same subcluster and afterwards merges the subclusters We can now discuss the lowest-dimensional cases, for into two clusters of approximately the same size. We next which explicit closed formulas for I dr can be derived. For prove that this intuition is right for all d. d ¼ 2, one has In the proof, we make repeated use of the trivial observation that, for asymptotically large N and 0 < a < 8 − 22−N b < c, one has Pcls ¼ : ðG6Þ Z b ðN þ 2ÞðN þ 1Þ ðc − xÞN dx ∼ ðc − aÞNþ1 =N: ðG8Þ a This result coincides with that of unknown probability distributions given in Eq. (F13) with ξΔ ¼ 1. This result is We also note that the contribution to the success probability expected, as the optimal protocol for known and unknown coming from the completely wrong assignment of distribu- probability distributions is exactly the same: Assign to the tions, i.e., ð1 þ qr − pr ÞN , is exponentially vanishing, since same cluster all data points that show the same symbol s. we assume pr > qr , and thus qr − pr < 0 [this fact is well Therefore, knowing the probability distribution does not illustrated by the terms proportional to 22−N in Eqs. (G6) provide any advantage for d ¼ 2. and (G7)]. For d > 2, however, knowledge of the distributions P Because of this last observation, we can drop the second and Q helps classify the data points. If d ¼ 3, the success term in the integrand of I dr [Eq. (G4)]. The integrals over qs, probability (G5) can be computed to be s ≤ r, of the remaining term, ð1 þ pr − qr ÞN , are domi- nated by the lower limit qs ¼ 0, as this value maximizes 25 ðN − 2Þ − 22−N ðN 2 þ 7N þ 18Þ 1 þ pr − qr . Using Eq. (G8), we get Pcls ¼ 6 : ðG7Þ ðN þ 4ÞðN þ 3ÞðN þ 2ÞðN þ 1Þ Z Z p −q ðd − 1Þ! rþ1 r I dr ∼ dP dqrþ1 … In Table II, we compare five values of Pcls in Eq. (G7), when Nr Sd prþ1 N ¼ 2; 3; …; 6, with those for unknown distributions P and Z p −q d−1 d−2 Q given by Eq. (F13). As expected, the success probability × dqd−1 ð1 þ pr ÞNþr ; ðG9Þ pd−1 is larger if P and Q are known. The source of the increase is where we recall that the volume of the simplex Sd is TABLE II. The success probability Pcls for d ¼ 3 and data string V d ¼ 1=ðd − 1Þ!. For the remaining integrals over qs in lengths N ¼ 2; …; 6 in the cases of known and unknown Eq. (G9), we can take the lower limits to be ps ≈ 0, for distributions P and Q. For unknown distributions, the values s ≥ r þ 1, since the integrand is maximized by pr ≈ 1. are computed using Eq. (F13) in Appendix F. For known Therefore, Pd−2 the upper limits become 1, 1 − qrþ1 ; …; 1− distributions, the values are given by Eq. (G7). The table shows that knowing P and Q increases the success probability of s¼rþ1 qs . We identify these upper and lower limits as clustering. those of an integral over a ðd − r − 1Þ-dimensional proba- bility simplex Sd−r . We can thus write N 2 3 4 5 6 Z Unknown: 7=12 11=30 0.250 0.176 0.130 ðd − 1Þ! I dr ∼ dPð1 þ pr ÞNþr : ðG10Þ Known: 3=5 2=5 0.283 0.210 0.160 ðd − r − 1Þ!N r Sd 041029-20 UNSUPERVISED CLASSIFICATION OF QUANTUM DATA PHYS. REV. X 9, 041029 (2019) The last equation can be cast as [8] V. Dunjko and H. J. Briegel, Machine Learning & Artificial Intelligence in the Quantum Domain: A Review of Recent Z  X Nþr Progress, Rep. Prog. Phys. 81, 074001 (2018). ðd − 1Þ! d−1 I dr ∼ dP 2 − ps ; ðG11Þ [9] M. Sasaki and A. Carlini, Quantum Learning and Universal ðd − r − 1Þ!N r Sd s¼r Quantum Matching Machine, Phys. Rev. A 66, 022303 P (2002). where we use again that pr ¼ 1 − ds¼rþ1 ps and note that [10] N. Liu and P. Rebentrost, Quantum Machine Learning for under the integral sign we are free R to relabel the variables ps . Quantum Anomaly Detection, Phys. Rev. A 97, 042315 According to the definition of sd dP, we need to perform (2018). d − r integrals over the variables pr , prþ1 ; …; pd−1 , for [11] M. Skotiniotis, R. Hotz, J. Calsamiglia, and R. Muñoz- Tapia, Identification of Malfunctioning Quantum Devices, which we can use Eq. (G8), which yields a factor arXiv:1808.02729. 2Nþd =N d−r . The remaining integrals over p1 ; p2 ; …; pr−1 [12] A. Bisio, G. Chiribella, G. M. D’Ariano, S. Facchini, and of this constant factor give an additional 1=ðr − 1Þ!, as P. Perinotti, Optimal Quantum Learning of a Unitary they effectively correspond to an integral over a (r − 1)- Transformation, Phys. Rev. A 81, 032324 (2010). dimensional simplex. Putting the different pieces together, [13] A. Bisio, G. M. D’Ariano, P. Perinotti, and M. Sedlák, the asymptotic expression of I dr reads Quantum Learning Algorithms for Quantum Measurements, Phys. Lett. A 375, 3425 (2011). 2Nþd ½ðd − 1Þ!2 [14] M. Guta and W. Kotlowski, Quantum Learning: Asymp- I dr ≃ : ðG12Þ totically Optimal Classification of Qubit States, New J. N ðr − 1Þ!ðd − r − 1Þ! d Phys. 12, 123032 (2010). [15] G. Sentís, J. Calsamiglia, R. Muñoz-Tapia, and E. Bagan, We are now in a position to compute the asymptotic Quantum Learning without Quantum Memory, Sci. Rep. 2, success probability. Inserting Eq. (G12) into Eq. (G5), we 708 (2012). readily obtain [16] G. Sentís, M. Guta, and G. Adesso, Quantum Learning of  d d−1   X  Coherent States, EPJ Quantum Techno. 2, 17 (2015). 2 d d−2 [17] M. Fanizza, A. Mari, and V. Giovannetti, Optimal Universal Pcls ∼ ðd − 1Þ!ðd − 1Þ N r¼1 r d−r−1 Learning Machines for Quantum State Discrimination,  d IEEE Trans. Inf. Theory 65, 5931 (2019). 2 ð2d − 2Þ! [18] T. Hastie, R. Tibshirani, J. Friedman, and J. Franklin, The ¼ ; ðG13Þ N ðd − 2Þ! Elements of Statistical Learning: Data Mining, Inference, and Prediction, Math. Intell. 27, 83 (2005). where [19] L. Devroye, L. Györfi, and G. Lugosi, A Probabilistic P a bwe use the well-known binomial identity Theory of Pattern Recognition (Springer, New York, 1996). ð Þð k k s−k Þ ¼ ðaþb s Þ [here, k ranges over all values for [20] A. Monràs, G. Sentís, and P. Wittek, Inductive Supervised which the binomials make sense]. Equation (G13) coin- Quantum Learning, Phys. Rev. Lett. 118, 190503 (2017). cides with the asymptotic expression in the unknown case [21] V. Dunjko, J. M. Taylor, and H. J. Briegel, Quantum- Eq. (9), as we anticipated. Enhanced Machine Learning, Phys. Rev. Lett. 117, 130501 (2016). [22] D. Aloise, A. Deshpande, P. Hansen, and P. Popat, NP-Hardness of Euclidean Sum-of-Squares Clustering, [1] P. W. Shor, Fault-Tolerant Quantum Computation, in Mach. Learn. 75, 245 (2009). Proceedings of the 37th Conference on Foundations of [23] S. Ben-David, Clustering is Easy When....What?, arXiv: Computer Science (IEEE, New York, 1996), pp. 56–65. 1510.05336. [2] L. K. Grover, Quantum Mechanics Helps in Searching [24] V. Bužek, M. Hillery, M. Ziman, and M. Roško, Program- for a Needle in a Haystack, Phys. Rev. Lett. 79, 325 mable Quantum Processors, Quantum Inf. Process. 5, 313 (1997). (2006). [3] A. B. Finnila, M. A. Gomez, C. Sebenik, C. Stenson, [25] C. W. Helstrom, Quantum Detection and Estimation Theory and J. D. Doll, Quantum Annealing: A New Method for (Academic, New York, 1976). Minimizing Multidimensional Functions, Chem. Phys. Lett. [26] S. M. Barnett, Minimum-Error Discrimination between Multi- 219, 343 (1994). ply Symmetric States, Phys. Rev. A 64, 030303(R) (2001). [4] T. Kadowaki and H. Nishimori, Quantum Annealing in the [27] G. Chiribella, G. M. D’Ariano, P. Perinotti, and M. F. Transverse Ising Model, Phys. Rev. E 58, 5355 (1998). Sacchi, Covariant Quantum Measurements That Maximize [5] S. Lloyd, Universal Quantum Simulators, Science 273, the Likelihood, Phys. Rev. A 70, 062105 (2004). 1073 (1996). [28] G. Chiribella, G. M. D’Ariano, P. Perinotti, and M. F. [6] H. J. Kimble, The Quantum Internet, Nature (London) 453, Sacchi, Maximum Likelihood Estimation for a Group of 1023 (2008). Physical Transformations, Int. J. Quantum. Inform. 04, 453 [7] S. Wehner, D. Elkouss, and R. Hanson, Quantum Internet: (2006). A Vision for the Road Ahead, Science 362, eaam9288 [29] K. M. R. Audenaert, J. Calsamiglia, R. Munoz-Tapia, (2018). E. Bagan, Ll. Masanes, A. Acin, and F. Verstraete, 041029-21 GAEL SENTÍS et al. PHYS. REV. X 9, 041029 (2019) Discriminating States: The Quantum Chernoff Bound, [47] G. Sentís, J. Calsamiglia, and R. Muñoz-Tapia, Exact Phys. Rev. Lett. 98, 160501 (2007). Identification of a Quantum Change Point, Phys. Rev. Lett. [30] H. Krovi, S. Guha, Z. Dutton, and M. P. da Silva, Optimal 119, 140506 (2017). Measurements for Symmetric Quantum States with Appli- [48] J. Von Korff and J. Kempe, Quantum Advantage in Trans- cations to Optical Communication, Phys. Rev. A 92, mitting a Permutation, Phys. Rev. Lett. 93, 260502 (2004). 062333 (2015). [49] M. Hillery, E. Andersson, S. M. Barnett, and D. Oi, [31] D. E. Knuth, Sorting and Searching, The Art of Computer Decision Problems with Quantum Black Boxes, J. Mod. Programming Vol. 3 (Addison-Wesley, Reading, MA, Opt. 57, 244 (2010). 1998). [50] E. Aïmeur, G. Brassard, and S. Gambs, Quantum Speed-Up [32] M. Abramowitz and I. A. Stegun, Handbook of Mathemati- for Unsupervised Learning, Mach. Learn. 90, 261 (2013). cal Functions: with Formulas, Graphs, and Mathematical [51] S. Lloyd, M. Mohseni, and P. Rebentrost, Quantum Algo- Tables (Dover, New York, 1965). rithms for Supervised and Unsupervised Machine Learning, [33] R. E. Korf, A Complete Anytime Algorithm for Number arXiv:1307.0411. Partitioning, Artif. Intell. 106, 181 (1998). [52] N. Wiebe, A. Kapoor, and K. Svore, Quantum Algorithms [34] A. S. Holevo, Probabilistic and Statistical Aspects of for Nearest-Neighbor Methods for Supervised and Unsu- Quantum Theory (North-Holland, Amsterdam, 1982). pervised Learning, Quantum Inf. Comput. 15, 0318 (2015). [35] A. S. Holevo, Statistical Decision Theory for Quantum [53] I. Kerenidis, J. Landman, A. Luongo, and A. Prakash, Systems, J. Multivariate Anal. 3, 337 (1973). q-Means: A Quantum Algorithm for Unsupervised Machine [36] H. Yuen, R. Kennedy, and M. Lax, Optimum Testing of Learning, arXiv:1812.03584. Multiple Hypotheses in Quantum Detection Theory, IEEE [54] V. Giovannetti, S. Lloyd, and L. Maccone, Quantum Trans. Inf. Theory 21, 125 (1975). Random Access Memory, Phys. Rev. Lett. 100, 160501 [37] N. D. Pozza and G. Pierobon, Optimality of Square- (2008). Root Measurements in Quantum State Discrimination, [55] G. Chiribella and D. Ebler, Quantum Speedup in the Phys. Rev. A 91, 042334 (2015). Identification of Cause-Effect Relations, Nat. Commun. [38] G. Sentís, E. Bagan, J. Calsamiglia, G. Chiribella, and R. 10, 1472 (2019). Muńoz-Tapia, Quantum Change Point, Phys. Rev. Lett. [56] P. Flajolet and R. Sedgewick, Analytic Combinatorics 117, 150502 (2016). (Cambridge University Press, Cambridge, England, 2009). [39] R. A. Horn and C. R. Johnson, Matrix Analysis, 2nd ed. [57] G. E. Andrews, The Theory of Partitions, Encyclopedia of (Cambridge University Press, Cambridge, England, 2013). Mathematics and Its Applications Vol. 2 (Addison-Wesley, [40] I. D. Ivanovic, How to Differentiate between Non-Orthogonal Reading, MA, 1976). States, Phys. Lett. A 123, 257 (1987). [58] B. E. Sagan, The Symmetric Group—Representations, Com- [41] D. Dieks, Overlap and Distinguishability of Quantum binatorial Algorithms, and Symmetric Functions (Springer, States, Phys. Lett. A 126, 303 (1988). New York, 2001). [42] A. Peres, How to Differentiate between Non-Orthogonal [59] R. Goodman and N. R. Wallach, in Symmetry, Representa- States, Phys. Lett. A 128, 19 (1988). tions, and Invariants, edited by S. Axler and K. A. Ribet, [43] A. Chefles and S. M. Barnett, Optimum Unambiguous Graduate Texts in Mathematics Vol. 255 (Springer, Discrimination between Linearly Independent Symmetric New York, 2009). States, Phys. Lett. A 250, 223 (1998). [60] S. Gliske, W. H. Klink, and T. Ton-That, Algorithms [44] S. Lloyd, Least Squares Quantization in PCM, IEEE Trans. for Computing Generalized U(N) Racah Coefficients, Acta Inf. Theory 28, 129 (1982). Appl. Math. 88, 229 (2005). [45] A. W. Harrow, Applications of Coherent Classical Commu- [61] N. I. Akhiezer and N. Kemmer, The Classical Moment nication and the Schur Transform to Quantum Information Problem: And Some Related Questions in Analysis (Oliver Theory, Ph.D. thesis, Massachusetts Institute of Technology, and Boyd, Edinburgh, 1965), Vol. 5. 2005. [62] L. Alonso and T. Gorin, Joint Probability Distributions [46] H. Krovi, An Efficient High Dimensional Quantum Schur for Projection Probabilities of Random Orthonormal States, Transform, Quantum 3, 122 (2019). J. Phys. A 49, 145004 (2016). 041029-22