On bipartite unitary matrices generating subalgebra-preserving quantum operations

Introduction

States of finite dimensional quantum systems are described by trace one, positive semidefinite matrices called density matrices. Their evolution is given by completely positive trace preserving maps (CPTP), also called quantum channels. For closed systems, the Quantum channel consists in the left and right multiplication by a unitary matrix and its hermitian conjugate respectively. Quantum channels describing the evolution of a system in contact with an environment, the so–called open quantum systems, are given by more general CPTP maps. The famous Stinespring dilation theorem connects the mathematical definition of open system evolution quantum channels with their physical interpretation: the evolution of an open quantum system can be seen as the closed evolution of a [system + environment] bipartite system, followed by the discarding (or partial tracing) of the environment:

Hence, the quantum evolution depends on two physical relevant parameters: the global evolution operator $U$ and the state of the environment subsystem $\beta$. We would like to identify the part played by the unitary interaction $U$ in the properties of the quantum channel $T$. Namely, we would like to characterize families of bipartite unitary matrices $U$ such that the quantum channels $T$ they generate have some prescribed properties, independently of the environment state $\beta$. In this work, we answer this question for channels preserving some special sub–algebras of states/observables. Different channel properties were studied under the same framework in (see also ).

Part of the initial motivation of our study originates in the characterization of quantum channels preserving a set of pointer states. These CPTP maps appear in the context of quantum non demolition measurements . The following proposition is a discrete time version of [8, Theorem 3]. It is obtained through the repeated application of Theorem 7.1.

The operator $U$ is block–diagonal, i.e. there exists unitary operators $U_{1},\ldots,U_{n}\in\mathcal{U}_{k}$ such that

The implication (1)$\implies$(2) holds also if (1) is replaced by

The main goal of the current paper is to obtain similar characterization of the set of bipartite unitary operators giving quantum operations which preserve some structure on the input state or observable, such as diagonal matrices, tensor products, or other block-structures. One of our main results is a characterization of quantum channels creating no coherences between states of a prescribed basis. They therefore act essentially classically. More precisely we characterize bipartite unitary matrices generating CPTP maps preserving quantum states which are diagonal in the computation basis (see Theorem 4.4 for a precise statement):

The paper is organized as follows. In Section 2 we set up the problem we are studying, giving the necessary definitions. In Section 3 we gather some useful facts about partial isometries which shall be necessary later on. The next four sections represent the core of the paper and contain the results about, respectively, diagonal, block–diagonal, tensor product, and zero algebras. The proofs for the preservation of diagonal or block diagonal algebra and tensor product algebra use incompatible techniques, we thus do not provide a characterization of bipartite unitary matrices generating quantum channels preserving direct sum of tensor product sub–algebras. Section 8 contains some numerical recipes to sample from the sets of unitary operators considered in this paper. Finally, the Appendix contains the proof of the non–commutative Sinkhorn algorithm in the case where the blocks of the matrix are invertible.

Acknowledgments. I.N. would like to thank Teo Banica and Martin Idel for inspiring discussions around Sinkhorn’s algorithm and its different generalizations. The authors’ research has been supported by the ANR projects RMTQIT ANR-12-IS01-0001-01 and StoQ ANR-14-CE25-0003-01. Both authors acknowledge the hospitality of the Mathematical Physics Chair of the Technische Universität München, where this research was initiated.

Quantum channels and invariant subalgebras

We refer the reader to [16, Chapter 6] for a mathematical introduction to CP maps, and to [15, Chapter 8] or for a quantum information theory perspective.

Our ultimate goal will be to characterize bipartite unitary operators $U$ with the property that all the UCP maps $S_{U,\beta}$ (respectively all quantum channels $T_{U,\beta}$) preserve a $C^{*}$–algebra

Similar relations hold for channels in the Schrödinger picture. Note that the above diagram does not imply any obvious relations between the sets $\mathcal{U}^{(\mathcal{A}_{1},H/S)}$ and $\mathcal{U}^{(\mathcal{A}_{2},H/S)}$; some special cases of algebra inclusions will be investigated in Sections 5.3 and 6.3, to show that these sets are, in general, not comparable.

Structures arising from partial isometries

Partial isometries are characterized by the relation $R=RR^{*}R$ (or, equivalently, by the relation $R^{*}=R^{*}RR^{*}$). Let us remark right away that two important classes of operators, orthogonal projections and unitary operators, are partial isometries.

For all $i\neq j\in I$, we have $E_{i}\perp E_{j}$;

are partial isometries. Let $E_{ij}$ (resp. $F_{ij}$) be the initial (resp. final) spaces of the partial isometries $R_{ij}$. The matrix of partial isometries $R$ is said to be of type $(x,y,z,\ldots)$ if, in addition, the subspaces $E_{ij},F_{ij}$ satisfy the orthogonality conditions $x,y,z,\ldots$ from the list below:

A matrix of partial isometries is unitary iff it is of type (C2),(C3).

Let $R$ be a matrix of partial isometries of type (C2),(C3), with blocks $R_{ij}$. We have

where we have used again the direct sum hypothesis for the partition $\{F_{is}\}_{s\in[n]}$.

Reciprocally, consider now a unitary operator $U$ and represent it by blocks (which are partial isometries)

From the unitarity condition $UU^{*}=I_{nk}$, we get that, for all $i\in[n]$,

The proofs of the upcoming sections are based on the following lemma, due to Cochran .

From (4) again, we have that for every $i\in[n]$, $A_{i}^{*}A_{i}\leq I$, hence $A_{i}^{*}A_{i}\leq P_{E_{i}}$ since $A_{i}^{*}A_{i}$ is on the orthogonal of $E_{i}$. It follows that $\sum_{i=1}^{n}P_{E_{i}}\geq I$ by summing over $i$. Assume this last inequality is strict. From the rank inequality (5), $\sum_{i=1}^{n}{\rm rk}(A_{i})>k$ since ${\rm rk}(A_{i})=\dim(E_{i})$ by the Rank–nullity Theorem. Since we assumed that $\sum_{i=1}^{n}{\rm rk}(A_{i})=k$ from the contradiction we obtain $\sum_{i=1}^{n}P_{E_{i}}=I$. Multiplying on the left and right by a specific $P_{E_{j}}$ we obtain $\sum_{i\neq j}P_{E_{j}}P_{E_{i}}P_{E_{j}}=0$. Since this sum is a sum of positive matrices equal to , all the terms must be . Hence, the mutual orthogonality of the $E_{i}$’s follows.

From the mutual orthogonality of the $E_{i}$’s and the equality (4), for any $j\in[n]$,

Hence the $A_{i}$’s are partial isometries. ∎

We prove next a more specialized version of Cochran’s lemma.

It follows that the $F_{i}$’s are mutually orthogonal.

The diagonal algebra

We start with the most simple case, that of the diagonal subalgebra

From a physical perspective, this case is probably the most interesting one, and it is also very illuminating from a mathematical point of view. We shall treat separately the cases of CP maps which are unital (the Heisenberg picture) and trace preserving (quantum channels, the Schrödinger picture). Although the results in this section are special cases of the ones in Section 5, we state and prove them separately, in order to showcase the different ideas and techniques involved in the proof, which are more transparent in this case.

We are interested physical transformations of observables, that is in unital completely positive maps (UCP). More precisely, such maps can be written as

In the basis $\{e_{i}\}$, the operator $U$ is a matrix of partial isometries (and thus it is of type (C2),(C3)).

The easy implication, $(2)\implies(1)$, is proved by direct calculation. By our assumption, the blocks of $U$ are partial isometries, with initial and final spaces satisfying conditions (C2),(C3) from Definition 3.2

Since the blocks $U_{ij}$ satisfy condition (C2) from Definition 3.2, the operator $U_{sj_{1}}^{*}U_{sj_{2}}$ is null, unless $j_{1}=j_{2}$. Hence, the output $S_{U,\beta}(e_{s}e_{s}^{*})$ is a diagonal operator, proving the claim.

Let us now show $(1)\implies(2)$. Going through the computations above, without assuming anything about the blocks of $U$, we see that the condition that $S_{U,\beta}$ preserves the diagonal implies that for all $s,j_{1},j_{2}\in[n]$ such that $j_{1}\neq j_{2}$ and for all $\beta\in\mathcal{B}$,

Since $U$ is unitary, we moreover have, for all $s\in[n]$, $\sum_{j}U_{sj}U^{*}_{sj}=I_{k}$. From Cochran’s Lemma 3.4 (with $A_{j}=U_{sj}^{*}$) we deduce $\dim F_{s}\geq k$. Hence $\sum_{j}{\rm rk}(U_{sj})=k$ and the $U_{sj}$’s are partial isometries of type (C2).

Let us consider the simplest case, where $n=k=2$, and the partial isometries appearing as the blocks of $U$ have unit rank. The $4\times 4$ unitary operators which satisfy the conditions of the result above are of the form

satisfy the conditions in Theorem 4.1, since

2. The Schrödinger picture

The main result of this section is the following theorem, which characterizes unitary matrices preserving, independently of the ancilla state, the diagonal subalgebra of the system space.

In the basis $\{e_{i}\}$, the operator $U$ is a matrix of partial isometries of type (C2),(C3),(C4).

where $E_{ji}$ is the initial space of the partial isometry corresponding to the block $(j,i)$ of $U$.

The proof follows more or less the same steps as the proof of Theorem 4.1. Let us start with the easier implication (2) $\implies$ (1). Consider a basis element $e_{s}$ and compute

Since $U$ is of type (C3), we have $U_{js}^{*}U_{is}=\delta_{ij}P_{E_{is}}$, and thus

We prove now the second implication, (1) $\implies$ (2). Using equation (8), we obtain that $T_{U,\beta}(e_{s}e_{s}^{*})$ is a diagonal element iff

Since the above relation holds for a set of matrices $\beta$ which spans the full matrix algebra, we conclude that

Using the unitarity condition $U\in\mathcal{U}_{nk}$, we also have

giving rise to the following Markov transition matrix

Note that the matrix above has the general form of a $2\times 2$ stochastic matrix.

If moreover (C1) holds, the matrix $P$ is bistochastic.

The block–diagonal algebra

We shall consider two different block decompositions of the unitary interaction matrix $U\in\mathcal{U}_{nk}$: the usual one

Accordingly, let $\{E_{ab}\}_{a,b\in[N]}$ (resp. $\{F_{ab}\}_{a,b\in[N]}$) be the initial (resp. final) spaces of the matrices $U_{ab}$: $E_{ab}=(\ker U_{ab})^{\perp}$ and $F_{ab}=\operatorname{ran}U_{ab}$.

As before, we start with the Heisenberg picture of UCP maps, since the statement and the proof of the main result are easier. Note that the Theorem below generalizes Theorem 4.1, which corresponds to the particular case $d_{a}=1$ for all $a\in[N]$.

Let us show $(1)\implies(2)$. We initially follow the same path as for Theorem 4.1. By direct computation, it is easy to see that the hypothesis from (1) is equivalent to

It remains to prove the equivalence of (2) with this statement.

We can reformulate (11) in terms of matrices:

The proof of this equivalence amounts to taking specific matrices $X=e_{i}e_{j}^{*}$ and multiplying on the left and right by $e_{x}e_{x}^{*}\otimes I_{k}$ and $e_{y}e_{y}^{*}\otimes I_{k}$ respectively. We leave the details to the reader.

We now show that (12) implies a finer structure for the final spaces.

Then $\langle\phi,(X\otimes I_{k})\psi\rangle=0$ implies

Hence for all $i,j\in{\bf a},\phi_{i}\perp\psi_{j}$.

Let $\hat{F}_{ab}=\operatorname{linspan}\{\phi_{i}|\phi\in F_{ab},\phi=\sum_{i\in{\bf a}}e_{i}\otimes\phi_{i}\}$ and $\hat{F}_{ac}=\operatorname{linspan}\{\psi_{i}|\psi\in F_{ac},\psi=\sum_{i\in{\bf a}}e_{i}\otimes\psi_{i}\}$. We have $\hat{F}_{ab}\perp\hat{F}_{ac}$ and $F_{ab}\subset V_{a}\otimes\hat{F}_{ab}$ for all $b\in[N]$. We shall prove the converse inclusion.

At the level of examples, the identity and the flip operators from Example 4.3 satisfy also the conditions in Theorem 5.1.

2. The Schrödinger picture

We move now to the Schrödinger case. Since the proof follows closely what has been done in the previous sections, we only sketch the main ideas, leaving the details to the reader.

From direct computation, (1) is equivalent to

The implication $(2)\implies(1)$ proof is then identical to the one of Theorem 5.1. We thus only show the implication, $(1)\implies(2)$.

In terms of matrices, (13) is equivalent to,

Fix $a,b,c\in[N]$, $b\neq c$ such that $d_{b}\geq d_{c}$. Let,

Since for any $b\in[N]$, $\sum_{a\in[N]}U_{ba}U_{ba}^{*}=I_{d_{b}}\otimes I_{k}$ and for any $a\in[N]$, $\sum_{b\in[N]}U_{ba}^{*}U_{ba}=I_{d_{a}}\otimes I_{k}$, the fact that the matrices $U_{ab}$ are partial isometries implies (2) and (3) hold.

We now show that (14) implies a finer structure for the final spaces.

Then $\langle\phi,(X\otimes I_{k})\psi\rangle=0$ implies

Hence for all $(i,j)\in{\bf b}\times{\bf c},\phi_{i}\perp\psi_{j}$.

Let $\hat{F}_{ba}=\operatorname{linspan}\{\phi_{i}|\phi\in F_{ba},\phi=\sum_{i\in{\bf b}}e_{i}\otimes\phi_{i}\}$ and $\hat{F}_{ca}=\operatorname{linspan}\{\psi_{i}|\psi\in F_{ca},\psi=\sum_{i\in{\bf c}}e_{i}\otimes\psi_{i}\}$. We have $\hat{F}_{ba}\perp\hat{F}_{ca}$ and $F_{ba}\subset V_{b}\otimes\hat{F}_{ba}$ for all $b\in[N]$. We shall prove the converse inclusion.

3. Comparing subalgebras

In this section, we would like to investigate the relation between the sets

To show that $\mathcal{U}^{(\text{inv})}_{1}\nsubseteq\mathcal{U}^{(\text{inv})}_{2}$, consider the following operator

Obviously, the operator $U$ above satisfies the conditions (C2), (C3) from Definition 3.2, so $U\in\mathcal{U}^{(\text{inv})}_{1}$. However, for the equivalence relation $1\sim 2\nsim 3$ induced by the subalgebra $\mathcal{A}_{2}$, and the choice of indices $(i,j,x,y)=(1,2,2,3)$, equation (11) from the proof of Theorem 5.1 is not satisfied:

hence $U\notin\mathcal{U}^{(\text{inv})}_{2}$.

To show that the reversed inclusion also fails to hold, consider a unitary matrix $W\in\mathcal{U}_{4}$ partitioned in $2\times 2$ blocks $W_{ij}$:

We construct the following unitary matrix $U\in\mathcal{U}_{9}$:

The tensor product algebra

We now analyze the case where there is just one term in the direct sum in (3), that is

Let $U\in\mathcal{U}_{nk}$ be a bipartite unitary operator. The following are equivalent:

There exist unitary operators $V\in\mathcal{U}_{rk}$ and $W\in\mathcal{U}_{dk}$ such that

We first show $\eqref{it:tensor-product-S-ii}\implies\eqref{it:tensor-product-S-i}$. For an interaction unitary operator $U$ as in (16), we have

proving the claim; a graphical representation of the computation above can be found in Figure 1.

For the reverse implication, using linearity and the hypothesis, we find that there is a bi-linear function $f_{U}(X,\beta)$ such that

where we recognize two different dilations of a CP map. On the level of the Choi matrices, the equality above translates to

Let us set $W:=A^{\Gamma}$. Since $U$ is an unitary operator, we have

and thus $V^{*}V$ must have full rank, i.e. $V$ is an isometry; in particular, $s\leq k$. But then, $I_{drk}=W^{*}W\otimes I_{r}$, hence $W$ is also an isometry, implying $k\leq s$ . We have thus $s=k$, and $V,W$ are unitary operators, as claimed. ∎

Let us consider some special cases of the result above. In the $d=1$ or $r=1$ case, requiring that the algebra $\mathcal{A}$ should be preserved does not impose additional constraints, so we recover the set of all unitary matrices $\mathcal{U}_{nk}$. If $k=1$, the ancilla space is trivial, and the UCP map acts by unitary conjugation. It is clear then that the unitary operator $U$ must be a tensor product, $U=W\otimes V$, with $W\in\mathcal{U}_{d}$ and $V\in\mathcal{U}_{r}$.

2. The Schrödinger picture

Before stating our main result, we introduce the set of bipartite unitary operators with the property that their partial transpose is also unitary

This set has been studied in , and we refer the reader to that paper for additional properties of such unitary operators.

Let $U\in\mathcal{U}_{nk}$ be a bipartite unitary operator. The following are equivalent:

There exist unitary operators $V\in\mathcal{U}_{dk}$ and $W\in\mathcal{U}_{rk}\cap\mathcal{U}_{rk}^{\Gamma}$ such that

where $\omega$ is the maximally entangled state (15). The computation above is represented graphically in Figure 2.

as claimed; see Figure 3, right panel. From the trace preservation condition, we get that $V$ is an isometry, and thus $k\leq s$. We conclude that $k=s$, and thus both $V$ and $W$ are unitary operators. Asking that $UU^{*}=I_{dkr}$ yields $G^{\Gamma}$ unitary, proving the final claim and finishing the proof.

As in the Heisenberg case, we discuss next some special cases of Theorem 6.2. In the case where $r=1$, $\mathcal{A}$ is the full input matrix algebra, so we recover the set of all unitary matrices $\mathcal{U}_{nk}$. If $k=1$, the ancilla space is trivial, and the quantum channel acts by unitary conjugation; hence, $U$ must be a tensor product, $U=V\otimes W$, with $V\in\mathcal{U}_{d}$ and $W\in\mathcal{U}_{r}$. Finally, if $d=1$, we just require of the quantum channels $T_{U,\beta}$ to be unital, independently of the value of $\beta$; but this is precisely Theorem [11, Theorem 3.1]: the unitary operator $U$ must be such that its partial transpose is also unitary $U=W\in\mathcal{U}_{rk}\cap\mathcal{U}_{rk}^{\Gamma}$.

3. Comparing subalgebras

We would like to address here the same question as the one in Section 5.3, but with the following choice of subalgebras:

where $d,r\geq 2$ are two arbitrary integers, and $n=dr$. It is clear that $\mathcal{A}_{1}\subseteq\mathcal{A}_{2}$. As in the previous case, we show that the two sets of unitary operators that leave invariant the above subalgebras cannot be compared.

Let us start by considering a general element from $\mathcal{U}^{(\text{inv})}_{1}$, of the form $U=(I_{d}\otimes V)(W\otimes I_{r})$, see Theorem 6.1. In order to check the conditions in Theorem 5.1, we decompose

and obtain the following expression for the blocks of $U$:

Since $W$ is unitary, an operator as above is a partial isometry iff $V_{ab}$ is one; but one can easily construct a unitary matrix $V$ having at least one block which is not a partial isometry (one can pick any small enough matrix $V_{11}$ which is not a partial isometry and extend it to a unitary matrix). This shows that $\mathcal{U}^{(\text{inv})}_{1}\nsubseteq\mathcal{U}^{(\text{inv})}_{2}$.

To show that the reversed inclusion also fails to hold, consider the case $k=r$ and choose two families $\{e_{ab}\}$, $\{f_{ab}\}$ of $k^{2}$ vectors, such that the conditions corresponding to conditions (C2), (C3) of Definition 3.2 are satisfied:

are partial isometries satisfying the hypotheses of Theorem 5.1 with initial and final spaces given by

Let us assume now that the unitary $U$ described above also leaves the algebra $\mathcal{A}_{2}$ invariant; from Theorem 6.1, we find unitary operators $V\in\mathcal{U}_{k^{2}}$ and $W\in\mathcal{U}_{kd}$ such that $U=(I_{d}\otimes V)(W\otimes I_{k})$. In particular, the blocks of $U$ read

where $V_{ab}$ are the $k\times k$ blocks of the unitary operator $V$. Muliplying the equation above with the adjoint of the same expression for another index pair $(\alpha,\beta)$, we get

Zero block algebra

The stability of $\mathcal{A}$ algebras in either the Schrödinger or Heisenberg pictures imposes the same constraints on the bipartite unitary matrices.

with $U_{00}$ and $U_{11}$ unitary matrices.

The implications (1)$\implies$(3) and (2)$\implies$(3) hold if the stability of the algebra $\mathcal{A}$ holds for a positive definite state $\beta$. In other words if $\mathcal{B}$ is replaced in respectively (1) and (2) by a singlet $\mathcal{B}=\{\beta\}$ with $\beta>0$.

We start with the implication (1)$\implies$(3). Statement (1) is equivalent to

Since $\beta>0$ and, $X$ and $Y$ are positive semidefinite, there exists a constant $c>0$ such that,

Hence $\|U_{10}\|_{HS}=0$ where $\|\cdot\|_{HS}$ is the Hilbert–Schmidt norm. Since $U$ is a unitary matrix, $U_{01}$ implies $U_{11}U_{11}^{*}=I_{d_{1}}$ and $U_{00}^{*}U_{00}=I_{d_{0}}$. Hence both $U_{00}$ and $U_{11}$ are full rank and thus unitary matrices by Cochran’s Lemma 3.4. Using again the fact that $U$ is unitary, $U_{11}U_{01}^{*}=0$ yields statement (3).

The proof of (2)$\implies$(3) is similar. Statement (2) is equivalent to

Since $\beta>0$, taking $X=P_{0}$ and $Y=P_{1}$ we deduce, $U_{01}=0$. Using again the fact that $U$ is unitary, statement (3) follows.

Imposing a finer subalgebra structure to $\mathcal{A}$ amounts to apply one of the appropriate theorems from previous sections to the unitary bloc $U_{11}$.

Generating random structured bipartite unitary operators

We discuss in this section the natural probability measure one can consider on the sets of bipartite unitary operators appearing in Theorems 4.1,4.4,5.1,5.2,6.1,6.2. We shall discuss each problem separately, in the order of increasing difficulty.

Since $U_{ij}$ is a partial isometry, we also have $\delta_{ij}=\dim F_{ij}$, and thus, from condition (C2), we get

We conclude that the non-negative integer matrix $\delta=(\delta_{ij})_{i,j=1}^{n}$ has the property that each of its rows and columns forms a partition of $k$. For each such pattern matrix $\delta$, we construct the following probability measure on the set of unitary matrices $U$.

Random bipartite unitary operators satisfying (C2),(C3) with a given pattern

Consider $2n$ i.i.d., Haar distributed unitary random matrices $R_{1},\ldots,R_{n},C_{1},\ldots,C_{n}\in\mathcal{U}_{k}$. Denote by $R_{i}(j)$ the $j$-th column of the matrix $R_{i}$; similarly for $C_{i}(j)$.

Define the input spaces $E_{ij}$ as follows:

For all $i,j\in[n]$, the partial isometry $U_{ij}$ is defined by its action on $E_{ij}$, the orthogonal of its kernel:

Output: $U=\sum_{i,j=1}^{n}e_{i}e_{j}^{*}\otimes U_{ij}$, a random unitary matrix satisfying the conditions from Theorem 5.1.

Note that the choice of the pattern matrix $\delta$ in the algorithm above is arbitrary. A canonical choice only appears when $k=n$, in which case one can choose $\delta_{ij}=1$, for all $i,j\in[n]$. The case of unitary operators appearing in Theorem 5.1 is dealt with in a similar manner, we leave the details to the reader.

Regarding operators which give quantum channels preserving tensor product algebras (Theorem 6.2), the situation is more complicated, since there is not an obvious way to sample uniformly from the set $\mathcal{U}_{unital}$ from (17), see also [11, Section 3]. We conjecture that the following algorithm will converge to an element of $\mathcal{U}_{unital}$.

Input: Integers $n,k$ and an error parameter $\varepsilon>0$.

Start with a Haar distributed unitary random unitary operator $U\in\mathcal{U}_{nk}$.

While $\|U^{\Gamma}(U^{\Gamma})^{*}-I_{nk}\|_{2}>\varepsilon$, repeat the next step:

$U\leftarrow\operatorname{Pol}(U^{\Gamma})$, where $\operatorname{Pol}(X)$ is the unitary operator $V$ appearing in the polar decomposition of $X$: $X=VP$ with $P\geq 0$.

Output: $U$, an operator at distance at most $\varepsilon$ from $\mathcal{U}_{unital}$.

In Figure 4, we present numerical evidence supporting our conjecture that the algorithm above converges. Note than an obstruction to the convergence of the algorithm would be an example of a matrix $U\in\mathcal{U}_{nk}$ such that

on such an input, the loop would be stuck on $U\notin\mathcal{U}_{unital}$. We do not know whether such matrices exist or not. An implementation of the algorithm above can be found at .

We say that $X$ is an $\varepsilon$-QLS if it is close to being a QLS, in the following sense:

Non-commutative Sinkhorn algorithm for sampling QLS

Input: The dimension $n$ and an error parameter $\varepsilon>0$

While $X$ is not an $\varepsilon$-QLS, do the steps (4-6)

Define the matrix $Y$ by making the rows of $X$ unitary:

Define the matrix $Z$ by making the rows of $Y$ unitary:

We conjecture that the algorithm above converges almost surely (for a computer implementation, see ). Again, the proof of this important result is elusive at this time, but we have numerical evidence (see Figure 5), as well as a proof of a relaxed version, where we replace the rank-1 projectors $p_{ij}$ with positive definite operators, see Appendix A.

Appendix A A non-commutative Sinkhorn algorithm: the invertible case

A block matrix having the two properties above will be called a block-bistochastic matrix. As in the classical case, we shall need to define an approximate notion of block-bistochasticity: given some positive $\varepsilon>0$, we call $Y$ $\varepsilon$-block-bistochastic if

Let us introduce now the non-commutative variant of the classical Sinkhorn algorithm.

Non-commutative Sinkhorn algorithm, the invertible case

While $Y$ is not $\varepsilon$-block-bistochastic, do the steps (4-6)

Define the block matrix $Y^{\prime}$ by normalizing the rows of $Y$:

Define the block matrix $Y^{\prime\prime}$ by normalizing the columns of $Y^{\prime}$:

Output: $Y$, a $\varepsilon$-block-bistochastic matrix.

Before proving that the algorithm above finishes after a finite number of steps, let us note that the inverses used in steps (4) and (5) are well-defined. Indeed, it is easy to check that at each step, the matrices $Y,Y^{\prime},Y^{\prime\prime}$ have positive definite blocks (we assume that the input $X$ has this property), and thus their row-sums and column-sums are also positive definite (and thus invertible) $k\times k$ matrices.

For any input $X$ having positive definite blocks and any precision parameter $\varepsilon>0$, the algorithm above stops after a finite number of steps.

Our proof is a natural extension of the proof in . On the set $\mathcal{X}_{n,k}$ of $n\times n$ block matrices with strictly positive $k\times k$ blocks $X_{ij}$, we introduce the function $F:\mathcal{X}_{n,k}\to[0,\infty)$ given by

Let us now consider a matrix $Y\in\mathcal{X}_{n,k}$ with the property that the columns of $Y$ are normalized, i.e. $\forall j\in[n]$, $\sum_{i=1}^{n}Y_{ij}=I_{k}$. We claim that $F(Y)\leq 1$. Indeed, this is a consequence of the arithmetic-geometric (AG) mean inequality, as follows:

So, if we denote by $Y_{1},Y_{2},\ldots$ the matrices $Y$ which enter the algorithm at step (4), then we have $F(Y_{r})\leq 1$, for all $r\geq 2$. We show now that, along the “trajectory” $Y_{1},Y_{2},\ldots$, the functional $F$ is increasing. We shall assume that $r\geq 2$ ($Y$ entering step (4) has normalized columns) and we shall prove that $F(Y)\leq F(Y^{\prime})$. The inequality $F(Y^{\prime})\leq F(Y^{\prime\prime})$ can be proved in a similar manner. We have

We have thus shown that the function $r\mapsto F(Y_{r})$ is increasing and bounded along a run $Y_{1},Y_{2},\ldots$ of the algorithm, so it must converge to some value $f_{\infty}\in$. In particular, the quantity appearing on the left hand side of (19) converges to 1, as $r\to\infty$. As a consequence, the AG mean inequalities which were used in (19) were almost equalities: given $\varepsilon$, there is some $R\geq 2$ such that, for all $r\geq R$ and all $i\in[n]$,

It is a classical fact (see, e.g. ) that this implies that that the numbers appearing in the AG inequality should be, up to some constants depending on $n$, $\varepsilon$-close to their mean; in our case this translates to the matrices $\sum_{i=1}^{s}Y_{is}$ being close to a multiple of the identity, which is our $\varepsilon$-block-bistochastic condition. ∎

References