{'fraction_non_alphanumeric': 0.051169966572383645, 'fraction_numerical': 0.011776806376960658, 'mean_word_length': 3.87124248496994, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 11, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On simultaneous min-entropy smoothing

In the context of network information theory, one often needs a multiparty probability distribution to be typical in several ways simultaneously. When considering quantum states instead of classical ones, it is in general difficult to prove the existence of a state that is jointly typical. Such a difficulty was recently emphasized and conjectures on the existence of such states were formulated. In this paper, we consider a one-shot multiparty typicality conjecture. The question can then be stated easily: is it possible to smooth the largest eigenvalues of all the marginals of a multipartite state {\rho} simultaneously while staying close to {\rho}? We prove the answer is yes whenever the marginals of the state commute. In the general quantum case, we prove that simultaneous smoothing is possible if the number of parties is two or more generally if the marginals to optimize satisfy some non-overlap property.


I. INTRODUCTION
It is natural in the context of studying information processing tasks to allow for a small error probability. This makes it possible to eliminate atypical behaviour of the system under consideration. When the state of a system is described by a probability distribution, an important quantity that arises in the analysis of information processing tasks is the largest probability. Events that happen with a probability that is atypically large can be discarded provided their total mass is smaller than the desired error probability. In order to optimize the rate of our task, one is then faced with an optimization over the choice of possible atypical sets. When the information processing task has multiple objectives, e.g., multiple receivers decoding the same message, there are several quantities to optimize. The question we consider here is how well can these different objectives be optimized simultaneously.
More concretely, consider a probability distribution ρ on m parties and fix some error tolerance ε > 0. Each marginal has some largest probability. Given that an error probability ε is allowed, it is possible to discard atypical sets of weight at most ε in order to reduce the largest probability. This could be done separately for each marginal. Now is it possible to find a state on m parties that is still reasonably close to the original state ρ but that is as good as the specific optimizers for all the marginals simultaneously? As the optimization in this setting refers to eliminating atypical behaviour, we also refer to the process as "smoothing". For quantum systems, the distribution is replaced by a positive semidefinite operator whose eigenvalues correspond to probabilities. The operation of taking a marginal corresponds to a partial trace. In this quantum framework, a (classical) probability distribution is represented as an operator with a particular eigenbasis.
One motivation for considering such a question is that it poses significant obstacles in the context of quantum network information theory as was recently emphasized in the study of multiparty state merging [2] and the study of the quantum interference channel [3], [7].
The purpose of this paper is to formulate the questions that arose from these works in a one-shot setting. We provide a proof of the conjecture when certain commutation relations between the marginals of the state hold. We also give a proof for the two-party quantum case and when the marginals to optimize are "non-overlapping". These seem to be the cases that can be handled using the current techniques and we believe that new techniques are needed to prove the general case. We hope this work will raise interest in the conjecture and its cousins.

A. Basic notation
The state of an isolated quantum system is represented by a unit vector in a Hilbert space. Quantum systems are denoted A, A 1 , A 2 , . . . and are identified with their corresponding Hilbert spaces. We write d A := dim A. To describe a distribution {p 1 , . . . , p r } over quantum states {|ψ 1 , . . . , |ψ r } (also called a mixed state), we use a density operator ρ = r i=1 p i |ψ i ψ i |. Here, |ψ ψ| refers to the projector on the complex line spanned by |ψ . A density operator is a positive semidefinite operator with unit trace. Let P(A) be the set of positive semidefinite operators acting on A. Then S(A) := {ρ ∈ P(A) : tr ρ = 1} is the set of density operators on A. The Hilbert space on which a density operator ρ ∈ S(A) acts is sometimes denoted by a subscript, as in ρ A . Superscripts are only used for labelling. In order to describe the state of a composite system A 1 A 2 , we use the tensor product Hilbert space A 1 ⊗ A 2 , which is sometimes simply denoted A 1 A 2 . If ρ A1A2 describes the joint state on A 1 A 2 , the reduced state on the system A 1 is obtained by the partial trace ρ A1 := tr A2 ρ A1A2 .
The evolution of any quantum system can be represented by a trace preserving completely positive map (TPCPM) E A→C . A map is called positive if for any positive operator ρ, E(ρ) is also positive. It is called completely positive if for any quantum system B, the map E ⊗ id B is positive. For a map E acting on system A 1 , we sometimes drop an identity acting on another system, as in E(ρ A1A2 ) = (E ⊗ id A2 )(ρ A1A2 ). For an introduction to quantum information, we refer the reader to [5], [12].

B. Distance measures
We use two distance measures based on extensions of the trace distance and the fidelity to subnormalized states, S ≤ (A) := {ρ ∈ P(A) : tr ρ ≤ 1}. For subnormalized states, we define quantum evolutions as trace non-increasing completely positive maps.
Let ρ, σ ∈ S ≤ (A) be subnormalized density operators. The trace distance is defined as Another metric that is more commonly used in this context is the purified distance [10], based on the generalized fidelity, which is given by The two distance measures are related by For the trace distance, the closed ε-ball around ρ is denoted by B D ε (ρ) and for the purified distance by B P ε (ρ). Quantum evolutions are non-expansive maps in both the trace distance and the purified distance. That is, for any trace non-increasing completely positive map E, we find (2)

C. Min-entropy
Let ρ ∈ S ≤ (A). The min-entropy of the state ρ is defined as H min (A) ρ := − log λ max (ρ), where λ max (ρ) denotes the largest eigenvalue of ρ. Optimizing this quantity over an εneighbourhood of ρ, we obtain the smooth min-entropy, where X can be set to either D for trace-distance or P for purified distance. As the purified distance is more common in this setting, we drop the superscript P when using it. Since The state σ can always be assumed to share a particular eigenbasis {|x } x with ρ. [8] This follows from the fact that a measurement of σ in this basis, E : σ → x |x x|σ|x x|, cannot increase the largest eigenvalue of σ. Since E(ρ) = ρ we find by (2) that E(σ) ∈ B X ε (ρ). As a consequence when only considering a single system A, the optimization problem in (3) is classical in the sense that we can always restrict it to states that share a particular eigenbasis with ρ.
III. CONJECTURE With this basic notation we state the main conjecture.
Conjecture III.1. For any number of parties m ∈ N there exists a function g m with lim ε→0 g m (ε) = 0 such that the following holds.
For any state ρ ∈ S ≤ (A) on any m-party system A = The function g m can depend on the number of parties m but it is important that it is independent of the physical realization. In particular, it must not depend on the dimensions of the systems A 1 , . . . , A m . Furthermore, note that by relation (1) the conjecture can equivalently be restated for the trace distance.
This conjecture is a generalization of the multiparty typicality conjecture of [2] to general states that are possibly not tensor powers. As such, by an application of the asymptotic equipartition property [9], Conjecture III.1 directly implies the multiparty typicality conjecture. One could of course consider stronger versions of this conjecture and ask for the conditional entropies to be also simultaneously smoothed. And in fact, the simultaneous decoding conjecture in [3] would follow from an analogous conjecture with conditional entropies. As difficulties already arise without conditioning, we focus on this simple setting here.
IV. MIN-ENTROPY SMOOTHING In the following, we give an explicit formula for a state σ ∈ B D ε (ρ) that satisfies (4) for X = D. This expression is then used to define smoothing as a quantum operation and to restate Conjecture III.1 from a different perspective.
Then the state σ :=f ε (ρ) ∈ B D ε (ρ) satisfies (4) for X = D. Using this Lemma, we define H min -smoothing as a quantum operation. Concisely, we realize it as a multiplication operator on the eigenvalues {λ i } i of the state ρ ∈ S ≤ (A), mapping Since f ε ≤ 1, we can represent this map as a quantum operation on S ≤ (A), Note that this map is also a feasible smoothing operation for (1). For the distance we then find P (ρ, E(ρ)) ≤ √ 2ε. On a multiparty system A = A 1 · · · A m , this construction can be repeated on every subsystem S. For ε > 0, we define a smoothing operation E S by where the smoothing function f S ε is defined in terms of ρ S . Conjecture III.1 can then be restated as follows: can we construct a global quantum evolution E : S ≤ (A) → S ≤ (A) from the marginal smoothing operations {E S } S⊂{A1,...,Am},S =∅ that simultaneously smooths all min-entropies of ρ keeping ρ close to itself?

V. CLASSICAL CASE
We show that classical states admit a natural solution of Conjecture III.1 from the perspective of quantum evolutions. In particular, the smoothing operations {E S } S∈K (6) for the subsystems, once extended appropriately to the total system, can be combined to define an iterative simultaneous H minsmoothing operation E. This result is stated in Theorem V.2. Furthermore, we provide a distribution showing the optimality of the obtained trace distance bound.
Let A = A 1 · · · A m be a classical system. A classical state ρ ∈ S cl ≤ (A) is characterized by its product eigenbasis, where {|i k } 1≤i k ≤dA k denotes an orthonormal basis of A k for all k ∈ {1, . . . , m}. Note that the structure of the classical state ρ implies that its closest simultaneous H min -smoother σ can always be assumed to be classical. This follows from the fact that a measurement of σ in the classical eigenbasis of ρ can increase neither the largest eigenvalue of any of its reduced states nor the distance to ρ. Therefore, Conjecture III.1 has a well-defined classical limit. Extending the smoothing maps {E S } S defined in (6) to act globally byĒ S := E S ⊗ id S c , so that E S (ρ S ) = tr S c (Ē S (ρ)), we observe the following properties.  (6) for all S ∈ K, are i) commutative:Ē S •Ē T =Ē T •Ē S ∀S, T ∈ K, ii) density operator decreasing:Ē S (τ ) ≤ τ ∀τ ∈ S cl ≤ (A), iii) distance preserving: D(τ,Ē S (τ )) = D(τ S , E S (τ S )) ∀τ ∈ S cl ≤ (A).
ii) This property holds for pure states τ = |i By linearity ofĒ S this statement extends to all of S cl ≤ (A). iii) The trace distance simplifies to the trace for ordered density operators, τ, ω ∈ S ≤ (A), τ ≥ ω : D(τ, ω) = tr(τ − ω), and, therefore, is independent of the subsystem where it is evaluated. By Lemma V.1 the smoothing operations {E S } S from (6) can be globally combined in a compatible way giving rise to Theorem V.2 (Classical case of Conjecture III.1). Let ρ ∈ S cl ≤ (A), K ⊂ 2 {A1,...Am} \ {∅}, ε > 0. There exists a state σ ∈ S cl ≤ (A) that satisfies In general, the bound (10) is optimal in the limit of large dimensions min 1≤i≤m d Ai .
Proof: Let (S i ) 1≤i≤|K| be an arbitrary ordering of the set K. Define the iteratively smoothed state Since property ii) Lemma V.1 carries over to any concatenation of the maps {Ē S } S∈K it follows that using complete positivity of E S , ∀S ∈ K, in the first step. This relation inherits to the subsystem S i under the partial trace, where it becomes σ S i ≤ E S i (ρ S i ), thus implying (9).
To bound the distance we successively apply the triangle inequality, where we have used Lemma V.1, iii), in the third step.
We prove that the bound (10) is optimal for two parties. The general case can be found in [1]. Let the parties A 1 , A 2 have equal dimension, d A1 = d A2 = 2n 2 + 1 for n ∈ N. Define a state p on the register {1, . . . , d A1 } × {1, . . . , d A2 } by the probability distribution where only every n-th entry on the diagonal is occupied by |K| , else set f S := 0.
Claim. For every ε < 1 |K| there exists n 0 ∈ N so that ∀n ≥ n 0 any classical state q on A 1 A 2 with H min (S) q ≥ H ε,D min (S) p ∀S ∈ K (12) satisfies D(p, q) ≥ |K|ε.
To prove this claim we denote the horizontal non-zero line in (11) by h A1 , the vertical non-zero line by h A2 and the non-zero diagonal by h A1A2 . Computing the marginals to we observe that the entries of p S , S ∈ K, coming from h S dominate all others by order n. Hence, for any ε < 1 |K| there exists an n 0 so that ∀n ≥ n 0 a probability weight of at least ε has to be removed from h S in order to smooth p on S. Since the only common entry of the sets {h S } S∈K has probability 0 the claim follows.
The construction of p in (11) can be naturally generalized to m parties. The probability distribution p is then defined on the discrete m-cube. The discrete lines h S are replaced by discrete hyperplanes, each lying orthogonal to the main diagonal of the subspace associated to the subsystem S. The density of nonzero entries on these hyperplanes decreases exponentially in the number of parties in subsystem S. The calculations are somewhat more involved and can be found in [1].
Choosing K = 2 {A1,...Am} \ {∅} Theorem V.2 proves conjecture III.1 for classical states with a trace distance bound of (2 m − 1)ε that is optimal (for trace distance smoothing) as shown by the distribution described in the previous paragraph. In fact, a modified version of Lemma V.1, where ii) and iii) only hold for τ = ρ, applies to any state ρ ∈ S ≤ (A) that satisfies the commutation relations This is sufficient to prove Theorem V.2 [1]. As a non-classical example that satisfies (13) consider a bipartite entangled pure state |ψ = d j=1 1 √ d |j A1 ⊗ |j A2 . Finally, considering simultaneous smoothing in the purified distance, we remark that the state p (11) and its generalizations to m parties for non-singleton K ⊂ 2 {A1,...Am} \ {∅} have a closest simultaneous H min -smoother q that satisfies in the limit (ε → 0) [1]. This shows that a squareroot dependence in ε is unavoidable when simultaneously smoothing in the purified distance.

VI. QUANTUM CASE
We start by analyzing the differences of the quantum case to the classical setting. Focussing on property ii) in Lemma V.1 we may ask: for any ρ ∈ S ≤ (A), does there exist a close state σ ≤ ρ with H min (S) σ ≥ H ε,D min (S) ρ ? The existence of such a state would immediately yield a proof for the quantum case of Conjecture III.1 by the fact that the smooth minentropy is monotonous in the positive semidefinite ordering on S ≤ (A). It turns out, however, that in general the answer is negative. As a counterexample consider a pure state ρ, so that one of its marginals ρ S is almost fully mixed with the exception of one eigenvalue, which is ε larger than all others. The state σ by σ ≤ ρ must then be a multiple of ρ, the best possible proportionality factor being 2 −(H ε min (S)ρ−Hmin(S)ρ) , which tends to 0 as (d S → ∞).
Returning to the quantum evolution perspective, the extended smoothing operations {Ē S := E S ⊗id S c } S∈K , where E S is defined as in (6), will in general not satisfy Lemma V.1, iii). Instead they satisfy the same property in the purified distance.
Proof: The inequality "≥" follows by the monotonicity property of the purified distance (2) under the TPCPM tr S c . [8] To derive the other inequality we use Uhlmann's Theorem for the fidelity [11]. Let |ψ ∈ A 1 A 2 R be a purification of τ , where in the first line it was used that Π A1 |ψ is a purification of Π A1 τ Π A1 . As tr(Π A1 τ Π A1 ) = tr(Π A1 τ A1 Π A1 ) and tr(τ ) = tr(τ A1 ) we conclude Using this Lemma, we show that the construction from the previous chapter can be transferred to the quantum setting yielding a proof of Conjecture III.1 for two parties.

A. Two parties
We note that the multiparty typicality conjecture, which is the special case when ρ is a tensor power state, was proved in [2] and subsequently in [6] for two parties. We provide here a proof in the more general one-shot setting which is hopefully more transparent.
Theorem VI.2 (Quantum case of conjecture III.1 for two parties).
The proof requires the following basic lemma.
We omit the proof of this basic fact, being essentially a consequence of the cyclicity of the partial trace in operators acting only on the system traced out.
Proof of Theorem VI.2: We define E S as in (6) for S ∈ K, E S := id S else, andĒ S := E S ⊗ id S c . Choose the order (S 1 , S 2 , S 3 ) = (A 1 , A 2 , A 1 A 2 ). Define This state has the right min-entropies (15): • On the total system A 1 A 2 we can apply the submultiplicativity of · ∞ : using Lemma VI.3 in the last step. SinceĒ A1 andĒ A2 commute the same argument applies on A 2 .
The distance part is entirely analogous to the classical case (cf. proof of Theorem V.2). The only difference is that P is used here throughout instead of D. Accordingly, Lemma VI.1 substitutes Lemma V.1, iii). Recalling that E S i was designed to smooth in the trace distance, in the last step we use (1) to obtain a bound on the purified distance, 2ε.

B. Non-overlapping subsystems
The proof of Theorem VI.2 can be generalized to an mparty system A = A 1 · · · A m where the subsystems K under consideration can be ordered with respect to the inclusion. The subsystems are then iteratively smoothed according to such an order starting with the largest system. Due to space limitations, we omit the proof of this result here.
Note that the smoothing operationsĒ S are rank nonincreasing and thus σ is pure if ρ is. By the Schmidtdecomposition, it follows that if ρ is pure for every pair of subsystems S, S c ∈ K the application of only one smoothing operation suffices to smooth them both. Therefore, Conjecture III.1 is also satisfied for tripartite pure states.

C. Three parties
The last theorem also highlights the simplest case where current techniques fail. Consider a mixed tripartite state ρ, K = {A 1 A 2 , A 2 A 3 }, ε > 0. Then, proceeding in an iterative way similar to the proof of Theorem VI.2, we introduce an ordering (S 1 , S 2 ) = (A 1 A 2 , A 2 A 3 ) and define σ :=Ē A1A2 • E A2A3 (ρ) for smoothing quantum operationsĒ A1A2 ,Ē A2A3 . Ignoring the structure ofĒ A2A3 for the moment, we can always defineĒ A1A2 such that H min (A 1 A 2 ) σ = H ε,D min (A 1 A 2 )ĒA 2 A 3 (ρ) provided thatĒ A2A3 (ρ) is known. But the question is precisely how to chooseĒ A2A3 so that the application ofĒ A1A2 does not affect the reduced state on A 2 A 3 too much?

VII. CONCLUSION
In this note, we presented a simple formulation for a problem that appears as a bottleneck in the analysis of network quantum information processing tasks. We proved that the classical version of the problem can be solved as well as the quantum case when the systems under consideration satisfy a non-overlapping condition. Understanding overlapping marginals seems to be also a barrier in the context of the quantum marginal problem [4].