format: text

text:
# Mitosis recursion for coefficients of Schubert polynomials

## 1. Introduction

It has been a goal for some years, ever since Kohnert made his conjecture in \[Koh91\], to find inductive combinatorial rules on diagrams in the $`n\times n`$ grid that yield the coefficients of Schubert polynomials \[LS82\], when counted properly. The mitosis rule was offered in \[KM02a\] as a solution to this problem, but the proof was long, and involved some notions that strayed rather far from the elementary combinatorics of permutations. The purpose of this note is to bring mitosis entirely into the realm of combinatorics, by giving a short combinatorial proof of the fact (Theorem 15) that mitosis lists reduced pipe dreams (also known as rc-graphs) \[FK96, BB93\] recursively by induction on weak order in $`S_n`$, starting from the unique reduced pipe dream for the long permutation $`w_0`$.

More precisely, the proof here of Theorem 15, and the resulting diagrammatic recursion for the coefficients of Schubert polynomials in Corollary 16, rests only on the formula of Billey, Jockusch, and Stanley (Theorem 4), the characterization of Schubert polynomials by divided differences (Definition 3), and elementary combinatorial properties of reduced pipe dreams (Lemmas 5, 9, and 12 plus Proposition 13).

Mitosis was originally conceived in \[KM02a\] as a residual operation derived from more complicated combinatorial isobaric divided differences (Demazure operators) on standard monomials for certain determinantal ideals defined in the context of Schubert varieties in flag manifolds. As such, it served as a geometrically motivated improvement on Kohnert’s rule \[Koh91, Mac91, Win99, Win02\], its advantages being the short combinatorial proof here and consistency with double Schubert polynomials as in \[KM02a\]. Mitosis is closely related to the construction of Schubert polynomials in terms of chains in Bruhat order in \[LS02\]. Other combinatorial algorithms producing Schubert polynomials include the chute and ladder moves on reduced pipe dreams \[BB93\], a different combinatorial divided difference operator on reduced pipe dreams \[Len02\], and an earlier construction of Bergeron \[Ber92\].

The plan of the paper is as follows. In the next two sections we review the definition of the set $`𝒫(w)`$ of reduced pipe dreams for a permutation $`wS_n`$, the BJS formula, and the mitosis algorithm on pipe dreams (subsets of the $`n\times n`$ grid). Section 4 provides an involution on $`𝒫(w)`$ that is crucial for the proof of the main theorem and corollary in Section 5. The final section, which concerns the mitosis poset and is logically independent of the other sections, reviews for the reader’s convenience two definitions and a conjecture from \[KM02a, Section 2.2\], because of their relevance in this combinatorial setting.

## 2. Pipe dreams

Consider a square grid $`_{>0}\times _{>0}`$ extending infinitely south and east, with the box in row $`i`$ and column $`j`$ labeled $`(i,j)`$, as in an $`\mathrm{}\times \mathrm{}`$ matrix. If each box in the grid is covered with a square tile containing either      or  Π Υ        , then one can think of the tiled grid as a network of pipes.

###### Definition 1.

A pipe dream is a finite subset of $`_{>0}\times _{>0}`$, identified as the set of crosses in a tiling by crosses      and elbow joints  Π Υ        . A pipe dream is reduced if each pair of pipes crosses at most once. The set $`𝒫(w)`$ of reduced pipe dreams for the permutation $`wS_n`$ is the set of reduced pipe dreams $`D`$ such that the pipe entering row $`i`$ exits from column $`w(i)`$.

Although we always draw crossing tiles as some sort of cross (either ‘+’ or ‘     ’, the former with the square tile boundary and the latter without), we often leave the elbow tiles blank or denote them by dots, to make the diagrams less cluttered. Viewing $`n`$ as fixed, we shall be interested in pipe dreams contained in the pipe dream $`D_0`$ that has crosses in the triangular region strictly above the main antidiagonal (in spots $`(i,j)`$ with $`i+jn`$) and elbow joints elsewhere in the square grid $`[n]\times [n]`$ of size $`n`$. Note that $`D_0`$ is the unique reduced pipe dream for the long permutation $`w_0=n\mathrm{}321`$ in $`S_n`$.

###### Example 2.

The pipe dream $`D`$ in Fig. 1 for $`n=8`$ is a reduced pipe dream for the permutation $`w=13865742S_8`$.

For clarity, we omit the square tile boundaries as well as the wavy “sea” of elbows  Π Υ         below the main antidiagonal in the right pipe dream. $`\mathrm{}`$

Since we need a statement of the BJS formula, we recall here the definition of Schubert polynomials of Lascoux and Schützenberger via divided differences. For notation, $`s_iS_n`$ denotes the transposition switching $`i`$ and $`i+1`$, and $`\mathrm{length}(w)`$ denotes the number of inversions in a permutation $`w`$.

###### Definition 3 (\[LS82\]).

The $`i^{\mathrm{th}}`$ divided difference operator $`_i`$ takes each polynomial $`f[x_1,\mathrm{},x_n]`$ to

$`_if(x_1,\mathrm{},x_n)`$ $`=`$ $`{\displaystyle \frac{f(x_1,\mathrm{},x_n)f(x_1,\mathrm{},x_{i1},x_{i+1},x_i,x_{i+2},\mathrm{},x_n)}{x_ix_{i+1}}}.`$
The Schubert polynomial for $`wS_n`$ is defined by the recursion

$`\mathrm{SS}_{ws_i}(x_1,\mathrm{},x_n)`$ $`=`$ $`_i\mathrm{SS}_w(x_1,\mathrm{},x_n)`$
whenever $`\mathrm{length}(ws_i)<\mathrm{length}(w)`$, and the initial condition $`\mathrm{SS}_{w_0}(x_1,\mathrm{},x_n)=_{i=1}^nx_i^{ni}`$.

###### Theorem 4 (\[BJS93, FS94\]).

$`\mathrm{SS}_w(x_1,\mathrm{},x_n)={\displaystyle \underset{D𝒫(w)}{}}𝐱^D`$, where $`𝐱^D={\displaystyle \underset{(i,j)D}{}}x_i`$.

The next lemma, which will be applied in Section 5, gives a criterion for when removing a ‘+’ from a pipe dream $`D𝒫(w)`$ leaves a pipe dream in $`𝒫(ws_i)`$. Specifically, it concerns the removal of a cross at $`(i,j)`$ from configurations that look like

* $`\begin{array}{cccccccccc}& 1& & & & \mathrm{}& & & j_{}& \\ i\hfill & \text{ }\text{ }& \text{ }\text{ }& \text{ }\text{ }& \text{ }\text{ }& \text{ }\text{ }& \text{ }\text{ }& \text{ }\text{ }& \text{ }\text{ }& \text{ }\mathrm{}\text{ }\\ i+1\hfill & \text{ }\text{ }& \text{ }\text{ }& \text{ }\text{ }& \text{ }\text{ }& \text{ }\text{ }& \text{ }\text{ }& \text{ }\text{ }& \text{Π}\text{ Υ}\text{ }\text{ }\text{ }& \end{array}\begin{array}{c}\\ =\end{array}\begin{array}{cccccccccc}& 1& \multicolumn{6}{c}{\mathrm{}}& j& \\ & & & & & & & & & \\ i\hfill & +& +& +& +& +& +& +& +& \text{ }\mathrm{}\text{ }\\ & & & & & & & & & \\ i+1\hfill & +& +& +& +& +& +& +& & \end{array}`$

at the left end of rows $`i`$ and $`i+1`$ in $`D`$.

###### Lemma 5.

Let $`D𝒫(w)`$ and $`j`$ be a fixed column index with $`(i+1,j)D`$, but $`(i,p)D`$ for all $`pj`$, and $`(i+1,p)D`$ for all $`p<j`$. Then $`\mathrm{length}(ws_i)<\mathrm{length}(w)`$, and if $`D^{}=D(i,j)`$ then $`D^{}𝒫(ws_i)`$.

###### Proof.

Removing $`(i,j)`$ only switches the exit points of the two pipes starting in rows $`i`$ and $`i+1`$, so the pipe starting in row $`k`$ of $`D^{}`$ exits out of column $`ws_i(k)`$ for each $`k`$. No pair of pipes can cross twice in $`D^{}`$ because there are $`\mathrm{length}(ws_i)`$ crossings.∎

## 3. Mitosis algorithm

Given a pipe dream in $`[n]\times [n]`$, define

$`\mathrm{start}_i(D)`$ $`=`$ $`\text{column index of leftmost elbow in row }i`$
$`=`$ $`\mathrm{min}(\{j(i,j)D\}\{n+1\}),`$
so the $`i^{\mathrm{th}}`$ row of $`D`$ is filled solidly with crosses in the region to the left of $`\mathrm{start}_i(D)`$. Let

$`𝒥_i(D)`$ $`=`$ $`\{\text{columns }j\text{ strictly to the left of }\mathrm{start}_i(D)(i+1,j)\text{ has no cross in }D\}.`$
For $`p𝒥_i(D)`$, construct the offspring $`D_p`$ as follows. First delete the cross at $`(i,p)`$ from $`D`$. Then take all crosses in row $`i`$ of $`𝒥_i(D)`$ that are to the left of column $`p`$, and move each one down to the empty box below it in row $`i+1`$.

###### Definition 6.

The $`i^{\mathrm{th}}`$ mitosis operator sends a pipe dream $`D`$ to

$`\mathrm{mitosis}_i(D)`$ $`=`$ $`\{D_pp𝒥_i(D)\}.`$
Write $`\mathrm{mitosis}_i(𝒫)=_{D𝒫}\mathrm{mitosis}_i(D)`$ whenever $`𝒫`$ is a set of pipe dreams.

Observe that all of the action takes place in rows $`i`$ and $`i+1`$, and $`\mathrm{mitosis}_i(D)`$ is an empty set whenever $`𝒥_i(D)`$ is empty.

###### Example 7.

The pipe dream $`D`$ at left is the reduced pipe dream for $`w=13865742`$ from Example 2:

$`\begin{array}{cc}& \\ & \\ 3& \\ 4& \\ & \\ & \\ & \\ & \\ & \end{array}\begin{array}{cccccccc}& & & & & & & \\ & +& & +& +& & & \\ & & & & & & & \\ & +& & & & +& & \\ & & & & & & & \\ +& +& +& +& & & & \\ & & & & & & & \\ & & +& & & & & \\ & & & & & & & \\ +& & & & & & & \\ & & & & & & & \\ +& +& & & & & & \\ & & & & & & & \\ +& & & & & & & \\ & & & & & & & \\ & & & & & & & \\ & & & & & & & \\ \multicolumn{4}{c}{}& & & & \\ \multicolumn{4}{c}{}& \mathrm{start}_3& & & \end{array}\begin{array}{c}\\ \\ \end{array}\begin{array}{c}\{\begin{array}{cccccccc}& & & & & & & \\ & +& & +& +& & & \\ & & & & & & & \\ & +& & & & +& & \\ & & & & & & & \\ & +& +& +& & & & \\ & & & & & & & \\ & & +& & & & & \\ & & & & & & & \\ +& & & & & & & \\ & & & & & & & \\ +& +& & & & & & \\ & & & & & & & \\ +& & & & & & & \\ & & & & & & & \\ & & & & & & & \end{array},\begin{array}{cccccccc}& & & & & & & \\ & +& & +& +& & & \\ & & & & & & & \\ & +& & & & +& & \\ & & & & & & & \\ & & +& +& & & & \\ & & & & & & & \\ +& & +& & & & & \\ & & & & & & & \\ +& & & & & & & \\ & & & & & & & \\ +& +& & & & & & \\ & & & & & & & \\ +& & & & & & & \\ & & & & & & & \\ & & & & & & & \end{array},\begin{array}{cccccccc}& & & & & & & \\ & +& & +& +& & & \\ & & & & & & & \\ & +& & & & +& & \\ & & & & & & & \\ & & +& & & & & \\ & & & & & & & \\ +& +& +& & & & & \\ & & & & & & & \\ +& & & & & & & \\ & & & & & & & \\ +& +& & & & & & \\ & & & & & & & \\ +& & & & & & & \\ & & & & & & & \\ & & & & & & & \end{array}\}\\ \begin{array}{c}\\ \end{array}\end{array}`$
The set of three pipe dreams on the right is obtained by applying $`\mathrm{mitosis}_3`$, since $`𝒥_3(D)`$ consists of columns $`1`$, $`2`$, and $`4`$. The offspring are ordered as in Proposition 10, below. $`\mathrm{}`$

In Proposition 10 we shall present another, more sequential way of writing down the mitosis offspring of a pipe dream. It uses a device invented by Bergeron and Billey.

###### Definition 8 (\[BB93\]).

A chutable rectangle is a connected $`2\times k`$ rectangle $`C`$ inside a pipe dream $`D`$ such that $`k2`$ and all but the following 3 locations in $`C`$ are crosses: the northwest, southwest, and southeast corners. Applying a chute move to $`D`$ is accomplished by placing a ‘+’ in the southwest corner of a chutable rectangle $`C`$ and removing the ‘+’ from the northeast corner of the same $`C`$.

Heuristically, a chute move therefore looks like:

* $`\begin{array}{c}\\ \begin{array}{ccccccccc}\multicolumn{7}{c}{}& & \begin{array}{c}\\ .\text{.}\text{.}\end{array}\\ & & & & & & & & \\ & & +& +& \text{ }\mathrm{}\text{ }& +& +& +& \\ & & & & & & & & \\ & & & & & & & & \\ & & +& +& & +& +& & \\ & & & & & & & & \\ \begin{array}{c}.\text{.}\text{.}\end{array}& & & & & & & & \end{array}\stackrel{\mathrm{chute}}{}\begin{array}{ccccccccc}\multicolumn{7}{c}{}& & \begin{array}{c}\\ .\text{.}\text{.}\end{array}\\ & & & & & & & & \\ & & +& +& \text{ }\mathrm{}\text{ }& +& +& & \\ & & & & & & & & \\ & & & & & & & & \\ & +& +& +& & +& +& & \\ & & & & & & & & \\ \begin{array}{c}.\text{.}\text{.}\end{array}& & & & & & & & \end{array}\end{array}`$

The following basic fact about chute moves was discovered by Bergeron and Billey \[BB93\].

###### Lemma 9.

The set $`𝒫(w)`$ of reduced pipe dreams for $`w`$ is closed under chute moves.

###### Proof.

If two pipe intersect at the ‘+’ in the northeast corner of a chutable rectangle $`C`$, then chuting that ‘+’ only changes the crossing point of the two pipes to the southwest corner of $`C`$. No other pipes are affected.∎

###### Proposition 10.

Let $`D`$ be a pipe dream, and suppose $`j`$ is the smallest column index such that $`(i+1,j)D`$ and $`(i,p)D`$ for all $`pj`$. Then $`D_p\mathrm{mitosis}_i(D)`$ is obtained from $`D`$ by

* removing $`(i,j)`$, and then
* performing chute moves from row $`i`$ to row $`i+1`$, each one as far left as possible, so that $`(i,p)`$ is the last ‘+’  removed.

###### Proof.

Immediate from Definitions 6 and 8. ∎

## 4. Intron mutation

###### Definition 11.

Let $`D`$ be a pipe dream and $`i`$ a fixed row index. Order the boxes in rows $`i`$ and $`i+1`$ of $`D`$ as in the following diagram:

* $`\begin{array}{cccccc}\multicolumn{6}{c}{}\\ \hfill & 1& 2& 3& 4& \mathrm{}\\ & & & & & \\ i\hfill & 1& 3& 5& 7& \text{ }\mathrm{}\text{ }\\ & & & & & \\ i+1\hfill & 2& 4& 6& 8& \\ & & & & & \end{array}`$

An intron111For the origin of this term, see \[KM02a, Section 3.5\]. in these two adjacent rows is a $`2\times k`$ rectangle $`C`$ such that

* the first and last boxes in $`C`$ (the northwest and southeast corners) are elbows; and
* no elbow in $`C`$ is strictly northeast or strictly southwest of another elbow (so due north, due south, due east, or due west are all okay).

Ignoring all $`\begin{array}{c}\\ +\\ \\ +\end{array}`$ columns in rows $`i`$ and $`i+1`$, an intron is just a sequence of $`\begin{array}{c}\\ \\ \\ +\end{array}`$ columns in rows $`i`$ and $`i+1`$, followed by a sequence of $`\begin{array}{c}\\ +\\ \\ \end{array}`$ columns, possibly with one $`\begin{array}{c}\\ \\ \\ \end{array}`$ column in between. Columns with two crosses $`\begin{array}{c}\\ +\\ \\ +\end{array}`$ can be ignored for the purpose of proofs in what follows.

If an intron $`C`$ satisfies the following extra condition, then $`C`$ is called a maximal intron:

* the elbow with largest index before $`C`$ (if there is one) resides in row $`i+1`$, and the elbow with smallest index after $`C`$ (if there is one) resides in row $`i`$.

###### Lemma 12.

For an intron $`C`$ in a reduced pipe dream, a unique intron $`\tau (C)`$ satisfies

* the sets of columns with exactly two crosses are the same in $`C`$ and $`\tau (C)`$, and
* the number $`c_i`$ of crosses in row $`i`$ of $`C`$ equals the number of crosses in row $`i+1`$ of $`\tau (C)`$, and conversely.

The involution $`\tau `$, called intron mutation, is always accomplished by a sequence of chute moves or inverse chute moves (because $`C`$ is part of a reduced pipe dream).

###### Proof.

First assume $`c_i>c_{i+1}`$ and work by induction on $`c=c_ic_{i+1}`$. If $`c=0`$ then $`\tau (C)=C`$ and the lemma is obvious. If $`c>0`$ then consider the leftmost $`\begin{array}{c}\\ +\\ \\ \end{array}`$ column. Moving to the left from this column there must be a column not equal to $`\begin{array}{c}\\ +\\ \\ +\end{array}`$ , since the northwest entry of $`C`$ is an elbow. The rightmost such column must be $`\begin{array}{c}\\ \\ \\ \end{array}`$ , because its row $`i`$ entry is an elbow (by construction) and its row $`i+1`$ entry cannot be a cross (for then the pipes crossing there would also cross in the $`\begin{array}{c}\\ +\\ \\ \end{array}`$ column). This means we can chute the ‘+’ in $`\begin{array}{c}\\ +\\ \\ \end{array}`$ into the $`\begin{array}{c}\\ \\ \\ \end{array}`$ column, and proceed by induction.

Flip the argument $`180^{}`$ if $`c_i<c_{i+1}`$, so the chute move becomes an inverse chute.∎

For example, here is an intron mutation accomplished by chuting the crosses in columns $`4`$, $`6`$, and then $`7`$ of row $`i`$; the zigzag shapes formed by the dots in these introns are typical.

$`\begin{array}{ccc}\begin{array}{ccccccccc}\multicolumn{8}{c}{}& \\ & & & & 4& & 6& 7& \\ i\hfill & \text{Π}\text{ Υ}\text{ }\text{ }\text{ }& \text{Π}\text{ Υ}\text{ }\text{ }\text{ }& \text{ }\text{ }& \text{ }\text{ }& \text{ }\text{ }& \text{ }\text{ }& \text{ }\text{ }& \text{ }\text{ }\\ i+1\hfill & \text{ }\text{ }& \text{Π}\text{ Υ}\text{ }\text{ }\text{ }& \text{ }\text{ }& \text{Π}\text{ Υ}\text{ }\text{ }\text{ }& \text{ }\text{ }& \text{Π}\text{ Υ}\text{ }\text{ }\text{ }& \text{Π}\text{ Υ}\text{ }\text{ }\text{ }& \text{Π}\text{ Υ}\text{ }\text{ }\text{ }\end{array}& =& \begin{array}{ccccccccc}\multicolumn{9}{c}{}\\ \multicolumn{4}{c}{}& 4& & 6& 7& \\ & & \multicolumn{-1}{c}{}& & & & & & \\ i\hfill & & & +& +& +& +& +& +\\ & & \multicolumn{-1}{c}{}& & & & & & \\ i+1\hfill & +& & +& & +& & & \end{array}\\ \begin{array}{c}\\ \tau \end{array}& & \begin{array}{c}\\ \tau \end{array}\\ \begin{array}{ccccccccc}\multicolumn{8}{c}{}& \\ & & & & & & & & \\ i\hfill & \text{Π}\text{ Υ}\text{ }\text{ }\text{ }& \text{Π}\text{ Υ}\text{ }\text{ }\text{ }& \text{ }\text{ }& \text{Π}\text{ Υ}\text{ }\text{ }\text{ }& \text{ }\text{ }& \text{Π}\text{ Υ}\text{ }\text{ }\text{ }& \text{Π}\text{ Υ}\text{ }\text{ }\text{ }& \text{ }\text{ }\\ i+1\hfill & \text{ }\text{ }& \text{ }\text{ }& \text{ }\text{ }& \text{ }\text{ }& \text{ }\text{ }& \text{ }\text{ }& \text{Π}\text{ Υ}\text{ }\text{ }\text{ }& \text{Π}\text{ Υ}\text{ }\text{ }\text{ }\end{array}& =& \begin{array}{ccccccc}& & \multicolumn{-1}{c}{}& & & & & & \\ i\hfill & & & +& & +& & & +\\ & & \multicolumn{-1}{c}{}& & & & & & \\ i+1\hfill & +& +& +& +& +& +& & \end{array}\end{array}`$
###### Proposition 13.

For each $`i`$ there is an involution $`\tau _i:𝒫(w)𝒫(w)`$ such that $`\tau _i^2=1`$, and for all $`D𝒫(w)`$:

* $`\tau _iD`$ agrees with $`D`$ outside rows $`i`$ and $`i+1`$.
* $`\mathrm{start}_i(\tau _iD)=\mathrm{start}_i(D)`$, and $`\tau _iD`$ agrees with $`D`$ strictly west of this column.
* $`\mathrm{}_i^i(\tau _iD)=\mathrm{}_{i+1}^i(D)`$,

where $`\mathrm{}_r^i()`$ is the number of crosses in row $`r`$ that are east of or in column $`\mathrm{start}_i()`$.

###### Proof.

Let $`D𝒫(w)`$. Consider the union of all columns in rows $`i`$ and $`i+1`$ of $`D`$ that are east of or coincide with column $`\mathrm{start}_i(D)`$. Since the first and last boxes in this region (numbered as in Definition 11) are elbows, this region breaks uniquely into a disjoint union of $`2\times k`$ rectangles, each of which is either a maximal intron or completely filled with crosses. Indeed, this follows from (3) and Definition 11. Applying intron mutation to each maximal intron therein leaves a pipe dream that breaks up uniquely into maximal introns and solid crosses in the same way. Therefore the lemma comes down to verifying that intron mutation preserves the property of being in $`𝒫(w)`$, which comes from Lemmas 9 and 12.∎

###### Remark 14.

Intron mutation is precisely the involution (coplactic operation) $`\sigma _i`$ defined by Lascoux on words (see the survey article \[LLT97\], for example) and extended to reduced pipe dreams in \[Len02\]. However, when all introns in rows $`i`$ and $`i+1`$ are strung together, the involution $`\tau _i`$ does not agree with $`\sigma _i`$. In fact, Lascoux’s involution is based on ‘$`r`$-pairing’, which is also used in the work of Bergeron \[Ber92\] and Lenart \[Len02\] to define combinatorial versions of divided difference operators. Intron mutation is therefore a different mechanism by which combinatorial divided differences can be defined on reduced pipe dreams. $`\mathrm{}`$

## 5. Mitosis theorem

###### Theorem 15.

If $`\mathrm{length}(ws_i)<\mathrm{length}(w)`$, then the set $`𝒫(ws_i)`$ of reduced pipe dreams for $`ws_i`$ is the disjoint union $`_{D𝒫(w)}\mathrm{mitosis}_i(D)`$. Therefore

(6) $`𝒫(w)`$ $`=`$ $`\mathrm{mitosis}_{i_k}\mathrm{}\mathrm{mitosis}_{i_1}(D_0)`$
if $`s_{i_1}\mathrm{}s_{i_k}`$ is a reduced expression for $`w_0w`$.

###### Proof.

Use the description of mitosis in Proposition 10 along with Lemmas 5 and 9 to conclude that $`\mathrm{mitosis}_i(D)𝒫(ws_i)`$ whenever $`D𝒫(w)`$. It follows directly from the definitions that $`\mathrm{mitosis}_i(D)\mathrm{mitosis}_i(D^{})=\mathrm{}`$ if $`DD^{}`$ are reduced pipe dreams for $`w`$. Thus it suffices to prove that $`\mathrm{mitosis}_i(𝒫(w))`$ has the same cardinality as $`𝒫(ws_i)`$.

Fix $`D𝒫(w)`$, write $`𝐱^D=_{(i,j)D}x_i`$, and let $`J=|𝒥_i(D)|`$ be the number of mitosis offspring of $`D`$. The monomial $`𝐱^D`$ is a product $`x_i^J𝐱^D^{}`$, where $`D^{}`$ is the pipe dream (not reduced) obtained from $`D`$ by erasing the crosses in row $`i`$ of $`𝒥_i(D)`$. Definition 6 implies that

(7)
$$\underset{E\mathrm{mitosis}_i(D)}{}𝐱^E=\underset{d=1}{\overset{J}{}}x_i^{Jd}x_{i+1}^{d1}𝐱^D^{}=_i(x_i^J)𝐱^D^{}.$$

If $`\tau _iD=D`$, then $`𝐱^D^{}`$ is symmetric in $`x_i`$ and $`x_{i+1}`$ by Proposition 13, so that

$$_i(x_i^J)𝐱^D^{}=_i(x_i^J𝐱^D^{})=_i(𝐱^D)$$

in this case. On the other hand, if $`\tau _iDD`$, then letting $`s_i`$ act on polynomials by switching $`x_i`$ and $`x_{i+1}`$, Proposition 13 implies that adding the sums in (7) for $`D`$ and $`\tau _iD`$ yields

$$_i(x_i^J)(𝐱^D^{}+s_i𝐱^D^{})=_i(x_i^J(𝐱^D^{}+s_i𝐱^D^{}))=_i(𝐱^D+𝐱^{\tau _iD}).$$

Pairing off the elements of $`𝒫(w)`$ not fixed by $`\tau _i`$, we therefore conclude that

$$\underset{E\mathrm{mitosis}_i(𝒫(w))}{}𝐱^E=_i\left(\underset{D𝒫(w)}{}𝐱^D\right)=_i(\mathrm{SS}_w(𝐱))=\mathrm{SS}_{ws_i}(𝐱)=\underset{E𝒫(ws_i)}{}𝐱^E$$

by Theorem 4 and the recursion for $`\mathrm{SS}_w(𝐱):=\mathrm{SS}_w(x_1,\mathrm{},x_n)`$ as in Definition 3. Plugging in $`1,\mathrm{},1`$ for $`𝐱=x_1,\mathrm{},x_n`$ implies that $`|\mathrm{mitosis}_i(𝒫(w))|=|𝒫(ws_i)|`$, as desired.∎

Finally we come to the generation of Schubert coefficients by induction on weak Bruhat order via mitosis. For notation, if $`v=s_{i_1}\mathrm{}s_{i_k}`$ is a reduced expression, set $`\mathrm{mitosis}_v=\mathrm{mitosis}_{i_k}\mathrm{}\mathrm{mitosis}_{i_1}`$.

###### Corollary 16.

For any permutation $`wS_n`$ we have

$`\mathrm{SS}_w(x_1,\mathrm{},x_n)`$ $`=`$ $`{\displaystyle \underset{D\mathrm{mitosis}_v(D_0)}{}}𝐱^D\mathrm{for}v=w_0w,`$
where $`𝒫(w_0)=\{D_0\}`$, and $`𝐱^D=_{(i,j)D}x_i`$ for any pipe dream $`D`$.

###### Proof.

Theorem 15 and Theorem 4. ∎

## 6. Mitosis poset

The next definition generalizes to arbitrary $`n`$ the poset of pipe dreams for $`n=3`$ in Fig. 2.

###### Definition 17 (\[KM02a, Definition 2.2.4\]).

Theorem 15 defines a partial order, namely

$`D^{}D`$ if $`D^{}\mathrm{mitosis}_i(D)\text{ for some }i,`$
making the reduced pipe dreams for all of $`S_n`$ into the mitosis poset $`𝒫_n=_{wS_n}𝒫(w)`$.

The poset $`𝒫_n`$, which is ranked by length = cardinality, fibers over the weak Bruhat order on $`S_n`$, with the preimage of $`wS_n`$ being $`𝒫(w)`$. A reduced expression for $`w_0w`$ can be thought of as the edge labels on a decreasing path beginning at $`w_0`$ and ending at $`w`$ in the weak Bruhat order on $`S_n`$. The preimage in $`𝒫_n`$ of such a path is a tree having $`𝒫(w)`$ among its leaves (two reduced pipe dreams cannot share an offspring by the disjointness of the union in Theorem 15).

###### Definition 18.

A path decreasing from $`w_0`$ to $`w`$ in the weak order is poptotic if the leaves of its preimage in $`𝒫_n`$ are precisely $`𝒫(w)`$.

In other words, a path is poptotic if every reduced pipe dream lying over its interior has at least one offspring. For example, the right hand path in Fig. 2 from $`321`$ to $`123`$ is poptotic because only one reduced pipe dream appears at each stage, while the left path is apoptotic222The word ‘apoptosis’ refers in biology to programmed cell death, where some cell in a multicellular organism commits suicide for the greater good of the organism. Thus apoptotic indicates that some reduced pipe dream dies without offspring, while poptotic indicates that all pipe dreams survive with offspring. because the first reduced pipe dream for $`132`$ has no offspring under $`\mathrm{mitosis}_2`$.

###### Proposition 19.

Poptotic paths from $`w_0`$ to $`w`$ exist. In fact, the lexicographically first reduced expression for $`w_0w`$ (in which $`s_1>s_2>\mathrm{}>s_{n1}`$) corresponds to a poptotic path.

In particular, the lex first path from $`w_0`$ to $`\mathrm{id}_n`$ passes through dominant permutations, which by definition have exactly one reduced pipe dream (shaped like a Young diagram).

###### Proof.

Number the boxes in the strict upper-left triangle, meaning all locations $`(q,p)`$ such that $`q+pn`$, as follows, where $`N=\left(\genfrac{}{}{0pt}{}{n}{2}\right)`$.

* $`\begin{array}{ccccccc}& & & & & & \\ N& & 10& 6& 3& 1& \\ & & & & & & \\ & & & & & & \\ & & 9& 5& 2& & \\ & & & & & & \\ \begin{array}{c}\mathrm{}\end{array}& \mathrm{}& 8& 4& \multicolumn{2}{c}{}& \\ & & & & & & \\ & & 7& \multicolumn{3}{c}{}& \\ & & & & & & \\ & .\text{.}\text{.}& \multicolumn{4}{c}{}& \end{array}`$

The ordered sequence $`(1,2,1,3,2,1,4,3,2,1,\mathrm{})`$ of row indices of boxes in this upper triangle gives rise to the lex first reduced expression $`s_1s_2s_1s_3s_2s_1s_4s_3s_2s_1\mathrm{}`$ for the long word $`w_0=w_0\mathrm{id}_n`$. In general, lex first reduced words for arbitrary $`w_0w`$ correspond bijectively to the complements in the upper-left triangle of so-called top reduced pipe dreams \[BB93\], which are characterized (by definition) as having no $`\begin{array}{c}\\ \\ \\ +\end{array}`$ configurations. The reduced word corresponding to a top pipe dream is the ordered subsequence of row indices skipping the crosses atop each column.

Now suppose that $`\mathrm{length}(ws_i)<\mathrm{length}(w)`$, and that the lex first reduced expression for $`w_0ws_i`$ ends in $`s_i^{}s_i`$. Under the bijection above between lex first reduced words and complements of top reduced pipe dreams, $`s_i^{}`$ and $`s_i`$ correspond to the row indices $`i^{}`$ and $`i`$ of boxes numbered $`\alpha ^{}`$ and $`\alpha `$ satisfying $`\alpha ^{}<\alpha `$. \[N.B. Either $`i=i^{}1`$, in which case $`\alpha ^{}=\alpha 1`$, or else $`i>i^{}`$, and $`\alpha `$ sits just above the main antidiagonal in some column to the left of $`\alpha ^{}`$.\] Therefore, we shall assume by induction on length that

(\*) every reduced pipe dream in $`𝒫(w)`$ has crosses in boxes $`>\alpha ^{}`$ and an elbow at $`\alpha ^{}`$.
(the case $`\mathrm{length}(w_0w)=1`$ is easy). The goal is to prove that $`()`$ holds with $`ws_i`$ in place of $`w`$ and $`\alpha `$ in place of $`\alpha ^{}`$. But first, note that Lemma 5, which holds with $`\alpha `$ in position $`(i,j)`$ by assumption $`()`$, says that $`\mathrm{mitosis}_i(D)`$ is nonempty for all $`D𝒫(w)`$, as required.

More precisely, Lemma 5 says that removing the cross at $`\alpha `$ from each $`D𝒫(w)`$ produces a pipe dream in $`𝒫(ws_i)`$. Furthermore, either $`\alpha `$ lies in the top row or the box in $`D`$ due north of $`\alpha `$ is a cross, so it is impossible for chute moves to end there after deleting the cross from $`\alpha `$. Consequently, Proposition 10 implies that every pipe dream $`D^{}\mathrm{mitosis}_i(D)`$ has crosses in boxes marked $`>\alpha `$, and an elbow joint in the box marked $`\alpha `$. The proof is complete by Theorem 15.∎

###### Example 20.

The three pipe dreams on the right in Example 7 are all reduced pipe dreams for $`v=13685742=ws_3`$, where $`w=13865742`$ as in Example 2. Setting $`i=4`$ and inspecting the inversions of $`v`$, we find that $`\mathrm{length}(vs_4)<\mathrm{length}(v)`$. On the other hand, $`\mathrm{mitosis}_4`$ kills the first two of the three pipe dreams, whereas the last has two offspring. Thus any path from $`w_0`$ to $`vs_4`$ ending with $`(\mathrm{},v,vs_4)`$ is necessarily apoptotic.

Note that the lex first reduced expression for $`w_0v`$, which corresponds to a poptotic path from $`w_0`$ to $`v`$ by Proposition 19, equals $`s_2s_1s_3s_5s_4s_3s_2s_1s_7s_6s_5s_4s_3s_2s_1`$, while the lex first reduced expression for $`w_0vs_4`$ equals $`s_2s_1s_3s_2s_5s_4s_3s_2s_1s_7s_6s_5s_4s_3s_2s_1`$ (the $`s_2`$ in the fourth slot is new). These correspond to top reduced pipe dreams

$$\begin{array}{cccccccc}& & & & & & & \\ & +& & +& +& & +& \\ & & & & & & & \\ & +& & +& +& & & \\ & & & & & & & \\ & +& & +& & & & \\ & & & & & & & \\ & +& & +& & & & \\ & & & & & & & \\ & +& & & & & & \\ & & & & & & & \\ & +& & & & & & \\ & & & & & & & \\ & & & & & & & \\ & & & & & & & \\ & & & & & & & \\ & & & & & & & \\ \multicolumn{8}{c}{}\\ \multicolumn{8}{c}{v}\end{array}\begin{array}{c}\\ \text{and}\\ \\ \end{array}\begin{array}{cccccccc}& & & & & & & \\ & +& & +& +& & +& \\ & & & & & & & \\ & +& & +& & & & \\ & & & & & & & \\ & +& & +& & & & \\ & & & & & & & \\ & +& & +& & & & \\ & & & & & & & \\ & +& & & & & & \\ & & & & & & & \\ & +& & & & & & \\ & & & & & & & \\ & & & & & & & \\ & & & & & & & \\ & & & & & & & \\ & & & & & & & \\ \multicolumn{8}{c}{}\\ \multicolumn{8}{c}{vs_4}\end{array}$$

in which the row indices of the dots give the lex first reduced expressions. $`\mathrm{}`$

Whether or not a path from $`w_0`$ to $`w`$ is poptotic, breadth-first search on the preimage tree (ordering the mitosis offspring as in Proposition 10) yields a total order on $`𝒫(w)`$. It can be shown that poptotic total orders by breadth-first search are linear extensions of the partial order on reduced pipe dreams determined by chute operations.

Define the simplicial complex $`_w`$ with vertex set $`[n]\times [n]`$ to have as its facets the complements of the reduced pipe dreams for $`w`$:

$`\mathrm{facets}(_w)`$ $`=`$ $`\{\left([n]\times [n]\right)DD𝒫(w)\}.`$
This is an example of a ‘subword complex’ \[KM02a, KM02b\], and is hence shellable by \[KM02a, Theorem A.4\]. Through heuristic arguments and computer calculations in small symmetric groups, we are convinced of the following.

###### Conjecture 21.

Poptotic orders on $`𝒫(w)`$ by breadth-first search yield shellings of $`_w`$.

To emphasize: shellability is not in question, because shellings of $`_w`$ appear in \[KM02a, Theorem A.4 and Section 3.9\]. The conjecture would just give more intuitive shellings than those known. It is conceivable that all of the apoptotic total orders are shellings, too, although this seems less likely.

Acknowledgements. The author is grateful to Allen Knutson, Cristian Lenart, Vic Reiner, and Anne Schilling for motivation and inspiration. Mitosis was discovered in part because of a superb AMS meeting on Modern Schubert Calculus organized by Frank Sottile and Nantel Bergeron (the latter also supplied macros for drawing pipe dreams).


text:
# Reversible transformations from pure to mixed states, and the unique measure of information

## I Introduction

There are two opposing pictures of information. In the first picture, a source produces a large amount of information if it has large entropy. Thus information can be associated with entropy. This is because the receiver is being informed only if he is “surprised”. In such an approach the information has a subjective meaning: something which is known by the sender, but is not known by receiver. The receiver treats the message as the information, if she didn’t know it.

One can consider a different approach to information – an objective one where a system represents information if it is in pure state (zero entropy). The state is itself the information. This view is more natural in the context of thermodynamics. There, ”knowledge is power” in the sense that one can draw work from a single heat bath by use of systems in known pure states Szilard (1929). On the other hand, the heat bath is represented by a maximally entropic state, hence it is the less informative one. The pure state represents information needed to order the energy of the heat bath.

There can be many candidates for functions to measure information. However, Shannon recognized that there is a unique function that shares some natural properties to describe information. Shannon, derived his unique measure based on the subjective picture of information. Therefore his information function (Shannon entropy) increases as the dispersion of the probability distribution increases. The same is true of the generalization of Shannon’s entropy to the quantum case which is the von Neumann’s entropy $`S(\varrho )=\mathrm{Tr}\varrho \mathrm{log}\varrho `$.

One can consider a measure of objective information, that has the converse tendency: namely $`I=\mathrm{log}dH`$ where $`\mathrm{log}d`$ is the maximal entropy of the system (i.e. the system has $`d`$ states). In the quantum case it would be $`\mathrm{log}dS(\varrho )`$. Such a function was naturally interpreted as the information contents of the state as introduced by Brillouin.

One can ask the question: can this function be derived independently of the notion of entropy, so that it is not just a subtraction of two known terms, but rather has an autonomous meaning?

It turns out that there is such a possibility and it is offered by quantum information theory: in Ref. Horodecki et al.  we have derived the function $`I`$ as the unique one, that does not increase under some class of operations. The motivation came from considering information as a resource in distributed systemsOppenheim et al. (2002). The main aim of the present paper is to present the full rigorous version of that derivation. In the process, we give a protocol for reversible transformations between states using a random source of noise. We also discuss these results in the context of the issue of reversibility and entanglement theory.

It is quantum information theory (QIT) that provides us with a suitable perspective to attack the problem. Indeed, one of the central themes of QIT is the idea of optimal transitions between states under a restricted class of operations. This originates from attempts to describe entanglement of quantum states. Although it was difficult to say what exactly entanglement was, it was clear that it could not increase under the class of operations made up of local operations and classical communication (LOCC)Bennett et al. (1996a, b). These operations allow one to use any amount of separable states for free, but do not allow one to create entangled states. One can take the converse point of view: one starts with a given class of operations (LOCC operations), and treat the states that are not free as containing a resource, which can be called entanglement (cf. Vidal (2000)). The basic questions of entanglement theory is: can state $`\varrho `$ be transformed into $`\sigma `$ by LOCC? What is the optimal rate of such a transition?

In entanglement theory, this allowed one to define a number of measures of entanglement, since essentially, any function which does not increase under LOCC is a measure. However, thus far, no one has found a unique measure. The essential difficulty (as will become clearer) is that operations under LOCC are not reversible. However, if one has a restricted class of operations for which transitions are reversible, then we will see that the rate of transitions gives one a unique measure. This is similar to pure bipartite state entanglement where we have reversibility, and there is unique measure of entanglement (entropy of subsystem)Popescu and Rohrlich (1997); Bennett et al. (1996c).

In the present work, we consider a restricted class of operations we shall call Noisy Operations (NO) Kar  and use this to develop a unique measure for information. Essentially, we consider operations where one is allowed to use random noise as a free resource. Perhaps counter-intuitively, randomness allows one to make the transformations reversible: the number of pure states and noise which is needed to form the state, is the same as the amount that can be obtained from the state. The usual interpretation of mixed states, is that there creation involves irreversibly destroying information. Here we see that if one has access to noise as a resource, then there is no irreversibility.

This has interesting consequences concerning entanglement theory, since there, the irreversibility is often associated with the fact that one is dealing with mixed states. Here, we see that transitions into mixed states need not involve irreversibility. In fact, the axiomatic structure of the paradigm presented here involving mixed states is very similar to pure state entanglement manipulation. This shows that apriori, mixed state entanglement manipulation need not involve irreversibility, leaving open the question of why entanglement manipulation involves inevitable irreversibilities.

Other restricted classes of operations may lead one to find unique measures for other quantities. Here, we consider the optimal transitions between states by means of NO. In the asymptotic limit of many identical copies, we will obtain that there is only one function that does not increase under NO. We will establish that the optimal ratio of conversion between a state $`\varrho `$ of a $`N`$ qubit system and a state $`\sigma `$ of a $`N^{}`$ qubit system is equal to $`\frac{NS(\varrho )}{N^{}S(\sigma )}`$. The transitions are reversible, even though mixed states are involved. Finally we will consider operations without free noisy ancillas. Then the mixed states have to be created from pure states by partial trace, which introduces irreversibility. We discuss the implications of our results on understanding entanglement transformations, especially bound entanglement.

The work is organized as follows: In Section II we introduce the class of Noisy Operations. Then in Section III we show how one can transform a given state into another state, under NO, provided certain conditions are met. In IV we go to the asymptotic regime, and show that these transition rates are optimal. This will allow us to find the unique measure of information in Section V. In Section VI we discuss the case of transitions without access to noise, and give the transition rates in this case. We discuss this in terms of understanding the source of irreversibility in transitions, and relate it to attempts to understand entanglement in Section VII. We conclude with some open questions in Section VIII.

## II Noisy operations

Perhaps the most important restricted class of operations which has been considered in quantum information theory is LOCC, which was introduced in the context of understanding entanglement in shared systems. One is then interested in such questions such as how many maximally entangled states can a particular state be transformed into (i.e. the rate of distilling singlet). However, analyzing LOCC operations proved rather difficult. Therefore, to facilitate the investigation of entanglement, a larger classes of operations were analyzed – so called PPT operationsRains (1999, 2001); Vedral and Plenio (1998) which are superoperators which preserve the positivity of partial transpose.

One can also consider other restricted classes of operations, and consider various versions of the state transformation problem. On the extreme end, one allows all operations, and adding any ancilla. Then any state can be created for free, so that there is no resources to be manipulated, and the theory becomes trivial.

As one knows any operation can be composed out of a unitary operation, adding an ancilla in some state, and removing ancilla. Suppose that we want to make the theory nontrivial, while keeping all unitaries in our class of allowable operations. The only way is then to restrict the state of the free ancilla, or somehow restrict removing ancillas. In the present work, we consider only restrictions to the free ancilla. While one could instead consider restrictions on removing ancillas, we believe that this would give identical resultscon .

Thus we will restrict to choosing states that can be added for free by means of ancillas. Remarkably, the choice of which ancillas to allow is forced on us. It turns out that the only choice that does not make the theory trivial is that the free ancilla must be in maximally mixed state. Essentially, we will see in Section VII that if one allows any other ancilla, then all transition rates become infinite. This fixes the class of operations we will call noisy operations (NO). The class NO is therefore very natural, as it is the only one which gives non-trivial transition rates.

In entanglement theory, an entangled state of Schmidt rank 2 represents the same resource whether it acts on a Hilbert space $`C^2C^2`$ or on a larger space $`C^dC^d`$. This is because embedding a state into a larger Hilbert space is equivalent to adding local ancillas in a pure state. In our case, a state acting on a Hilbert space $`C^2`$ is not the same resource as the one acting on $`C^d`$. This is because adding ancilla in pure state is adding a new resource.

## III Optimal transitions under noisy operations - single copy case

In this section we will present a protocol to transform single copies of states into each other by diluting them with noise. We will show that the transition from a single copy of $`\varrho `$ to a single copy of state $`\sigma `$ is possible if and only if the latter is more mixed than the former. This is provided the Hilbert space is the same for both states, i.e. they occupy the same number of qubits. We will also consider the transitions between systems of different number of qubits. One then has to add maximally mixed ancillas to one of the systems (or to both), so that the number of qubits become equal. Then we can apply the above criterion. The term “more mixed” Uhlmann (1971) has the following meaning: For states $`\varrho `$ and $`\varrho ^{}`$ on the Hilbert space $`=C^d`$, we say that $`\varrho `$ is more mixed than $`\varrho ^{}`$ ($`\varrho \varrho ^{}`$) if their eigenvalues in decreasing order satisfy $`_{i=1}^k\lambda _k_{i=1}^k\lambda _k^{}`$, for all $`kdim`$. (In the same way, one can say that some probability distribution is more mixed than another one). If the state is more mixed, its eigendistribution is more spread. The order introduced by the relation “$``$” has a largest element – the maximally mixed state. It is easy to see that it is more mixed than any other state.

Let us now prove the main result of this section.

###### Proposition 1

For states $`\varrho `$ and $`\sigma `$ of $`d`$-level systems the transition $`\varrho \sigma `$ by NO is possible if and only if $`\varrho \sigma `$.

Proof.$``$” follows from the fact Chefles  that $`\sigma \varrho `$ iff there exists a bistochastic map bis  that maps $`\varrho `$ into $`\sigma `$. Since noisy operations (for equal input and output dimensions) are bistochastic, then $`\varrho \sigma `$ implies $`\sigma \varrho `$. To prove “$``$” we cannot use the result of Chefles , because we do not know if the existing map can be taken to be noisy operations. Instead we will construct the map explicitly. Let us then assume that $`\sigma \varrho `$. First we can always rotate $`\varrho `$ unitarily, so that it commutes with $`\sigma `$. Thus we can assume without loss of generality that the states commute. We can now use the fact Bhatia (1997) that if probability distribution $`\{q_i\}`$ is more mixed than $`\{p_i\}`$, then the former can be obtained from the latter via a mixture of permutations, i.e.

$$q_i=\underset{j}{}\alpha _jp_{\sigma _j(i)}$$
(1)
where $`_j\alpha _j=1`$, while $`\sigma _j`$ are permutations of indices of the probability distribution. Let then $`p_i`$ be the eigenvalues of $`\varrho `$ and $`q_i`$ \- eigenvalues of $`\sigma `$. We will consider state $`\varrho \tau _N`$ (where $`\tau _N`$ is an added maximally mixed state of dimension $`N`$) and construct some permutation of eigenvalues of the latter density matrix. After such permutation, and removing the ancilla, the state will approach $`\sigma `$ for large $`d`$. For simplicity we will assume that there are only two permutations $`\sigma _1`$ and $`\sigma _2`$, so that $`q_i=\alpha p_{\sigma _1(i)}+(1\alpha )p_{\sigma _2(i)}`$.

The state $`\varrho \tau _N`$ consists of blocks, of dimensions $`N`$:

$$\frac{1}{N}(\underset{N}{\underset{}{p_1,\mathrm{},p_1}},\mathrm{},\underset{N}{\underset{}{p_d,\mathrm{},p_d}})$$
(2)
We will divide each block into two groups of entries: $`N_1`$ first entries and the rest $`N_2=NN_1`$ entries. Now we will apply permutation $`\sigma _1`$ to the first entries of each block. Similarly, we apply it to the second set of entries, and so on, in the first group. The second group is subjected to permutation $`\sigma _2`$ in a similar way. The resulting density matrix is

$$\frac{1}{N}(\underset{N_1}{\underset{}{p_{\sigma _1(1)},\mathrm{},p_{\sigma _1(1)}}},\underset{N_2}{\underset{}{p_{\sigma _2(1)},\mathrm{},p_{\sigma _2(1)}}}\mathrm{},\underset{N_1}{\underset{}{p_{\sigma _1(N)},\mathrm{},p_{\sigma _1(N)}}},\underset{N_2}{\underset{}{p_{\sigma _2(N)},\mathrm{},p_{\sigma _2(N)}}})$$
(3)
Now we trace out the ancilla. This means that we sum all elements of each block, and instead of the block, take the resulting number. The obtained eigendistribution is given by

$$\stackrel{~}{q}_i=\frac{N_1}{N}p_{\sigma _1(i)}+\frac{N_2}{N}p_{\sigma _2(i)}.$$
(4)
Choosing large $`N`$ and suitable $`N_1`$, $`N_2`$ one can approach $`\alpha `$ and $`1\alpha `$ with arbitrarily high accuracy. This ends the proof of the proposition.

## IV Optimal transitions under noisy operations - asymptotic regime

Here we will consider asymptotic transitions of type

$$\varrho ^n\sigma ^{m_n}$$
(5)
Usually it is not possible to obtain a perfect state $`\sigma ^{m_n}`$ from $`\varrho ^n`$ even if an arbitrarily large amount of copies can be used. It is however possible to obtain the state $`\sigma _n`$ that will asymptotically converge to $`\sigma ^{m_n}`$

$$\varrho ^n\sigma _n\sigma ^{m_n}$$
(6)
Thus we allow for inaccuracy, provided it vanishes in the limit of large $`n`$. The fidelity can be measured by the trace norm, i.e. one requires that

$$\sigma _n\sigma ^{m_n}0\text{for}n\mathrm{}.$$
(7)
The rate of given protocol of asymptotic $`\varrho \sigma `$ transition is given by the asymptotic ratio $`lim_n\frac{m_n}{n}`$. The optimal transition rate denoted by $`R(\varrho \sigma )`$ is given by supremum over rates attainable by protocols that satisfy the asymptotic accuracy condition (7).

### IV.1 Conversion from mixed to pure states

We will now consider the optimal rate for transition to the one qubit pure state $`\pi `$ i.e. $`\varrho \pi `$. We will show that if $`\varrho `$ is a state of $`d`$-level system then

$$R(\varrho \pi )=I(\varrho )$$
(8)
where $`I=NS(\varrho )`$ with $`N=\mathrm{log}d`$ being the amount of qubits occupied by the state $`\varrho `$. In other words, the transformation from pure states to mixed states is reversible, in the sense that the number of pure states which is needed, or which can be obtained is the same. The proof could be just use of Schumacher compression Schumacher (1995), however with a different interpretation (similar to that in Schulmann and Vazirani ). We will also show that conversely, the amount of copies in state $`\varrho `$ that can be obtained under $`NO`$ per input pure qubit is also equal to $`I`$. The proofs will be similar to the reasoning of Nielsen in Nielsen (1999) where he derived asymptotic rates of pure state entanglement manipulations from single copies based on majorization.

We will use law of large numbers Cover and Thomas (1991); Schumacher (1995), that implies that there exists a subset of eigenvalues of $`\varrho ^n`$ call the typical set $`TYP`$ with useful properties. More precisely, given $`ϵ,\delta >0`$, there exists large enough $`n`$, and the set $`TYP`$ of eigenvalues such that

$`{\displaystyle \underset{p_iTYP}{}}p_i1ϵ`$ (9)
$`2^{n(S+\delta )}p_i2^{n(S\delta )}\text{for}p_iTYP`$ (10)
These are thus the eigenvalues that carry almost the whole weight and they are more or less uniform. One can consider two states $`\varrho _{typ}`$ and $`\varrho _{atyp}`$, given by

$$\varrho _{typ}=\frac{1}{c}\underset{p_iTYP}{}p_i|ii|,\varrho _{atyp}=\frac{1}{1c}\underset{p_iTYP}{}p_i|ii|$$
(11)
where $`|i`$ are eigenvectors corresponding to $`p_i`$, and $`c=_{p_iTYP}p_i`$ is a normalization constant. Clearly $`\varrho ^n`$ is a mixture of those states

$$\varrho ^n=c\varrho _{typ}+(1c)\varrho _{atyp}$$
(12)
Since $`c1ϵ`$ one finds that $`\varrho _{typ}`$ is close to $`\varrho ^n`$:

$$\varrho _{typ}\varrho ^n2ϵ$$
(13)
Thus it suffices to use $`\varrho _{typ}`$ instead of $`\varrho ^n`$. Let us first show that one can convert $`\varrho _{typ}`$ into approximately $`n(NS)`$ copies of pure qubits. To this end, note that the eigenvalues of $`\varrho _{typ}`$ satisfy:

$$\lambda _i\frac{p_i}{c}\frac{1}{c}2^{n(S+\delta )}.$$
(14)
Thus $`\varrho _{typ}`$ is less mixed than the state $`\varrho _{out}`$ with eigenvalues

$$\{\underset{D}{\underset{}{\frac{1}{D},\mathrm{},\frac{1}{D}}},\underset{d^nD}{\underset{}{0,\mathrm{},0}}\},$$
(15)
where $`D`$ is given by

$$D=\frac{1}{\frac{1}{c}2^{n(S+\delta )}}$$
(16)
(the eigenvectors of $`\varrho _{out}`$ are irrelevant, as we can perform any unitary transformation for free). Both of the states act on a $`d^n`$ dimensional space, so that we can apply our Prop. 1. Thus it is possible to go from $`\varrho _{typ}`$ to $`\varrho _{out}`$ via noisy operations. If we choose $`D`$ to be larger than in eq. (16), namely so that it is a power of $`2`$, the transition is still possible. The smallest such $`D`$ satisfies $`\mathrm{log}D=n(S+\delta )n(S+\delta )+1`$. Then the state $`\varrho _{out}`$ represents exactly the tensor product of $`\mathrm{log}D`$ qubits in maximally mixed state and $`n\mathrm{log}d\mathrm{log}Dn(\mathrm{log}dS\delta )1`$ qubits in pure states. Thus one can remove the mixed qubits, and keep the obtained pure qubits. Call the obtained state $`\pi _{out}`$. The rate of the transition is the number of obtained pure qubits divided by $`n`$. For large $`n`$ this tends to $`\mathrm{log}dS\delta `$. Since $`\delta `$ can be chosen arbitrarily small, we obtain the optimal asymptotic rate equal to $`\mathrm{log}dS`$.

One could think that we obtain the pure qubits exactly. However, we used Proposition 1, where the transition is not exact, though arbitrarily precise.

Yet we have not transformed $`\varrho ^n`$ but $`\varrho _{typ}`$. We now take instead of $`\varrho _{typ}`$, the state $`\varrho ^n`$ and apply the same action, which transformed $`\varrho _{typ}`$ into the required amount of pure qubits (call the action $`\mathrm{\Lambda }`$). It is now easy to see that $`\mathrm{\Lambda }(\varrho ^n)`$ is close to a final state of pure qubits $`\pi _{out}`$. Indeed, we have

$$\mathrm{\Lambda }(\varrho ^n)\pi _{out}=\mathrm{\Lambda }(\varrho ^n)\mathrm{\Lambda }(\varrho _{typ})\varrho ^n\varrho _{typ}ϵ$$
(17)
where the second last inequality comes from the fact that completely positive trace-preserving maps are contractions on Hermitian operators in trace norms, i.e. $`\mathrm{\Lambda }(A)A`$ for Hermitian $`A`$ Ruskai (1994).

Now we should show that the converse is possible, i.e. to create a state $`\varrho ^n`$ it is sufficient to start with $`\mathrm{log}dS`$ pure qubits per output copy of $`\varrho `$. However, the proof is similar to the above. The only difference is that we now use the other part of eq. (10). Namely, we note that $`\varrho _{typ}`$ is more mixed than the state with eigenvalues

$$\{\underset{D^{}}{\underset{}{\frac{1}{D^{}},\mathrm{},\frac{1}{D^{}}}},\underset{d^nD^{}}{\underset{}{0,\mathrm{},0}}\},$$
(18)
where $`D^{}`$ is given by

$$D^{}=\frac{1}{\frac{1}{c}2^{n(S\delta )}}$$
(19)
Again, due to Proposition 1 we can turn $`\varrho _{typ}`$ into the latter state. Changing $`D^{}`$ into a suitable power of $`2`$ (so that it is smaller than $`D^{}`$ of the above equation hence passing from $`\varrho _{typ}`$ is still possible) one gets that the latter state is a tensor product of $`\mathrm{log}D^{}`$ qubits in maximally mixed states and approximately $`n(\mathrm{log}dS)`$ qubits in pure states.

Thus starting with $`n(\mathrm{log}dS)`$ qubits in a pure state, one has to add $`\mathrm{log}D^{}`$ qubits in the maximally mixed state, and pass to the state $`\varrho _{typ}`$ which can be made arbitrarily close to $`\varrho ^n`$ by choosing small $`ϵ`$.

### IV.2 Optimality of $`\mathrm{log}dS`$ transition rates and optimal mixed-mixed transition rates

We will now show that the obtained rates are optimal. We will follow Ref. Popescu and Rohrlich (1997) invoking standard thermodynamical reasoning concerning Carnot efficiency (cf. Bennett et al. (1996c)). Essentially, we will show that $`I=NS`$ cannot increase under NO maps, and then show that if our transitions are not optimal, one could increase $`I`$ under NO. We will use the reversibility of our protocol, and also the asymptotic continuity property of von Neumann entropy.

We will prove optimality by contradiction. Suppose that for the transition to pure qubits $`\varrho \pi `$ one can obtain a better rate than $`R(\varrho \pi )=NS`$ (where $`N=\mathrm{log}d`$, $`\varrho `$ acts on $`C^d`$). Then one can run the following transition

$$\pi \varrho \pi ,$$
(20)
and obtain a rate of such transition which is more than 1. In other words, employing $`n<m(NS)`$ pure qubits, according to the assumption, one gets $`m`$ pairs in state $`\varrho `$. Then one can apply the protocol of the previous section to the $`m`$ pairs of $`\varrho `$, to obtain $`m(NS)`$ pure qubits. Thus one would be able to increase the number of pure qubits from $`n`$ to $`m`$. Repeating the procedure one can obtain an arbitrary number of pure qubits.

Now, we have to show that this is impossible. This follows from the fact that $`NS`$ cannot increase under NO maps. Indeed, unitary maps do not change the quantity. Partial trace of one qubit decreases $`N`$ by 1, and can increase entropy at most by 1. Finally, adding a system in maximally mixed state, increases $`N`$ by 1, but also increases entropy by 1. Now, for $`m`$ pure qubits, $`NS=m`$, while for $`n`$ qubits we have $`NS=n<m`$, thus the function $`NS`$ must increase.

This is yet not the full proof, as we have made an implicit assumption, that the final qubits are exactly pure states. In fact it is not true, as all our conversions are only asymptotically true. However the von Neumann entropy is asymptotically continuous, namely for $`N`$ qubit states $`\varrho `$ and $`\sigma `$ we have Fannes (1973)

$$|S(\varrho )S(\sigma )|N\varrho \sigma +O(1)$$
(21)
In our case we take $`\varrho =\pi ^m`$ and $`\sigma _m`$ being the actual final state. We know then that $`S(\varrho )=0`$ and that $`\sigma _m\varrho `$ tends to zero as $`m`$ goes to infinity. Thus $`\frac{|S(\sigma _m)|}{m}0`$ for large $`m`$. Thus the density of the function $`I`$ tends to $`1`$ for the state $`\sigma _m`$. This density is also $`1`$ for the initial state $`\pi ^n`$. Thus we can write that in our process $`I_{out}=m_no(m_n)`$; on the other hand $`I_{in}=n`$. We will show that for large $`n`$, (which also implies that $`m_n`$ is large) $`I_{in}<I_{out}`$. Indeed that latter inequality is equivalent to the following set of equivalent inequalities

$`m_no(m_n)>n`$ (22)
$`{\displaystyle \frac{m_n}{n}}{\displaystyle \frac{o(m_n)}{n}}>1`$
$`{\displaystyle \frac{m_n}{n}}(1{\displaystyle \frac{o(m_n)}{m_n}})>1`$
The quantity inside the bracket tends to 1, while in our protocol $`\frac{m_n}{n}`$ goes to a number greater than one. Thus the inequality holds, which is impossible. Therefore our assumption that our rate is not optimal is incorrect. In a similar way one can show that one cannot obtain a better rate than

$$R(\pi \varrho )=\frac{1}{I}$$
(23)
while going from pure states to mixed ones.

Clearly since the transitions from mixed to pure states are reversible and optimal, one can use these protocols to go from one mixed state to another in a reversible and optimal way by just distilling pure states and then creating another mixed state. This gives that the optimal ratio of conversion between state $`\varrho `$ of a $`N`$ qubit system and state $`\sigma `$ of a $`N^{}`$ qubit system is equal to

$$\frac{R(\varrho \sigma )=NS(\varrho )}{N^{}S(\sigma ).}$$
(24)
## V Information monotones and the unique measure of information

Here we will derive the unique measure of information $`I`$, with virtually no assumptions. The derivation will be mostly operational. We will actually assume two properties. The first will concern the intuition of what information is – namely, noisy operations should not increase it. Indeed, information, whatever it is, shouldn’t be increased by unitary operations, by adding a qubit in maximally mixed state (supposed to be information-less) and discarding qubit (rather obvious requirement). Thus we postulate

Postulate 1. $`I`$ should be monotonic under noisy operations.

We will actually see in the next section, that this postulate is rigid, in the sense that if instead of noisy operations, we had chosen operations with a free resource other than maximally mixed states, the theory would be trivial, and all rates would be infinite.

The second assumption will not be connected with the expected properties of information. Rather it will display the properties any function used in the asymptotic regime (limit of many copies) should possess. I.e.

Postulate 2. $`I`$ is asymptotically continuous.

By asymptotically continuous, one means that for the state $`\varrho _N`$ and $`\sigma _N`$ of $`N`$ qubits, such that $`\varrho _N\sigma _N0`$ for $`N\mathrm{}`$. One would then require

$$|f(\varrho _N)f(\sigma _N)|0.$$
(25)
We then say that $`f`$ is asymptotically continuous. The motivation for this is that in the asymptotic regime, one identifies the states that asymptotically converge to each other. Thus the only relevant functions of states are those that also somehow identify those states. Of course in the asymptotic limit, the interesting functions become infinite, so that one has to pass to intensive quantities and divide by the number of copies to obtain densities. The relevant functions would be those whose densities converge on convergent sequences. Note that this not merely a technical requirement. Rather this follows from the basic assumption of the asymptotic regime - that similar states should be identified. The latter assumption is necessary, and physically natural - it is simply impossible to obtain exact transitions.

Let us now prove that there is a unique function that satisfies these two postulates.

The proof can be obtained from Refs. Donald et al. ; Horodecki (2001). According to Horodecki (2001) The following inequality is true

$$R(\varrho \sigma )\frac{f^{\mathrm{}}(\varrho )}{f^{\mathrm{}}(\sigma )}$$
(26)
where $`R`$ denotes the rate of transition under any given class of operations, and $`f`$ is an asymptotically continuous function nonincreasing under the class. The symbol $`\mathrm{}`$ stands for regularization. The regularization of function $`f(\varrho )`$ is $`M^{\mathrm{}}(\varrho )=lim_n\mathrm{}\frac{1}{n}M(\varrho ^n)`$.

Choosing as $`\sigma `$ the one qubit pure state $`\pi `$ and exchanging the roles of $`\varrho `$ and $`\sigma `$ we obtain

$`R(\varrho \pi ){\displaystyle \frac{f^{\mathrm{}}(\varrho )}{f^{\mathrm{}}(\pi )}}`$ (27)
$`R(\pi \varrho ){\displaystyle \frac{f^{\mathrm{}}(\pi )}{f^{\mathrm{}}(\varrho )}}`$
Denoting $`1/f^{\mathrm{}}(\pi )=a`$ we obtain

$$R(\varrho \pi )af^{\mathrm{}}(\varrho )\frac{1}{R(\pi \varrho )}$$
(28)
However we have explicit protocols which show that $`R(\varrho \pi )I`$ and $`1/R(\pi \varrho )I`$. Thus up to the constant $`a`$ we obtain that $`f^{\mathrm{}}=I`$. In this sense $`I`$ is the unique measure of information.

It is interesting to see how other measures of information are removed in the asymptotic limit. Suppose that we consider measures of information which only satisfying the first postulate. Since we see that everything is very similar to the problem of pure state entanglement, one is not surprised that all monotones under NO are so called Shur concave functions of the density matrix. In particular there is a set of information measures (or ”monotones”) which is enough to determine if a transition is possible. These are the so called Ky Fan k-norms, i.e. sums of the first $`k`$ largest eigenvalues. By definition of the “more mixed” condition, we have $`\varrho \sigma `$ iff for all $`k`$-norms, $`\varrho _k\sigma _k`$. Thus the process $`\sigma \varrho `$ is possible iff in the process no monotone increases.

One might get the feeling that there is some contradiction here. Namely, in asymptotic transitions, the only restriction for the rate is the monotone $`I`$. Thus there are allowed transitions for which other monotones increase. Indeed, we say that $`\varrho ^n\sigma ^m`$ is possible, though it is clear that some of the monotones will increase. The solution is that, in fact we are not talking about exact transitions. Thus in the actual transition, the final state obeys the nonincreasing of monotones. For that state, all monotones are not greater than for the initial state. The monotones are however not asymptotically continuous, and they see differences between that actual state, and the required state $`\sigma ^m`$. The only monotone that does not see the difference is $`I`$. Therefore only this function survives in the asymptotic limit.

### V.1 The choice of free resource is unique

One could think that the way we have obtained the information measure is not fully operational, as we assumed, somewhat arbitrarily that the free resource is the maximally mixed state. Here we will show that this is the only reasonable choice, if we want to allow ancillas at all, and if the theory is to be nontrivial i.e. the transition rates are finite, and therefore, not all states can be obtained for free. We thus assume that our operations include unitary transformations, and partial trace, and will try to play with third component - adding ancillas.

Suppose that instead of maximally mixed states $`\tau `$, we chose any other state $`\varrho _0`$ as a free resource. This means that we can use arbitrarily many copies of this state. From $`\varrho _0^n`$ we can produce without use of noise pure states by Schumacher compression Schumacher (1995); Schulmann and Vazirani  (in this paper we have not described this - we always used noise). Thus we have pure states for free. From pure states we can produce noise by entangling two qubits in a maximally entangled state and rejecting one qubit. The remaining one will be in a maximally mixed state. This is not very efficient: we spend two qubits in a pure state to get one qubit of noise. However pure states are for free, hence this method is sufficiently good in our situation. Now we have both noise and pure states for free, hence via the protocol described in the previous section, we can create any state. The theory becomes trivial - all states are for free; all rates are infinite. Thus if we allow adding systems for free at all, we can only add ones in maximally mixed state. We thus see that Postulate 1 is rather rigid, in the sense that changing it to a class of operations which allows any other ancilla, will result in a trivial theory.

## VI Reversibility and irreversibility

Note that we have a kind of reversibility: the amount of pure qubits that can be drawn from a given state is equal to the amount we need to create the state. Let us consider another situation, where we count everything (no free resource). we then see that there is basic irreversibility: transitions from almost any state $`\varrho `$ to any other state is irreversible. For example, one can draw $`I`$ pure qubits from $`\varrho `$, but to create $`\varrho `$, one needs many more pure qubits. There are two reasons for this. The first reason is trivial - to get $`N`$ qubits in state $`\varrho `$ one needs $`N`$ qubits anyway. This is 1 qubit per output qubits, which is already more than $`I=NS(\varrho )`$. Now, however, even more pure qubits are needed. Namely, the output state has nonzero entropy. However the only way of producing entropy out of pure states is rather wasteful: one entangles two qubits, and removes one of them (as already described in the previous section). Indeed, previously, we had a free source of entropy - maximally mixed states, now we have only pure states to our disposal, and we count them.

Interestingly, in the classical world there is no way to produce entropy at all. Therefore in classical statistical mechanics, one has to assume mixed state from the very beginning. Quantum mechanics allows one to produce mixed states out of pure ones. This may lead one to prefer Bayes concept of probability.

We will now show that

###### Proposition 2

$`N+S`$ pure qubits are necessary and sufficient to produce $`\varrho `$ if one doesn’t have access to noise.

That this is sufficient can be seen by noting that $`\varrho `$ can be creating by preparing the purification of $`\varrho _{typ}`$. We thus consider a pure state of two systems $`A`$ and $`B`$. Subsystem $`A`$ has $`N`$ qubits, and its state is $`\varrho _{typ}`$. The state of subsystem $`B`$ (the purification) is also $`\varrho _{typ}`$, but we do not need it to be an $`N`$ qubit system, but rather want it to use the smallest possible amount of qubits. The latter is equal to $`S`$ qubits. Thus $`N+S`$ qubits in pure state are needed to prepare $`\varrho _{typ}`$ (preparation is discarding the system $`B`$). That this number of qubits are necessary simply stems from the fact that we start from an initially pure state, so to get a mixed state we must trace out part of the initial system, and the “garbage” that gets traced out must have at least $`S`$ qubits (since the number of qubits of garbage cannot be less than it’s entropy, and the garbage must have entropy $`S`$ since the system is initially pure). We must also have at least $`N`$ qubits left over to form the state. So, in general, to create the N qubit state $`\varrho `$ we need $`N+S`$ pure qubits, but we can draw only $`NS`$ qubits. The “information of preparation” is much greater than ”information of distillation”. During the transition

$$\psi \varrho \psi $$
(29)
we lose $`2S`$ pure qubits.

###### Proposition 3

To produce the mixed-mixed transition $`\varrho \sigma `$, without access to noise, $`\mathrm{\Delta }N+\mathrm{\Delta }S`$ qubits are necessary and sufficient where $`\mathrm{\Delta }NN(\sigma )N(\varrho )`$ and $`\mathrm{\Delta }SS(\sigma )S(\varrho )`$

To see these resources are necessary, we note that a general protocol involves an initial state $`\varrho |\psi \psi |`$, where $`|\psi `$ is some initial pure state. One then performs unitaries to give a state $`\varrho ^{}`$, and then one traces out the garbage $`g`$ to leave the state $`\sigma `$. We can then use the triangle inequality

$$|S(\sigma )S(g)|S(\varrho ^{})=S(\varrho )$$
(30)
to see that the number of garbage bits traced out $`N(g)`$ satisfies $`N(g)S(g)\mathrm{\Delta }S`$ (if $`S(g)S(\sigma )`$ then trivially $`S(g)\mathrm{\Delta }S`$. So, we need a minimum of $`N(\sigma )+\mathrm{\Delta }S`$ pure qubits to create $`\sigma `$, but we already had $`N(\rho )`$ bits to start, so the minimum amount of additional qubits needed is $`\mathrm{\Delta }N+\mathrm{\Delta }S`$.

The protocol which realizes this bound is to reversibly distill $`\varrho `$ into $`N(\varrho )S(\varrho )`$ pure qubits and $`S(\varrho )`$ bits of noise in a manner which we shall shortly describe. We then add in an additional $`\mathrm{\Delta }N\mathrm{\Delta }S`$ pure qubits. However, we also need $`\mathrm{\Delta }S`$ bits of noise, which costs $`2\mathrm{\Delta }S`$ pure states (this is the only part of the protocol which is irreversible). We then create $`\sigma `$ reversibly as described in the previous section, using the $`\mathrm{\Delta }N+\mathrm{\Delta }S`$ additional qubits.

The distillation procedure can be realized using a scheme similar to quantum data compressionSchumacher (1995) and to the concentration of entanglement scheme of Ref. Bennett et al. (1996c) (here however, the procedure is applied to the entire state). The protocol is essentially a projective measurement onto blocks proportional to the identity. On average, the size of the Hilbert space that the state is projected onto will be of size $`S(\varrho )`$, and so, the state can then be unitarily rotated to leave $`N(\varrho )S(\varrho )`$ pure states. We will explicitly give the protocol for $`n`$ qubits i.e. $`N(\varrho )=1`$ but the extension to higher dimensional states is straight-forward.

We can write the state in the eigenbasis which we label as $`0`$ and $`1`$, i.e. $`\varrho =a|0+b|1`$. We have have $`n`$ copies, i.e. we operate on the state $`\varrho ^n`$, and then we measure how many zeros this state has. This is a measurement with $`n+1`$ outcomes and it will yield a result $`k=0,\mathrm{},n`$ telling us how many zeros there are. This projects us onto a state which has $`d_k=\left(\genfrac{}{}{0pt}{}{n}{k}\right)`$ basis vectors, all with equal coefficients. I.e. it is proportional to the identity. The probability of finding a particular outcome $`k`$ is $`p_k=\left(\genfrac{}{}{0pt}{}{n}{k}\right)a^{2k}b^{2(nk)}`$ and since it does not in general span the entire Hilbert space, can be unitarily transformed to yield $`I_k=n\mathrm{log}d_k`$ pure states.

Each process $`\varrho \{p_k,\rho _k\}`$ after which $`I_k`$ pure states is extracted from $`\rho _k`$ with probability $`p_k`$, provides

$$N_o=\underset{k}{}p_kI_kH(\{p\})$$
(31)
total pure states. The Shannon entropy $`H(\{p\})`$ of distribution $`\{p_k\}`$ equals the cost of the erasure of information which allows us to work with an ensemble of $`\rho _k`$’s Landauer (1961). Thus we need $`I_{er}=H(\{p\})`$ bits of erasure to pay for the next part of the scheme, in which they draw $`_kp_kI_k`$ pure states. This quantity, which is of order $`\mathrm{log}n`$ is negligible in the large $`n`$ limit. We can divide the above equation by $`n`$ to obtain the amount of extractable pure states per qubit.

$$N_o/n=1S(\varrho )$$
(32)
where the erasure cost has been neglected since it is of order $`\mathrm{log}n/n`$. This completes our proof of the proposition.

This allows one to think of states in the following way: the mixed state consists of $`NS`$ bits of information and $`S`$ bits of noise. Thus to produce it one needs $`NS`$ qubits in pure states, to account for information, and $`2S`$ qubits to produce noise. Indeed one bit of noise costs two pure qubits - since noise is produced by rejecting part of entangled system.

It is interesting that one needs to add a free resource (noise) in order to achieve efficient transitions from pure to mixed states which are much less “useful” than mixed-to-pure transitions. Indeed, the latter is a task that can be associated with such actions as cooling, error-correction, increasing signal. This useful task can be performed without the help of an additional resource at the optimal rate. Only the converse direction, which is not useful (who wants to have mixed states instead of pure ones?) needs noise, and is much less efficient without noise.

There are other cases where reversibility needs noise. For example according to the Shannon second theorem, one can simulate one use of noiseless channel by $`1/C`$ uses of a noisy channel of capacity $`C`$. However, one cannot do the converse, i.e. simulate noisy channels by noiseless one, without sharing random correlated data Bennett et al. . Again, the useful task does not need any additional resource, while the useless task needs one. This is clear, if one realizes that in both situation we deal with dilution of some valuable resource into noise. Similarly in thermodynamics, the the thermodynamical system with difference of temperature can be thought as being “pure energy” (such as mechanical energy) diluted into “pure heat”. To draw work out of it one does not need any additional resource. However to create the system of heat baths efficiently, one needs a heat reservoir at the beginning. Otherwise, one has to spend work to produce heat, exactly as we needed to spend pure states to produce noise.

## VII Discussion: comparison with entanglement transformations

The paradigm discussed in this paper may be useful to understand the problems of entanglement theory. As one knows there is a basic irreversibility in entanglement transformations. We deal there with bipartite systems, shared by distant parties. One is interested in how many pure singlets are needed to form a state $`\rho _{AB}`$ (the entanglement cost, and also, how many singlets can be obtained from the state (the distillable entanglement). If $`\rho _{AB}`$ is pure, then the entanglement cost is equal to the distillable entanglement in the limit of many copies of $`\rho _{AB}`$ Bennett et al. (1996c). The tranformations are reversible. However it is known that for a number of mixed states, the distillable entanglement is not equal to the entanglement cost Vidal and Cirac (2001). One has irreversibility. It has generally been assumed that this is because one is making transformations between pure states (in this case, singlets), and the mixed state $`\rho _{AB}`$. One therefore expects some information loss. However, as we have seen here, one can make transformations between pure and mixed states completely reversible, provided one has access to noise. And indeed, in the paradigm of entanglement theory, there is no reason why two distant parties couldn’t share some initial noisy resource. There is no special apriori reason for irreversibility in entanglement theory. It is therefore interesting to compare the situation discussed here, with that of entanglement theory. This comparison is summerized in the following table, and described below

| Paradigm | Class of Operations | Free Resource | Expensive Resource | Reversible? |
| --- | --- | --- | --- | --- |
| information | NO | maximally mixed states | pure states | yes |
| pure state entanglement | LOCC | separable states | singlets | yes |
| mixed state entanglement | LOCC | separable states | singlets | no |
| thermodynamics | adiabatic processes | heathea | work | yes |
| ToEtoe  Horodecki et al. (2002) | LOCC + PPT states | PPT states | singlets | no (?) |
| PPT Adenaert et al. | PPT operations | PPT states | singlets | in some cases |

Instead of NO, in entanglement theory we have there LOCC, which means that 1) arbitrary local unitary operations can be performed, 2) any local ancilla can be added, 3) any local partial trace can be performed 4) qubits can be communicated between distant parties only via a dephasing channel. The role of noise is played by separable states - all the states that can be produced for free within the allowed class of operations are a free resources. The role of pure states is played by pure entangled states.

One could imagine that like with ”local information theory”, in entanglement theory, any state is a reversible mixture of two phases: pure entanglement and a separable noisy phase. One should be able to draw the same amount of pure entanglement from a given state as is needed to produce it. Creation of mixed states would be reversible dilution of pure entanglement into mixed, separable states.

In this simple picture we would have only two kinds of basic elements in entanglement theory: pure entangled systems and disentangled systems. One is useful, the other - useless. A state which is neither pure entangled nor disentangled, consists of those two basic elements. This is in parallel to the paradigm presented in this paper, where the useful elements were pure states, the useless maximally mixed ones.

As noted, such a situation exists for pure states, where we can reversibly concentrate and dilute entanglement. However, such a situation does not exist with mixed states in entanglement theory. What is the basic difference between mixed state entanglement and the paradigms (I) of pure entanglement, and (II) the present NO one?

In both I and II we have the following common point. We define states that can be added for free, and then the class of operations. Then in both cases it turns out that the free states remain the only nontrivial set of states closed under the class of operations. Now in mixed state entanglement we may have another basic element - bound entangled ones. One cannot obtain them from separable states, but also one cannot obtain any pure entanglement from them. Thus the set of states closed under the class of operations is greater than it would seem from the construction of the paradigm. Thus in situations I and II we have only two elements: useful and useless. In paradigm II the useful element is information, the useless one - noise. In paradigm II - the useful element is entanglement, the useless - separability. Here, entanglement itself is divided into at least to phases: bound and pure. From bound entanglement we cannot make pure, so call it useless as well. Thus we can have states that have entanglement, but are useless. This is different than I and II, but similar to thermodynamics: we have there two forms of energy, useful and useless. In Ref. Horodecki et al. (2002) we have asked a question - is it possible that mixed-state entanglement is like thermodynamics. There would be three basic elements: separable states (no entanglement), bound entanglement and pure entanglement, similarly as in thermodynamics there are states without energy, with disordered energy (single heat bath) and with ordered energy (mechanical energy). All three kinds could be reversibly mixed.

In Horodecki et al. (2002) it was shown that such a picture can be treated as a sort of “first order approximation” rather than full description of asymptotic bipartite entanglement. Related questions were studied in Ref. Adenaert et al.  where reversibility for some states holds, if so called PPT superoparators are allowed Rains (1999). The relation between the latter result and the “thermodynamic” approach of Ref. Horodecki et al. (2002) goes beyond the scope of this paper and is explained in Horodecki et al. (2002) itself.

## VIII Conclusion

Contrary to what might be imagined, we have shown that mixed states do not necessarily impose irreversibility. One can reversibly transform pure states into mixed ones, provided one has access to random noise. This defines a class of operations (NO) which can then be used to explore the transition rates between various states. It is found that the information measure $`I=NS`$ cannot decrease under NO, and is therefore the unique asymptotically continuous measure of information. It would be extremely interesting to explore other restricted classes of operations in addition to $`NO`$, to see whether there are other non-trivial theories. Exploring the connection between this, and the LOCC paradigm of entanglement theory, would be extremely useful in understanding entanglement in distributed quantum systems. Perhaps ideas along the lines of Horodecki et al. (2002) may prove fruitful.

###### Acknowledgements.

MH and PH thank Ryszard Horodecki and JO thanks Jacob Bekenstein for numerous discussions on the notion of information. This work is supported by EU grant EQUIP, Contract No. IST-1999-11053. JO acknowledges the support of the Lady Davis Fellowship Trust, and grant No. 129/00-1 of the Israel Science Foundation.


text:
# Coexistence of 𝑠-wave Superconductivity and Antiferromagnetism

## Abstract

We study the phase diagram of a new model that exhibits a first order transition between s-wave superconducting and antiferromagnetic phases. The model, a generalized Hubbard model augmented with competing spin-spin and pair-pair interactions, was investigated using the projector Quantum Monte Carlo method. Upon varying the Hubbard $`U`$ from attractive to repulsive we find a first order phase transition between superconducting and antiferromagnetic states.

Experimental phase diagrams with superconducting and magnetic phases in close proximity continue to fascinate since the broken symmetry states are incompatible. In particular, a canonical two-dimensional example is the layered organic superconductor $`\kappa `$-(BEDT-TTF)2Cu\[N(CN)2\]Cl which shows a first order transition between antiferromagnetic (AF) insulating and superconducting (SC) phases upon varying the pressure.Lefebvre  Debate continues about the nature of the superconducting state. Kanoda et al. argue that NMR data are consistent with an unconventional superconducting gap with nodal lines.Kanoda  Conversely, many experimental studies are rather consistent with s-wave, phonon mediated superconductivity. In particular, Kini et al. could demonstrate a BCS-like mass isotope effect in $`\kappa `$–S.Kini  The same material exhibits a strong superconductivity induced (acoustic) phonon renormalization. Pintschovius  Nodes in the pair order parameter are also incompatible with specific heat measurements.Muller

In order to model the scenario of a phase transition between an AF and an s-wave SC on a half-filled two dimensional lattice we add to the standard Hubbard model a pair hopping term:

$`H`$ $`=`$ $`t{\displaystyle \underset{\stackrel{}{i},\stackrel{}{j},\sigma }{}}(c_{\stackrel{}{i},\sigma }^{}c_{\stackrel{}{j},\sigma }+H.c.)+U{\displaystyle \underset{\stackrel{}{i}}{}}n_{\stackrel{}{i},}n_{\stackrel{}{i},}`$
$``$ $`t_p({\displaystyle \underset{\sigma }{}}c_{\stackrel{}{i},\sigma }^{}c_{\stackrel{}{j},\sigma }+H.c.)^24V{\displaystyle \underset{\stackrel{}{i},\stackrel{}{j}}{}}\eta _\stackrel{}{i}^z\eta _\stackrel{}{j}^z`$
where $`\stackrel{}{i}`$ labels the sites of a square lattice and the first sum runs over nearest neighbor bonds. The fermionic spin is given by $`\stackrel{}{S}_\stackrel{}{i}=\frac{1}{2}_{s,t}c_{\stackrel{}{i},s}^{}\stackrel{}{\sigma }_{s,t}c_{\stackrel{}{i},t}`$ and $`\stackrel{}{\sigma }`$ denotes the Pauli matrices. For a dimer the pair hopping term arises exactly when we assume a Su-Schrieffer-Heeger electron-phonon interaction Su80  and integrate out the phonon in the antiadiabatic limit. We introduce a particle-hole transformation $`𝒫`$ with properties $`𝒫c_{\stackrel{}{i},}𝒫=c_{\stackrel{}{i},}`$, $`𝒫c_{\stackrel{}{i},}𝒫=(1)^\stackrel{}{i}c_{\stackrel{}{i},}^{}`$ and $`𝒫^2=𝒫`$. Next we define the pairing operators as Zhang  $`\stackrel{}{\eta }_\stackrel{}{i}=𝒫\stackrel{}{S}_\stackrel{}{i}𝒫`$, the pair creation operator $`\eta _\stackrel{}{i}^{}=(1)^\stackrel{}{i}c_{\stackrel{}{i},}^{}c_{\stackrel{}{i},}^{}`$ and $`\eta _\stackrel{}{i}^z=(n_{\stackrel{}{i},}+n_{\stackrel{}{i},}1)/2`$ is the total charge. The pair hopping term may be recast Assaad01  as $`(_\sigma c_{\stackrel{}{i},\sigma }^{}c_{\stackrel{}{j},\sigma }+H.c.)^2=4(\stackrel{}{S}_\stackrel{}{i}\stackrel{}{S}_\stackrel{}{j}+\stackrel{}{\eta }_\stackrel{}{i}\stackrel{}{\eta }_\stackrel{}{j}\frac{1}{4}).`$ For the simulations, we have used the projector auxiliary field QMC algorithm which is well suited for the study of ground state properties Assaad01 . Simulations do not suffer from a sign problem in the region of attractive $`U<0`$ with the additional constraint $`U8|V|`$. This is the shaded region in Fig. 1. Using particle-hole symmetry the region of repulsive $`U`$ at $`V=0`$ is also accessible.

Two $`SU(2)_{S,\eta }`$ symmetry groups are generated by the spin algebra $`[S_\stackrel{}{i}^+,S_\stackrel{}{j}^{}]=2\delta _{\stackrel{}{i},\stackrel{}{j}}S_\stackrel{}{i}^z`$ and its particle-hole equivalent for the $`\eta `$ operators. Note that the commutator $`[\stackrel{}{S}_\stackrel{}{i},\stackrel{}{\eta }_\stackrel{}{i}]=0`$ because $`S_\stackrel{}{i}^\alpha \eta _\stackrel{}{i}^\beta =0`$. The hopping terms $`H_t`$ and $`H_{t_p}`$ are known to be invariant under spin rotation and also commute with the discrete symmetry $`𝒫`$. This in turn implies that $`\stackrel{}{\eta }_\stackrel{}{i}=𝒫\stackrel{}{S}_\stackrel{}{i}𝒫`$ also commutes with both hopping terms. The symmetries of the Hubbard term become apparent after putting it into the form

$$H_U=U/3\underset{\stackrel{}{i}}{}\left[\left(\stackrel{}{\eta }_\stackrel{}{i}\right)^2\left(\stackrel{}{S}_\stackrel{}{i}\right)^2\right].$$
(2)
We can read off the $`SU(2)_SSU(2)_\eta `$ symmetry and observe that the Hubbard term changes sign under $`𝒫`$ transformation. Zhang  In Fig. 1 the various symmetries for different parameter regions are displayed. Bars denote symmetries which we numerically find to be spontaneously broken in the thermodynamic limit. The point $`U=V=0`$ has the full symmetry: $`SU(2)_SSU(2)_\eta Z_{2,PH}`$ where $`Z_{2,PH}`$ denotes the discrete particle-hole symmetry. Here two scenarios are possible: i) Long range order for *both* AF and SC correlations since one implies the other through $`Z_{2,PH}`$ symmetry or ii) The competition between the two broken symmetry states leads to a disordered state. We find that the system realizes the first possibility of coexistence of s-wave SC and AF. Switching on $`U`$ breaks the particle-hole symmetry whereas $`V`$ reduces the $`SU(2)_\eta U(1)Z_{2,\eta }`$.

In the following, we will first discuss the phase transition at constant negative $`U`$ as a function of $`V`$ and then turn our attention to the phase transition at $`V=0`$ and varying $`U`$.

In the $`U\mathrm{}`$ limit the model is equivalent to hard-core bosons with repulsive nearest neighbor interactions. At half-filling this system experiences a transition from SC to charge-density wave states (CDW) going across $`V=0`$. Troyer  The transition point is marked by the higher symmetry $`SU(2)_\eta `$ and broken symmetry states may be labeled according to the direction of the magnetization. Therefore it is possible to find broken symmetry states which show a coexistence of CDW and SC order parameters. One can view this as a consequence of merging the Ising and the $`U(1)`$ symmetries into a continuous group.

The same behavior is still present for finite attractive $`U`$. In particular our simulations show (see Figs. 3b and 6b) that single particle excitations are always gapped so we can argue that the system still renormalizes to the bosonic model. As we will see, crossing the $`V=0`$ line at $`T=0`$, we observe a divergence of the correlation length (Fig. 2) which points to a second order phase transition. Furthermore, we find no sign of a discontinuity in the first derivative of the free energy $`(1/N)F/V=2n_\stackrel{}{i}n_{\stackrel{}{i}+\stackrel{}{x}}`$ (see Fig. 3a). At the same time we observe a jump for the CDW and SC order parameters at $`V=0`$. To understand this transition, we split it up into three parts: a) $`V0^{}`$, b) $`V=0^{}0^+`$ and c) $`V0^+`$. Part b) is responsible for the jump in the order parameters. Let us introduce the two limiting ground states via

$`\mathrm{\Psi }_{\mathrm{Ising}}`$ $`=`$ $`\underset{V0^{}}{lim}\underset{N\mathrm{}}{lim}\mathrm{\Psi }(V)`$ (3)
$`\mathrm{\Psi }_{\mathrm{XY}}`$ $`=`$ $`\underset{V0^+}{lim}\underset{N\mathrm{}}{lim}\mathrm{\Psi }(V).`$ (4)
The ground state in the Ising regime $`\mathrm{\Psi }_{\mathrm{Ising}}`$ has CDW order and the SC order parameter is zero. Jumping to positive $`V`$ and $`\mathrm{\Psi }_{\mathrm{XY}}`$ the situation reverses. Thus the observed jump in the order parameters is the simple consequence of forcing the transition from one broken symmetry state to the other: $`\mathrm{\Psi }_{\mathrm{Ising}}\mathrm{\Psi }_{\mathrm{XY}}`$. Next we look at the critical behavior as we approach the phase transition from either side. Linear spin wave theory (LSWT) predicts for both transitions a) and c) the same square root divergence for the respective transverse correlation function. In case c) the equal time transverse correlation function is $`n_\stackrel{}{Q}n_\stackrel{}{Q}`$ where $`n_\stackrel{}{Q}=(1/\sqrt{N})_\stackrel{}{r}e^{i\stackrel{}{Q}\stackrel{}{r}}n_\stackrel{}{r}`$, $`n_\stackrel{}{r}=n_{\stackrel{}{r},}+n_{\stackrel{}{r},}`$ and $`\stackrel{}{Q}=(\pi ,\pi )`$. According to LSWT this density-density correlation diverges like $`n_\stackrel{}{Q}n_\stackrel{}{Q}=8S/\sqrt{V/t_p}`$ as $`V0^+`$. The real part of the uniform susceptibility

$$\chi _{n,n}^{}(\stackrel{}{k}=\stackrel{}{Q},\omega =0)=_0^{\mathrm{}}𝑑\tau n_\stackrel{}{Q}n_\stackrel{}{Q}(\tau )$$
(5)
picks up the inverse of the gap $`\mathrm{\Delta }=8\sqrt{2Vt_p}`$ and in LSWT diverges like $`\chi _{n,n}^{}(\stackrel{}{Q},0)=\sqrt{1/2}S/V`$. Asymptotically the correlation function $`n_\stackrel{}{i}n_0(\tau )`$ decays exponentially in space and time thus the integrated correlation functions are proportional to the correlation length and gap

$`n_\stackrel{}{Q}n_\stackrel{}{Q}`$ $``$ $`\xi ^2`$ (6)
$`\chi _{n,n}^{}(\stackrel{}{k}=\stackrel{}{Q},\omega =0)`$ $``$ $`\xi ^2\mathrm{\Delta }^1.`$ (7)
Data for both $`\chi _{n,n}^{}(\stackrel{}{Q},0)`$ and $`n_\stackrel{}{Q}^zn_\stackrel{}{Q}^z(\tau =0)`$ are shown in Fig. 2 where the dotted line plots the LSWT result multiplied with a single constant to account for the reduced moment.

The ordered state in the XY regime has one Goldstone mode and the transverse correlations $`n_\stackrel{}{Q}n_\stackrel{}{Q}`$ are gapped. Approaching the critical point the gap closes and the $`n_\stackrel{}{Q}n_\stackrel{}{Q}`$ correlation length diverges. Thus critical behavior reflects the softening of the observed mode which turns into a Goldstone mode at the point with higher symmetry. Ultimately it is the softening of the transverse mode which is responsible for the observed critical behavior.

Following the $`V=0`$ line as $`U0`$ the bosonic LRO decreases only slightly leading to a finite limit at $`U=0^+`$ which is shown in Fig. 4. Crossing the $`U=0`$ point we encounter again a phase transition which is linked to a point with higher symmetry: the discrete particle-hole symmetry. Using the $`Z_{2,PH}`$ symmetry, one can map this bosonic LRO to an equivalent spin LRO for the repulsive $`U`$ case at $`V=0`$. Precisely at $`U=0`$ particle hole symmetry implies that bose correlation functions are equal to their spin counterparts

$$S_{\stackrel{}{k}+\stackrel{}{Q}}^\alpha S_{\stackrel{}{k}\stackrel{}{Q}}^\alpha =\eta _\stackrel{}{k}^\alpha \eta _\stackrel{}{k}^\alpha .$$
(8)
This explains a jump by a factor two for the density-density correlations as one moves from the symmetric point to a finite $`U`$ which is visible in Fig. 4. The emergence of a Goldstone mode above was associated with the critical behavior of the phase transition. As we are now approaching the $`U=0`$ point the only continuous symmetry available which is not associated with the bosonic LRO is the spin symmetry. In Fig. 5 we compute the correlation length for $`S_\stackrel{}{Q}^zS_\stackrel{}{Q}^z`$. This quantity shows no sign of divergence at the phase transition. Contrary to what happened in the SC to CDW transition we may classify this transition as a first order level crossing transition. From Fig. 6 we equally see that the derivative of the free energy with respect to $`U`$ is discontinuous. The free energy as a function of double occupancy has a plateau which marks a region of phase coexistence.

For the point $`U=V=0`$ we find coexistence of the spin and pair order parameters. After finite size extrapolation the results of Fig. 7 are consistent with a finite value of the magnetization $`m_s`$ up to weak coupling ($`t_p/t<<1`$). At the same time the superconducting order parameter $`\mathrm{\Delta }`$ is also nonzero and the measured value $`\mathrm{\Delta }=\sqrt{2}m_s`$ agrees with Eq. 8. The observed coexistence of AF and SC order is due to the special particle-hole symmetry $`Z_{2,PH}`$ at the point $`U=0`$ which renders the energies of both the AF and SC states degenerate.

In order to understand how the $`SU(2)_SSU(2)_\eta `$ symmetries are spontaneously broken we also need to discuss whether the discrete particle-hole symmetry is broken and how this affects the spontaneous breaking of the continuous symmetries. We introduce the following pseudo-spin order parameter

$`𝒮_\stackrel{}{i}`$ $`=`$ $`\left((2S_\stackrel{}{i}^z)^2(2\eta _\stackrel{}{i}^z)^2\right)\{\begin{array}{c}+1:|,|\\ 1:|,|0\end{array},`$ (11)
$`𝒮`$ $`=`$ $`𝒫𝒮𝒫=𝒮`$ (12)
which has to be zero as long as the $`Z_{2,PH}`$ symmetry is not broken as assumed in Eq. (12). A positive (negative) value for $`𝒮`$ indicates a majority of spins (pairs) in the system. Plotting the uniform correlations $`1/N𝒮_\stackrel{}{k}𝒮_\stackrel{}{k}(\stackrel{}{k}=0)`$ as a function of temperature, one sees in Fig. 8 that below a temperature $`T_c1.8t`$ particle-hole symmetry is indeed broken. Hence below $`T_c`$ and in the thermodynamic limit the $`Z_{2,PH}`$ particle-hole symmetry is broken and depending on the orientation of the pseudo-spin, $`𝒮_\stackrel{}{i}`$, the SC or AF ground state will be chosen.

In conclusion we have considered a model with competing interactions. The main ingredients in the model are on the one hand the Heisenberg and Hubbard terms which lead to a localization of single electrons thereby producing antiferromagnetic insulating states and on the other hand, pair hopping and nearest neighbor attractive terms which lead to on-site s-wave superconducting states. Based on the symmetries of the model as well as quantum Monte Carlo simulations we have shown that the model has a variety of phase transitions. In particular we have found a first order phase transition between an s-wave superconducting state and antiferromagnetic Mott insulator at a high symmetry point ($`U=V=0`$) where the two phases coexist.

We wish to thank the HLR-Stuttgart for generous allocation of computer time, the DFG for financial support (grant numbers AS 120/1-3 , AS 120/1-1 ) as well as a joint Franco-German cooperative grant (PROCOPE).