{'fraction_non_alphanumeric': 0.05627552296024669, 'fraction_numerical': 0.008167347278939911, 'mean_word_length': 3.957343524065276, 'pattern_counts': {'":': 0, '<': 27, '<?xml version=': 0, '>': 22, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Universal entanglement concentration

We propose a new protocol of \textit{universal} entanglement concentration, which converts many copies of an \textit{unknown} pure state to an \textit{% exact} maximally entangled state. The yield of the protocol, which is outputted as a classical information, is probabilistic, and achives the entropy rate with high probability, just as non-universal entanglement concentration protocols do. Our protocol is optimal among all similar protocols in terms of wide varieties of measures either up to higher orders or non-asymptotically, depending on the choice of the measure. The key of the proof of optimality is the following fact, which is a consequence of the symmetry-based construction of the protocol: For any invariant measures, optimal protocols are found out in modifications of the protocol only in its classical output, or the claim on the product. We also observe that the classical part of the output of the protocol gives a natural estimate of the entropy of entanglement, and prove that that estimate achieves the better asymptotic performance than any other (potentially global) measurements.


I. INTRODUCTION
Conversion of a given partially entangled state to a maximally entangled state by local operation and classical communication (LOCC) is an important task in quantum information processing, both in application and theory. If the given state is a pure state, such protocols are called entanglement concentration, while mixed state versions are called entanglement distillation.
In the paper, we study universal entanglement concentration, or entanglement concentration protocols which take unknown states as input, and discuss the optimal yield in higher order asymptotic theory, or in non-asymptotic theory, depending on the settings.
The reason why we studied universal entanglement concentration rather than universal entanglement distillation is to study optimal yield in detail, in comparison with non-universal protocols, which had been studied in detail [6,12,15,18,19]. Note that study of the optimal entanglement distillation is under development even in non-universal settings. For example, the known formula for the optimal first order rate still includes optimization over LOCC in one-copy space. This is sharp contrast with the study of entanglement concentration, for which non-asymptotic and higher order asymptotic formula in various form are obtained.
As demonstrated by Bennett et al. [3], if many copies of known pure states are given, the optimal asymptotic yield equals the entropy of entanglement of the input state [18]. To achieve the optimal, both parties apply projections onto the typical subspaces of the reduced density matrix of given partially entangled pairs (BBPS protocol, hereafter). Obviously, the protocol is not applicable to the case where information about Schmidt basis is unknown. Of course, one can estimate necessary information by measuring some of the given copies. In such protocol, however, the final state is not quite a maximally entangled state, because errors in estimation of the Schmidt basis will cause distortions. This paper proposes a protocol, denoted by {C n * }, of universal distortion-free entanglement concentration, in which exact (not approximate) entangled states are produced out of identically prepared copies of an unknown pure state. Its yield is probabilistic(, so users cannot predict the yield beforehand), but the protocol outputs the amount of the yield as classical information, ( so that users know what they have obtained, ) and the rate of the yield asymptotically achieves the entropy of entanglement with probability close to unity.
A key to construction of our protocol is symmetry; an ensemble of identically prepared copies of a state is left unchanged by simultaneous reordering of copies at each site. This symmetry gives rise to entanglement which is accessible without any information about the Schmidt basis.
In some applications, small distortion in outputs might be enough, and estimation-based protocols might suffice, because entropy rate is achieved anyway. In higher order asymptotic terms and non-asymptotic evaluations, however, we will prove that our protocol is better than any other protocols which may allow small distortion.
In the proof, the following observation simplifies the problem to large extent. Let us concentrate on the optimization of the worst-case quantity of performance measures over all the unknown Schmidt basis, because the uncertainty about Schmidt basis is the main difficulty of universal entanglement concentration. We also assume performance measures are not increasing by postprocessing which decreases the Schmidt rank of the product maximally entangled state.
With such reasonable restrictions, an optimal protocol is always found out in a class of protocols which are the same as {C n * } in output quantum states, but may differ in classical output. Therefore, any trial of improvement of {C n * } cannot change real yield. What can be 'improved' is the information about how much yield was produced. For {C n * } outputs the information about yield correctly, there should be no room for 'improvement' in this part, too. This observation assures us that {C n * } is optimal if the criterion is fair. In addition, the optimization is now straightforward, for we have to optimize only classical part of the protocol.
Based on this observation, we prove the optimality in terms of a natural class of measures: monotone increasing measures which are bounded over the range and continuously differentiable except at finitely many points. In terms of such measures, distortion-free condition trivially implies the non-asymptotic optimality of our protocol, while the constraint on the distortion implies that our protocol is optimal up to the higher orders. Also, (a kind of ) nonasymptotic optimality is proved for some performance measures which varies with both yield and distortion. These results assure us that our protocol {C n * } is the best universal entanglement concentration protocol. Here, we stress that most of these results generalize to the case where Schmidt coefficients of an input are known and its Schmidt basis is unknown.
In the end, we prove that the classical output of our protocol gives an asymptotically optimal estimate of entropy of entanglement. Surprisingly, this estimate is not less accurate than any other estimate based on (potentially global) measurement whose construction depends on the Schmidt basis of the unknown state.
Considering its optimal performance in very strong senses, it is surprising that our protocol does not use any classical communication at all.
The paper is organized as follows. After introducing symbols and terms in Section II, we describe implications of the permutation symmetry, and constructed the protocol {C n * } (Subsection III A). Its asymptotic performance is analyzed using known results of group representation theoretic type theory in Subsection III B, followed by comparison with a estimation based protocol III C.
Optimality of the protocol is discussed in Section IV. Subsection IV A gives definition of measures of performance and short description of proved assertions. The key lemma, which restricts the class of protocols of interest to large extent, is proved in Subsection IV B. Subsections IV C-IV G treats proof of optimality in each setting.
The estimation theoretic application of the protocol is discussed in Section V. Interestingly, a part of arguments in this section gives another proof of optimality of {C n * } in terms of error exponent. In the appendices, we demonstrated several technical lemmas and formulas. Among them, an asymptotic formula of average yield of non-universal entanglement concentration protocols is, so far as we know, had not shown, and might be useful for other applications.

Given an entangled pure state |φ ∈ H
we denote its Schmidt coefficients by p φ = (p 1,φ , . . . , p d,φ ) (p 1,φ ≥ p 2,φ ≥ . . . ≥ p d,φ ≥ 0) and its Schmidt basis by {|e φ i,x }, respectively. Entropy of entanglement of |φ equals the Shannon entropy H of the probability distribution p φ , where Shannon entropy H is defined by H(p) := i −p i log p i . (Throughout the paper, the base of log is 2.) In the paper, our main concern is concentration of maximal entanglement from |φ ⊗n by LOCC. We denote a maximally entangled state with the Schmidt rank L by where {|f n i,x } is an orthonormal basis in H ⊗n x (x = A, B). Note that {|f n i,x } need not to be explicitly defined, for the difference between 1 is compensated by a local unitary. One can optimally produce 2 nH(p φ ) from |φ ⊗n by LOCC with high probability and high fidelity, if n is very large [3,18].
In this paper, an entanglement concentration {C n } is a sequence of LOCC measurement, in which C n takes n copies |φ ⊗n of unknown state as its input. With probability Q φ C n (x), C n outputs ρ φ C n (x), which is meant to be an approximation to 2 nx , together with x as classical information.
The worst-case distortion ǫ φ C n is the maximum of square of the Bure's distance between the output ρ φ C n (x) and the target 2 nx , whileǭ φ C n denotes the average distortion, A protocol is said to be distortion -free, if ǫ φ C n = ǫ φ C n = 0 holds for all φ. In the construction of {C n * }, we exploit two kinds of symmetries. First, our input, |φ ⊗n , is invariant by the reordering of copies, or the action of the permutation σ in the set {1, . . . n} such that where |h i,x ∈ H x (x = A, B). (Hereafter, the totality of permutations in the set {1, ..., n} is denoted by S n .) Second, an action of local unitary transform U ⊗n ⊗V ⊗n (U, V ∈ SU(d)) corresponds to change of the Schmidt basis.
Action of these groups induces a decomposition of the tensored space H ⊗n where U n,x and V n,x is an irreducible space of the tensor representation of SU(d), and the representation (1) of the group of permutations respectively, and n = (n 1 , . . . , n d ), is called Young index, which U n,x and V n,x uniquely correspond to. In case of spin-1 2 -system, W n,x is an eigenspace of the total spin operator. Due to the invariance by the permutation (1), any n-tensored state |φ ⊗n is decomposed in the following form.
where, |φ n is a state vector in U n,A ⊗ U n,B , a φ n is a complex number, and |V n is a maximally entangled state in V n,A ⊗ V n,B with the Schmidt rank dim V n,A . While |φ n and a φ n depends on the input |φ , |V n does not depend on the input.

Proof
Write is a complete orthonormal basis in U n,A , V n,A , U n,B , V n,B , respectively. Establish a correspondence between a vector |φ ⊗n in bipartite system and an operator Φ n := n,n ′ i,j,k,l b n,i,j,n ′ ,k,l e Un For this map is one to one, we study Φ n in stead of |φ ⊗n .
Observe that Φ n is invariant by action of any permutation σ, where the action of σ is defined by (III A). Due to Lemma 14, b n,i,j,n ′ ,k,l = 0 unless n = n ′ , and Φ n = n i,j,k,l b n,i,j,n,k,l e Un proving that Φ n is of the form where Φ n is a linear map in U n . To obtain the lemma, we simply take "partial transpose" of this again: apply the linear map which maps e Un For this map is one to one, Φ n is mapped to |φ ⊗n . By this map, e Vn j e Vn j is mapped to |V n , and Φ n is mapped to This lemma implies that there are maximally entangled states, |V n , which are accessible without using knowledge on the input state. The average amount of the accessible entanglement is decided by the coefficients a φ n , which vary with the Schmidt coefficients of the input |φ . Now we are at the position to present our universal distortion-free entanglement concentration protocol {C n * } (Hereafter, the projection onto a Hilbert space X is also denoted by X ): First, each party apply the projection measurements {W nA,A } nA and {W nB,B } nB at each site independently. This yields the same measurement result n A = n B = n at both site, and the state is changed to |φ n ⊗ |V n . Taking partial trace over U n,A and U n,B at each site, we obtain |V n .
If H A and H B are qubit systems, {W nA,A } nA is nothing but the measurement of the total angular momentum. For the sake of the formalism, |V n is mapped to dim V n . With this modification, ρ φ C n * (x) = 2 nx 2 nx and Q φ C n * (x) = a φ n , if 2 nx = dim V n (if such n does not exist, Q φ C n * (x) = 0). Due to the identity Q φ C n * log dim Vn n = a φ n = Tr W n,A (Tr B |φ φ|) ⊗n and the formulas in the appendix of [8], we can evaluate the asymptotic behavior of Q φ C n * (x) as follows: where R is an arbitrary closed subset of {q|q 1 ≥ q 2 ≥ . . . ≥ q d ≥ 0, In this subsection, we analyze the asymptotic performance of {C n * } in terms of success (failure) probability, total fidelity, and average of the log of Schmidt rank of the output maximally entangled states. (The proof of the optimality of {C n * } is made for more general class of measures). For the main difficulty of universal concentration is attributed to uncertainty about Schmidt basis, we consider the value in the worst-case Schmidt basis.
The worst-case value for the failure probability, or the probability that the yield is not more than y equals max U,V x:x≤y where U and V run all over unitary matrices. For the yield of our protocol {C n * } is invariant by local unitary operations, the maximum over U and V can be removed. Due to the first and the third formula in (3), we have, and lim n→∞ −1 n log Eq. (5) implies that our protocol achieves entropy rate: if R is strictly smaller than H(p φ ), the RHS of Eq. (5) is positive, which means that the failure probability is exponentially small. On the other hand, Eq. (6) means that the probability to have the yield more than the optimal rate (strong converse probability) tends to vanish, and its convergence is exponentially fast.
Next, we evaluate the exponent of the total fidelity F φ C n (R), or the average fidelity to the maximally entangled state whose Schmidt rank is not smaller than 2 nR : (The optimization is considered in the worst-case Schmidt basis.) This function describes trade-off between yield and distortion. Obviously, F φ C n (R) is non-increasing in R, and takes larger value if the protocol is better. We evaluate this quantity for {C n * } as follows.
The RHS is upper-bounded by x:x<R Q φ C n * (x) and lower-bounded by The exponent of failure probability, strong converse probability, and total fidelity for the optimal non-universal protocol are found out in [15], and we can observe the non-zero gap between the exponents of {C n * } and the optimal non-universal protocol. By contrast, these quantities for BBPS protocol coincides with the ones for {C n * }. (Proof is straightforwardly done using the classical type theory).
This fact may imply that the protocol {C n * } is so well-designed that its performance is comparable with the one which uses some information about the input state. However, it might be the case that these quantities are not sensitive to difference in performance. Hence, we also discuss another quantity, the average yield (, evaluated at the worst-case Schmidt basis), The average yield of BBPS protocol is of the form where the coefficients A, B and their derivation are described in Appendix B. The average yield of the protocol {C n * } is less than that of BBPS protocol by C n , where C is calculated in Appendix C. Hence, this measure is sensitive to the difference in performance which do not reveal in the exponent of failure probability etc.

C. Comparison with estimation based protocols
Most straightforwardly, universal entanglement concentration is constructed based on the state estimation; First, c n copies of |φ are used to estimate the Schmidt basis, and second, apply BBPS protocol to the n − c n copies of |φ . The average yield of such protocol cannot be better than where c n slowly grows as n increases. Therefore, this estimation-based protocol cannot be better than {C n * }, because the average yield of {C n * } and BBPS protocol are the same except for O 1 n -terms. One might improve the estimation-based protocol by replacing BBPS protocol with the non-asymptotically optimal entanglement concentration protocol. However, this improvement is not likely to be effective, because in qubit case, the yield of these protocols are the same up to the order of O log n n (Appendix D, O 1 n -term is also given). Another alternative is to use precise measurements which cause only negligible distortion, so that we can use all the given copies of an unknown state for entanglement concentration. This protocol can be very good, and there might be many other good protocols. As is proven in the next section, however, none of these protocols is no better than {C n * }, i.e., {C n * } is optimal for all protocols whose outputs are slightly distorted.

A. Measures, settings, and summary of results
A performance of an entanglement concentration has two parts. One is amount of yield, and the other is distortion of the output. The measures of the latter are, as is explained in Section II, ǫ φ C n and ǫ φ C n . Hereafter, maximum of these quantities over all Schmidt basises ( max U, The measures of the yield (4), (8) discussed in the previous section are essentially of the form So far, we had considered minimization for error probability, and maximization for average yield. Hereafter, we use success probability with Θ(x) denoting the step function, instead of error probability (4). From here to the end, optimization of an yield measure (9) means maximization of (9).
Namely, minimization of (4) corresponds to maximization of (9) with f (x) = Θ(x − R). Also, maximization of (8) is equivalent to maximization of (9) with f (x) = x log d . These examples are monotone and bounded, or and continuously differentiable but finitely many points.
The condition (10) and (11) are assumed throughout the paper unless otherwise mentioned. In the following subsections, measures of the form (9) are optimized with the restriction on the worst-case distortion Also, we consider the optimization (maximization) of the measures which vary with both yield and distortion. Namely, the weighted sum of these yield measure and the average distortion ǫ φ C n , i.e., and the total fidelity max U,V F U⊗V φ C n (R) are considered. We prove that the protocol is optimal, in the following senses.
2. Non-asymptotic behavior is best among all distortion-free protocols (Subsection IV C).
3. Higher order asymptotic behavior is best for all protocols which allows small distortions (Subsections IV D, IV E).
4. In terms of weighed sum measures (13) and the total fidelity, the non-asymptotic optimality holds (Subsections IV F-IV G).
The key to the proof of these assertions is Lemma 3 which will be proved in the next section. Due to this lemma, we can focus on the protocols which is a modification of {C n * } in its classical outputs only. This fact not only simplifies the argument but also assures us that {C n * } is a very natural protocol. Here, we note that many of our results in this section generalize to the case where Schmidt basis is unknown and Schmidt coefficients are known. Such generalization is possible if the optimization problem can be recasted only in terms of a family of quantum states {U ⊗ V φ} UV , where |φ is a given input state and U and V run all over SU(d). This is trivially the case when we optimize a function of distortion and yield. This is also the case if conditions on distortion are needed to be imposed only on the given input state, and not on all the possible input states.

B. The Key Lemma
In this subsection, we prove Lemma 3, which is the key to the arguments in the rest of the paper. To make analysis easier, before the protocol starts, each party applies U ⊗n , V ⊗n at each site, where U and V are chosen randomly according to Haar measure in SU(d), and erase the memory of U, V . This operation is denoted by O1, hereafter.
From here to the end of the paper, C n * means the composition of O1 followed by C n * . The optimality of the newly defined {C n * } trivially implies the optimality of {C n * } defined previously, because O1 simply randomizes output and cannot improve the performance; where E U,V denotes expectation by Haar measure in SU(d). (More explicitly, where µ is the Haar measure with the convention µ(dU ) = 1.) Lemma 17 implies that U n,A ⊗U n,B is an irreducible space of the tensored representation U ⊗n ⊗V ⊗n of SU(d)×SU(d). Hence, by virtue of Lemmas 14-15, the average state writes and We denote by O2 the projection measurement {W nA,A ⊗ W nB ,B } nA,nB , which maps the state ρ to the pair Here note that, due to the form of σ φ n , n A = n B := n, so long as the input is many copies of a pure state. Given a pair n, σ φ n of classical information and a state supported on W n,A ⊗ W n,B , the operation O3 outputs n, tr Un,A⊗Un,B σ φ n . Denoting the composition of an operation A followed by an operation B as B •A, C n * writes O3•O2•O1, essentially. (The mapping from |V n to || dim V n is needed only for the sake of formality.) Here, in defining B • A, if A's output is a pair (n, ρ n ) of classical information and quantum state, we always consider the correspondence where {|n } is an orthonormal basis, and U x is an local isometry to appropriately defined Hilbert space. Here, 'local' is in terms of A-B partition. In terms of this convention, the definition of O3 rewrites using local isometry U n and U ′ n . (The domain of U n and U ′ n is W n,A ⊗ W n,B and V n,A ⊗ V n,B , respectively.) Recall that all the measures listed in the previous section are invariant by local unitary operations to the input, i.e., the measure f n (ρ, {C n }) satisfies and is affine with respect to ρ, Recall also that the worst-case/average distortion are affine. Hereafter, the worst-case/average distortion are always evaluated at the worst-case Schmidt basis, so that those measures satisfy (17).
Lemma 2 For any given protocol {C n }, we can find a protocol such that; (i) The protocol is of the form {B n • C n * }, where B n is an LOCC operation; (ii) A performance measure satisfying (17) and (18)takes the same value as the protocol {C n }, Proof Due to (17) and (18), the operation O1 does not decrease the measure of the performance, because Hence, {C n • O1} is the same as {C n } in the performance. After the operation O1, the state is block diagonal in subspaces {W n,A ⊗ W n,B }. Therefore, if we use the correspondence (15), the state is not unchanged by O2 (up to local isometry). More explicitly, let U n be a local isometry in (16), and C ′n = C n • U † n . Then, we have Observe also that, after the operation O1, parts of the state which are supported on U n,A ⊗ U n,B are tensor product states. Hence, there is a operation B n such that because tensor product states can be reproduced locally whenever they are needed. More explicitly, where U n and U ′ n are local isometry in (16). After all,f (ρ, {B n • C n * }) = f (ρ, {C n }) and the lemma is proved. ✷ In the postprocessing B n , a classical output x will be changed to x+∆ with probability Q n (x + ∆|x), accompanying some SLOCC operations on the quantum output. In the following lemma, for a given Q n (y|x), Q n (y|x) is a transition matrix such that Q n (y|x) = Q n (y|x) for y > x and Q n (y|x) = 0 for y < x, and Q n (x|x) := Q n (x|x) + y<x Q n (y|x).  Proof The condition (a) follows from Lemma 2, for worst-case/average distortion, (9), and total fidelity (7) because they satisfy (17) and (18).
where Q n (y|x) is a transition matrix such that Q n (y|x) = Q n (y|x) for y > x and Q n (y|x) = 0 for y < x, and Q n (x|x) := Q n (x|x)+ y<x Q n (y|x). Hence, Q n (y|x) improves Q n (y|x) in average yield (9), while worst-case/average distortion is unchanged as is proved later. Therefore, (b) applies to (i) and (ii).
To go on further, we have to find out optimal state transition made by the postprocessing. When the postprocessing B n changes classical output x to y, the corresponding quantum output ρ φ B n (y|x) which minimize the distortion i.e., maximizes the fidelity to 2 ny is for the reasons stated shortly. In case the y ≤ x, LOCC can change the output of C n * , ||2 nx , to 2 ny perfectly and deterministically. On the other hand, in case y > x, monotonicity of Schmidt rank by SLOCC implies that 2 nx is the best approximate state to 2 ny in all the states which can be reached from 2 nx with non-zero probability. This transition causes the distortion of 1 − 2 −n(y−x) .
From (19), it is easily understood that worst-case/average distortion of Q n (y|x) equals that of Q n (y|x), and that the condition (c) applies to (i) and (ii). It remains to prove (b) and (c) for (iii). Observe that total fidelity (7) does not depend on the classical output of the protocol. Therefore, condition (b) is not restriction in optimization. Therefore, we only prove (c). By definition, which is maximal. In x < R case, for any z ≥ R(> x), the maximum of 2 nz ||ρ φ B n (y|x) 2 nz is achieved by ρ φ B n (y|x) = 2 nx 2 nx ||, because monotonicity of Schmidt rank by SLOCC implies that 2 nx is the best approximate state to 2 nz in all the states which can be reached from 2 nx with non-zero probability. Therefore, the optimal output state should be as is described in (c). ✷ Now, the protocol of interest is very much restricted. We modify classical output of C n * according to transition probability Q n (y|x), while its quantum output is untouched. Note Q n (y|x) is non-zero only if y ≥ x. Especially, transition to y strictly larger than x means that the protocol claims the yield y while in fact its yield is x < y. In other words, this is excessive claim on its yield.
Main part of our effort in the following is how to suppress 'excessive claim', or Q n (y|x) for y > x by setting appropriate measure or constraint.
Note that the mathematical treatment is much simplified now, for we only have to optimize transition probability Q n (y|x), with the condition that the distortion 1 − 2 −n(y−x) occurs only if y ≥ x.
Observe that in the proof of these lemmas, we have used the uncertainty about Schmidt basis. This assumption is needed to justify the condition (17). However, the uncertainty about Schmidt coefficients has played no role. Therefore, Lemma 2-3 holds true even in the case where Schmidt coefficients are known.
Hereafter, maximization/minimization over local unitaries will be often removed, because the protocols of our interest are local unitary invariant.

C. Distortion-free protocols
Theorem 4 {C n * } achieves the optimal (maximal) value of (9) for all universal distortion-free concentrations for all finite n, any input state |φ , and any threshold R. Here, f only need to be monotone increasing, and need not to be bounded nor continuous.
Proof Lemma 3 apply to this case, for distortion-free condition writes, using the invariant measure of a distortion, max U,V ǫ U⊗V φ C n = 0. To increase the value of (9), Q n (x + ∆|x) should be non-zero for some x, ∆ with ∆ > 0, which causes non-zero distortion. Hence, it is impossible to improve the yield measure (9) by postprocessing. ✷ Observe that the proof also applies to the case where Schmidt coefficients are known, for the condition max U,V ǫ U⊗V φ C n = 0 assertion is needed to be imposed only on the input state.

D. Constraints on the worst-case distortion
In this subsection, we discuss the higher order asymptotic optimality of {C n * } in terms of the average yield (9) under the constraint on the worst-case distortion, This means that the magnitude of the improvement in the yield is uniformly upper-bounded by − log(1−rn) n . Ineq. (20) is the key to the rest of the argument in this subsection.
In discussing the average yield (9), we assume f (x) is continuously differentiable at around x = H (p φ ). In addition, first we assume f ′ (H (p φ )) > 0. After that, we study the case where f ′ (x) = 0 in the neighborhood of x =.H (p φ ). A typical example of the former and the latter is f (x) = x log d and f (x) = Θ(x − R), respectively. Note that the argument in this section holds true also for the cases where Schmidt coefficients are known. This is because the constraint max U,V ǫ U⊗V φ C n ≤ r n is needed to be imposed only on a given input state, and not on all the state.
Theorem 5 Suppose that f is continuously differentiable in a region (R 1 , R 2 ) with R 1 < H (p φ ) < R 2 , and r n is smaller than 1 − δ with δ being a positive constant, and r n is not exponentially small. Then, (i) {C n * } is optimal in the order which is slightly larger than O rn n , or for any protocol {C n }, (ii) if f ′ (H (p φ )) > 0, there is a protocol {C n } which is better than {C n * } by the magnitude of O rn n for an input |ψ , or Applied to f (x) = x log d , (i) and (ii) imply that with the constraint max U,V ǫ U⊗V φ C n → 0, {C n * } is optimal up to O 1 n -terms, and not optimal in the order smaller than that. Hence, the coefficients computed in Appendix D are optimal. Proof (i) Obviously, the optimal protocol {C n } is given by In the region (R 1 , R 2 ), with c := max x:R1≤x≤R2 f ′ (x), holds. For the function − log(1 − x) is monotone and concave, if r n < 1 − δ, we have The average of the both sides of this over x yields for the sum over the complement of (R 1 , R 2 ) is exponentially small due to the third equation of (3). This implies the optimality of our protocol.
(ii) Due to mean value theorem, holds in a neighborhood of x = H (p φ ). Hence, letting {C n } be the protocol corresponding to (21), we have proving the achievability. ✷ In case of f (x) = Θ(x − R), which is flat at around x = H (p φ ), (ii) of this theorem does not apply, and as is shown below, the upper-bound to the average yield suggested by (i) is not tight at all.
and the equality is achieved by {C n * }.
This theorem intuitively means that, if f (x) is flat at the neighborhood of x = H (p φ ), for the optimal protocol, the quantity (9) is approximately of the form, Applied to f (x) = Θ(x − R), the theorem implies the optimality of (5) and (6) under the constraint lim n→∞ max U,V ǫ U⊗V φ C n < 1. Proof Suppose H (p φ ) > R 1 . For any R < R 1 , where the second inequality is due to monotonicity of f . On the other hand, (20) implies Combination of these inequalities with (5) leads to lim n→∞ −1 n log which, letting R → R 1 , leads to the first inequality. On the other hand, in H (p φ ) < R 2 case, the monotonicity of f and (20) also implies Combination of this with (6) leads to the second inequality. The achievability is proved as follows. Suppose H (p φ ) > R 1 . For x smaller than R 1 , Hence, the exponent is lower bounded by which means the first inequality is achieved. Suppose H (p φ ) < R 2 . For x larger than R 2 , then we have where R 0 is an arbitrary constant with R 0 > R 2 . Hence, the exponent is upper-bounded by Letting R 0 → R 1 , we have the achievability of the second inequality. ✷

E. Constraints on the average distortion
In this subsection, we discuss the higher-order asymptotic optimality of {C n * } in terms of the generalized average yield (9) under the constraint on the average distortion, Denote the probability that the improvement by the amount ∆ occurs by Observe that Hence, the magnitude of improvement is upper-bounded only in average sense, in contrast with (20) which implies an upper-bound uniform with respect to x. Suppose that f is continuously differentiable all over the region (0, log d). Then, the improvement x → x + ∆ causes the distortion by the amount of where, c = max x:0≤x≤1 f ′ (x) . Taking average of the both side, or, On the other hand, let the protocol {C n } be the one corresponding to Q n (log d|x) = r n , ∀x.
Then, we have while the average distortion of {C n } is at most r n . Now, we extend these arguments to the case where finitely many discontinuous points exist. First, in the proof of the upper-bound, it is sufficient for f to be continuously differentiable in the neighborhood of x = H (p φ ), if the exponentially small terms are neglected. Second, the evaluation of the performance of the protocol constructed above does not rely on the differentiability of f . Therefore, we have the following theorem.
Theorem 7 (i) Suppose that f is continuously differentiable in the neighborhood of x = H (p φ ). Suppose also r n is not exponentially small. Then, if ǫ φ C n ≤ r n ., {C n * } is optimal in terms of (9), up to the order which is slightly larger than O(r n ), or for any protocol {C n }, (ii) Suppose that f (H(p φ ) + c) < 1, ∃c > 0, and ǫ φ C n ≤ r n . Then, there is a protocol {C n } which improves {C n * } by the order of O(r n ); Let us compare this theorem with Theorem 5 which states optimality results with constraint on worst-case distortion. First, the yield is worse by the order of 1 n . In particular, if f (x) = x log d , r n needs to be o( log n n ) for optimality up to a higher order term is guaranteed. By contrast, under the constraint on the worst-case distortion, r n = o(1) is enough to certify optimality up to the third leading term.
Second, applied to the case of f (x) = Θ(x − R), H(p φ ) > R , Theorem 7 implies the following. With r n = o(1), the success probability x:x≥R Q φ C n (x) vanishes (strong converse holds), but the speed of convergence is at most as fast as r n , which is not exponentially fast, in general. Therefore, (6) is far from optimal unless r n decreases exponentially fast. By contrast, under the constraint on the worst-case distortion, a constant upper-bound is enough to guarantee the optimality of the exponent (6).
Let us study the equivalence of Theorem 6, because Theorem 7, (ii) cannot be applied to discussion of optimality of the exponent (5), in which the rate R is typically less than H(p φ ).

Lemma 8 Suppose that
holds for all |φ . Then, for all |φ , all c > 0, all δ > 0, and all R ′ , R ′′ with R ′ > R ′′ , there is a sequence {x n } such that R ′′ ≤ x n ≤ R ′ and Proof Assume the lemma is false, i.e., there is a sequence {n k } such that for all x in the interval (R ′′ , R ′ ), which, combined with (22), implies This cannot hold when n k is large enough. Therefore, the lemma has to be true. ✷ Theorem 9 Suppose that f (x) = 1 for x ≥ R, and H(p φ ) > R holds. Then, if lim n→∞ max U,V ǫ U⊗V φ C n < 1 holds for all |φ , and the equality is achieved by {C n * }.
Note the premise of the theorem is the negation of the premise of Theorem 7 , (ii). Note also that the constraint on the average distortion is very moderate, allowing constant distortion.
Proof First, we prove (23) for f (x) = Θ (x − R). Without loss of generality, we can assume that Q n (y|x) is non-zero only if y = R and x < R. Therefore Let R ′ , R ′′ be real numbers with R ′ < R ′′ < R, and {x n } be a sequence given by Lemma 8. Then we have, due to Lemma 8, For this holds true for all R ′′ < R ′ < R, the limit R ′′ → R leads to the inequality (23) for f (x) = Θ (x − R).
As for f which satisfies the premise of the theorem, we lower-bound 1 − f (x) by (1 − f (R 0 ))(1 − Θ(x − R 0 )), with R 0 < R. Then, the exponent is The limit R 0 → R leads to the inequality of the theorem. The achievability is proven in the same way as the proof of Theorem 5. ✷ Note the arguments in the proof of Theorem 7 apply also to the case where Schmidt coefficients are known. This is because the constraint max U,V ǫ U⊗V φ C n ≤ r n is required only for a given input state, and not for all the state. On the contrary, the proof of Theorem 9 is valid only if the constraint max U,V ǫ U⊗V φ C n ≤ r n is assumed for all |φ (otherwise, Lemma 8 cannot be proved), meaning the generalization to the case where Schmidt coefficients are known is impossible.

F. Weighted sum of the distortion and the yield
In this subsection, we discuss the weighted sum (13) of the distortion and the yield. First, we study the case where f is continuously differentiable over the domain, and then study the case where f is an arbitrary monotone nondecreasing, bounded function. In this section, we prove (a sort of) non-asymptotic optimality. Finally, we apply our result to induce another proof of Theorem 7. The argument in this subsection generalize to the case where Schmidt coefficients are known, as is explained toward the end of Subsection IV A.
To have a reasonable result, the wight λ cannot be too small nor too large. In this subsection, we assume because otherwise the yield f (x) can take the value larger than the maximum value of the distortion, which equals unity. No explicit upper-bound to λ is assumed, but λ is regarded as a constant only slightly larger than 1. Due to Lemma 3, the difference between the value of the measure (13) of {C n * } and the protocol characterized by Q n (x|y) is x,y: x≥y For {C n * }, or Q n (x|y) = 0 to be optimal, the coefficient for Q n (x|y) has to be non-positive, or, When n is large enough, the RHS of this approximately equals λΘ (x − y). Hence, this inequality holds, if n is larger than some threshold n 0 , for varieties of f 's. More rigorously, the condition for the optimality of {C n * } writes ∀x, y, 0 ≤ y < x ≤ log d.
Observe that − log(1 − x) is convex and monotone increasing, and − log(1 − 0) = 0. Hence, the RHS of (26) is upper-bounded by If the function f is continuously differentiable, the last side of the equation equals After all, we have the following theorem.
Theorem 10 If f satisfies (10)- (12), {C n * } is optimal, i,e., achieves maximum of (13) with the weight (24) for any input state, any n larger than the threshold n 0 , where . Some comments on the theorem are in order. First,this assertion is different from so called asymptotic optimality, in which the higher order terms are neglected. On the contrary, our assertion is more like non-asymptotic arguments, for we have proved that {C n * } is optimal up to arbitrary order if n is larger than some finite threshold. Second, the factor − log 1 − 1 λ is relatively small even if λ is very close to 1. For example, for λ = 1.001, − log 1 − 1 λ = 9.96 · · · . Hence, the threshold value is not so large. For example, if f (x) = x, n 0 = −1 log d log 1 − 1 λ = 9.96··· log d ≤ 10.
So far, λ has been a constant, but, let λ = 1 1−d −n , so that the range of f and the distortion coincide with each other. (Note 1 1−d −n is only slightly larger than 1.) Then, if f (x) = x log d , the condition for the optimality of {C n * } writes, which holds for all n ≥ 1, implying the non-asymptotic optimality. Now, let us study the case where f is not differentiable, such as f (x) = Θ(x − R). In such case, we see the condition (26) as a restriction on ∆ := x − y such that Q n (y + ∆|y) for the optimal protocol takes non-zero value for some y.
Observe that f (x) − f (y) ≤ 1 is true for all the function satisfying (11). Therefore, for Q n (y + ∆|y)'s for the optimal protocol vanish for all y. Hence, the improvement of {C n * } is possible only in the very small range of ∆, when n is very large.
Those analysis of the weighted sum measures can be applied to the proof of Theorem 7, (i). For this purpose, we use a Lagrangian such that with λ > 1, r n > 0. Observe that (9) cannot be larger than L under the condition max U,V ǫ U⊗V φ C n ≤ r n . For under this condition, the second term is positive, and the first term of L is nothing but (9). In case that f is differentiable, Theorem 10 implies that the maximum of L (λ > 1) is achieved by {C n * }. Therefore, for ǫ φ C n * = 0, we obtain the inequality, max (9) ≤ (9) for C n * + λr n .
The similar argument applies to the case where f is continuously differentiable only in the neighbor of x = H(p φ ), except for the exponentially small terms.
This measure equals fidelity between an output and a target, and relation between R and this quantity reflects the trade-off between yield and distortion. Note that the argument in this subsection also generalizes to the case where the Schmidt coefficients are known, as is explained toward the end of Subsection IV A.
Theorem 11 {C n * } achieves the optimal (maximum) value of total fidelity (7) in all the protocols, for any n, any input state |φ , and any threshold R.
Proof Due to Lemma 3, the protocol of interest is postprocessing of {C n * } which does not touch its quantum output. The total fidelity of such protocol equals that of {C n * }, for total fidelity (7) is not related to a classical output of the protocol. ✷

V. UNIVERSAL CONCENTRATION AS AN ESTIMATE OF ENTANGLEMENT
In this section, universal concentration is related to statistical estimation of entanglement measure H(p φ ). Observe thatĤ is a natural estimate of H(p φ ) when n ≫ 1. Letting f (x) = Θ(x − R), Theorem 7, (i) implies that the probability forĤ C n > H(p φ ) tends to vanish, if lim n→∞ ǫ φ C n < 1, as is demonstrated right after the statement of the theorem.
Therefore, if {C n } achieves the entropy rate, the estimateĤ C n converges to H(p φ ) in probability as n → ∞ (a consistent estimate). Especially, for the estimate H C n * which is based on {C n * }, the error exponent is given using (5) and (6) as, Now, we prove that this exponent is better than any other consistent estimate which potentially uses global measurements, if the Schmidt basis is unknown.
holds for any consistent estimateĤ n of H(p φ ) by global measurement, if the Schmidt basis is unknown.
Proof An argument almost parallel to the one in Subsection IV B implies that we can restrict ourselves to the estimate which is computed from the classical output of C n * . From here, we use the argument almost parallel with the one in [16]. For ǫ, |φ , |ψ with H(p ψ ) < H(p φ ) − δ, consistency of H n implies Pr φ H n < H(p φ ) − δ ( := p n ) → 0, On the other hand, monotonicity of relative entropy implies or, equivalently, . With the help of Eqs. (30), letting n → ∞ of the both sides of this inequality,.we obtain Bahadur-type inequality [2], LHS of (28) ≤ lim whose RHS equals D(p ψ p φ ), as in Appendix E. Therefore, choosing |ψ such that H(p ψ ) is infinitely close to R, If a protocol {C n } satisfies lim n→∞ ǫ φ C n < 1 and achieves the rate of the entropy of entanglement, as is mentioned at the beginning of this section, the corresponding estimateĤ C n is consistent, and satisfies Ineq. (28). This is equivalent to the optimality (23) with f (x) = Θ (x − R), R > H(p φ ), for the error probability ofĤ C n equals that of C n . ✷ Suppose in addition that the Schmidt basis is known, and we discuss the first main term of the mean square error, Theorem 13 Suppose the Schmidt basis of |φ is known and its Schmidt coefficient is unknown. Then, any global measurement satisfies,Ṽ if E φ (Ĥ n ) → H(p φ ) (n → ∞) for all |φ , and the estimateĤ C n * based on {C n * } achieves the equality.
Proof Consider a family of state vectors i √ p φ,i |e j,A |e j,B , where {|e j,A |e j,B } is fixed and p φ runs over all the probability distributions supported on {1, . . . , d}. Due to Theorem 5 in [13], the asymptotically optimal estimate of H(p φ ) is a function of data result from the projection measurement {|e j,A |e j,B } on each copies. Therefore, the problem reduces to the optimal estimate of H(p φ ) from the data generated from probability distribution p φ . Due to asymptotic Cramér-Rao inequality of classical statistics, the asymptotic mean square error of such estimate is lower-bounded by, where J is the Fisher information matrix of the totality of probability distributions supported on {1, · · · , d}. For J −1 i,j = p i,φ δ i,j − p i,φ p j,φ , we obtain the lower-bound (32).
To prove the achievability, observe that the Schmidt coefficient is exactly the spectrum of the reduced density matrix. As is discussed in [11,14],, the optimal measurement is the projectors {W n,A ⊗ W n,B } , which is used in the protocol {C n * }, and the estimated of the spectrum is n n . It had been shown that the asymptotic mean square error matrix of this estimate equals 1 n J −1 + o 1 n . Hence, if we estimate H(p φ ) by H( n n ), we can achieve the lower bound, as is easily checked by using Taylor's expansion. Now, due to (3), our estimate log dim Vn n differs from H( n n ) at most by O log n n . Therefore, their mean square error differs at most by O log n n 2 = o 1 n . As a result, the estimate based on {C n * } achieves the lower-bound (32). ✷

VI. CONCLUSIONS AND DISCUSSIONS
We have proposed a new protocol of entanglement concentration {C n * }, which has the following properties.
1. The input state are many copies of unknown pure states.
2. The output is the exact maximally entangled state, and its Schmidt rank.
3. Its performance is probabilistic, and entropy rate is asymptotically achieved.
4. Any protocol is no better than a protocol given by modification of the protocol {C n * } in its classical output only. 5. The protocol is optimal up to higher orders or non-asymptotically, depending on measures.
6. No classical communication is needed. 7. The classical output gives the estimate of the entropy of entanglement with minimum asymptotic error, where minimum is taken over all the global measurements.
The key to the optimality arguments is Lemma 3, which imply 4 in above, and drastically simplified the arguments. As is pointed out throughout the paper, almost all the statement of optimality, except for Theorem 9, generalizes to the case where the Schmidt coefficients are known.
As a measure of the distortion, we considered the worst-case distortion and the average distortion. Trivially, the latter constraint is stronger, and thus the proof for optimality was technically much simpler and results are stronger. A problem is which one is more natural. This is very subtle problem, but we think that the constraints on the average distortion is too generous. The reason is as follows. Under this constraint, the strong converse probability decreases very slowly (Theorem 7, (ii) ). It is easy to generalize this statement to non-universal entanglement concentration. This is in sharp contrast with the fact that strong converse probability converges exponentially fast in many other information theoretic problems.
Toward the end of Section IV F, using the linear programming approach, we gave another proof of Theorem 7. The similar proof of Theorem 9 is possible using the Lagrangian with H (p ψ ) slightly smaller than R. In addition, using the Lagrangian one can give another proof of the optimality results with the constraint on worst-case distortion. It had been pointed out by many authors that the theory of linear programming, especially the duality theorem, supplies strong mathematical tool to obtain an upper/lower-bound. Our case is one of such examples. Almost parallel with the arguments in this paper, we can prove the optimality of BBPS protocol for all the protocols which do not use information about phases of Schmidt basis and Schmidt coefficients. For that, we just have to replace average over all the local unitary in our arguments with the one over the phases. This average kills all the coherence between typical subspaces, changing the state to the direct sum of the maximally entangled states, and we obtain an equivalence of our key lemma. Rest of the arguments are also parallel, for an equivalence of (3) holds due to type theoretic arguments.
In the paper, we discussed universal entanglement concentration only, but the importance of universal entanglement distillation is obvious. This topic is already studied by some authors [4,17], but optimality of their protocol, etc. are left for the future study.
Another possible future direction is to explore new applications of the measurement used in our protocol. This measurement had already been applied to the estimation of the spectrum [11,14], and the universal data compression [8,10]. In addition, after the appearance of the first draft [9] of this paper, the polynomial size circuit for this measurement had been proposed [1], meaning that this measurements can be realized efficiently by forthcoming quantum computers.