Time-reversal of rank-one quantum strategy functions
Yuan Su John Watrous
quant-ph

=1














theoremTheorem
lemma[theorem]Lemma
prop[theorem]Proposition
cor[theorem]Corollary
definition
definition[theorem]Definition
*remarkRemark































 
 







































mylist[1]
	
	
	
	
	
	























                 
















  Department of Computer Science,
  Institute for Advanced Computer Studies, and
  Joint Center for Quantum Information and Computer Science,
  University of Maryland, USA


http://quics.umd.edu/people/yuan-su
0000-0003-1144-3563


Institute for Quantum Computing and School of Computer
  Science, University of Waterloo, Canada


Canadian Institute for Advanced Research, Toronto,
  Canada



homepage
  https://cs.uwaterloo.ca/ watrous/
    https://cs.uwaterloo.ca/.17ex∼watrous/


0000-0002-4263-9393

Time-reversal of rank-one quantum strategyfunctions
    John Watrous
    October 1, 2018
===================================================




  The quantum strategy (or quantum combs) framework is a useful
  tool for reasoning about interactions among entities that process and
  exchange quantum information over the course of multiple turns.
  We prove a time-reversal property for a class of linear functions, defined
  on quantum strategy representations within this framework, that corresponds
  to the set of rank-one positive semidefinite operators on a certain space.
  This time-reversal property states that the maximum value obtained by such a
  function over all valid quantum strategies is also obtained when the
  direction of time for the function is reversed, despite the fact that the
  strategies themselves are generally not time reversible.
  An application of this fact is an alternative proof of a known relationship
  between the conditional min- and max-entropy of bipartite quantum states,
  along with generalizations of this relationship.






§ THE QUANTUM STRATEGY FRAMEWORK


The quantum strategy framework <cit.>, which is also known as
the quantum combs framework <cit.>,
provides a useful framework for reasoning about networks of quantum channels.
It may be used to model scenarios in which two or more entities, which we will
call players, process and exchange quantum information over the course
of multiple rounds of communication; and it is particularly useful when one
wishes to consider an optimization over all possible behaviors of one
player, for any given specification of the other player or players.
Various developments, applications, and variants of the quantum strategy
framework can be found in
<cit.>,
for instance, and in a number of other sources.

In the discussion of the quantum strategy framework that follows, as well as in
the subsequent sections of this paper, we assume that the reader is familiar
with quantum information theory and semidefinite programming.
References on this material include
<cit.> as well as
<cit.>, which we follow closely with respect to notation and
terminology.
In particular, we denote quantum registers by capital sans serif letters such
as X, Y, and Z (sometimes with natural number
subscripts), while the same letters (with matching subscripts) in a scripted
font, such as , , and  denote the complex Euclidean spaces
(i.e., finite-dimensional complex Hilbert spaces) associated with the
corresponding registers.
The set (,) denotes the set of all linear operators from  to
;
() is a shorthand for (,);
(), (), (), and () denote the sets
of all Hermitian operators, positive semidefinite operators, density operators,
and unitary operators acting on ;
(,) denotes the set of all channels (i.e., completely positive and
trace-preserving maps) mapping () to (); and
() is a shorthand for (,).
The adjoint of an operator A is denoted A^∗, the entry-wise complex
conjugate is denoted A, and the transpose is denoted A^.
A similar notation is used for the adjoint and transpose of a channel Φ
(the meaning of which, in the case of the transpose, will be clarified later).
The (Hilbert-Schmidt) inner-product is defined as AB = (A^∗B)
for all operators A,B∈().
Some additional notation will be introduced as it is used.



 §.§ An example of a six-message interaction


To explain the aspects of the quantum strategy framework that are relevant to
this paper, we will begin by discussing an example of an interaction structure
involving six messages exchanged between two players, Alice and Bob.
We have chosen to describe a six-message interaction because it is simple and
concrete, but nevertheless clearly suggests the underlying structure of an
interaction having any finite number of message exchanges.
Our main result holds in the general case, which will be considered later,
where an arbitrary finite number of message exchanges may take place.



Figure <ref> illustrates an interaction between
Alice and Bob.
In this figure, time proceeds from left to right, and the arrows represent
registers either being sent from one player to the other
(as is the case for the registers X_1, Y_1, X_2,
Y_2, X_3, and Y_3), or momentarily stored by one of the
two players (as is the case for Z_1 and Z_2, stored by Alice,
and W_1, W_2, W_3, W_4, stored by Bob).
Alice's actions are represented by the channels Φ_1, Φ_2, and
Φ_3, and Bob's actions are represented by the channels Ψ_1, Ψ_2,
Ψ_3, and Ψ_4, as well as a final measurement, which is not given a
name in the figure.

Suppose that Bob's specification has been fixed, including his choices for the
channels Ψ_1, Ψ_2, Ψ_3, and Ψ_4, as well as his final
measurement, and suppose further that one of Bob's possible measurement
outcomes is to be viewed as desirable to Alice.
It is then natural to consider an optimization over Alice's possible actions,
maximizing the probability that Bob's measurement produces the outcome Alice
desires.
The quantum strategy framework reveals that this optimization problem can be
expressed as a semidefinite program, in the manner that will now be described.

First, a single channel Ξ_3 that transforms
(X_1,X_2,X_3) to (Y_1,Y_2,Y_3) is
associated with any given choice for Alice's actions.
That is, the channel Ξ_3 takes the form

    Ξ_3∈(_1⊗_2⊗_3,_1⊗_2⊗_3),

and for a particular selection of Φ_1, Φ_2, and Φ_3 may be
expressed as

    Ξ_3 = (_(_1⊗_2)⊗Φ_3)
      (_(_1)⊗Φ_2 ⊗_(_3))
      (Φ_1 ⊗_(_2 ⊗_3)).

Formally speaking, this composition requires that we view Φ_1, Φ_2,
and Φ_3 as channels of the form
Φ_1∈(_1,_1⊗_1),
Φ_2 ∈(_1⊗_2,_2⊗_2), and
Φ_3 ∈(_2⊗_3,_3),
as opposed to the forms
Φ_1∈(_1,_1⊗_1),
Φ_2 ∈(_1⊗_2,_2⊗_2), and
Φ_3 ∈(_2⊗_3,_3) suggested by
Figure <ref>, so that the ordering of the tensor
factors of the various input and output spaces is consistent with the
composition.
Similar re-orderings of tensor factors should be assumed implicitly throughout
this paper as needed.
This understanding should not be a source of confusion because we always
assign distinct names to distinct registers (and their associated spaces).
Figure <ref> illustrates the action of the channel
Ξ_3, which in words may be described as the channel obtained if all three
of the registers (X_1,X_2,X_3) are provided initially, and
then Alice's actions are composed in the natural way to produce
(Y_1,Y_2,Y_3) as output registers.



It may appear that by considering the channel Ξ_3, one is ignoring the
possibility that Bob's actions could, for instance, allow the contents of
Y_1 or Y_2 to influence what is input into X_2 or
X_3.
Despite this appearance, the influence that Alice's actions have from the
viewpoint of Bob, including the probability for each of his measurement
outcomes to appear, is uniquely determined by the channel Ξ_3.

Naturally, not all channels of the form (<ref>) will arise
from a composition of channels Φ_1, Φ_2, and Φ_3 as in
(<ref>); the fact that Φ_1 is effectively
performed first, Φ_2 is performed second, and Φ_3 is performed third
imposes constraints on the channels Ξ_3 that can be obtained.
In particular, consider the channel that results when Ξ_3 is performed
and then the partial trace is performed on _3.
As Φ_3 is a channel, discarding its output is equivalent to discarding its
inputs, from which it follows that

    Tr__3∘Ξ_3 = Ξ_2 ∘Tr__3,

where the circles represent channel compositions and
Ξ_2∈(_1⊗_2,_1⊗_2) is the channel defined as

    Ξ_2 = (_(_1)⊗ (__2∘Φ_2))
      (Φ_1 ⊗_(_2)).

That is, Ξ_2 is the channel obtained from Φ_1 and Φ_2, followed
by the partial trace over _2, by a similar process to the one used to
obtain Ξ_3.
By similar reasoning, one finds that

    Tr__2∘Ξ_2 = Ξ_1 ∘Tr__2,

where Ξ_1∈(_1,_1) is the channel given by
Ξ_1 = __1∘Φ_1.

Somewhat remarkably, this is not only a necessary condition on the channel
Ξ_3, but also a sufficient one, for it to be obtained from a composition of
channels Φ_1, Φ_2, and Φ_3 as described above.
That is, given any channel

    Ξ_3∈(_1⊗_2⊗_3,_1⊗_2⊗_3)

satisfying (<ref>) and (<ref>),
for some choice of channels

    Ξ_2∈(_1⊗_2,_1⊗_2),
    Ξ_1∈(_1,_1),

there must exist channels

    Φ_1∈(_1,_1⊗_1),
    Φ_2∈(_1⊗_2,_2⊗_2),
    Φ_3∈(_2⊗_3,_3),

for spaces _1 and _2 having sufficiently large dimension, so that
(<ref>) holds.
This fact is proved in <cit.>, and we
note that a key idea through which this equivalence is proved may be found in
<cit.>.

The next step toward an expression of the optimization problem suggested above
as a semidefinite program makes use of the Choi representation of channels.
The Choi representation of the channel Ξ_3 takes the form

    J(Ξ_3) ∈(_1⊗_2⊗_3⊗_1⊗_2⊗_3),

as the complete positivity of Φ_1, Φ_2, and Φ_3 implies that
Ξ_3 is also completely positive, and therefore J(Ξ_3) is positive
semidefinite.
The constraints on the channel Ξ_3 described previously correspond
(conveniently) to linear constraints;
one has that (<ref>) and
(<ref>) hold, for some choice of channels Ξ_2 and
Ξ_1, if and only if the Choi representation X_3 = J(Ξ_3) of Ξ_3
satisfies

    __3(X_3) = X_2 ⊗__3,
    __2(X_2) = X_1 ⊗__2,
    __1(X_1) = __1,

for some choice of operators

    X_2 ∈(_1⊗_2⊗_1⊗_2),
    
        X_1 ∈(_1⊗_1).

These operators correspond to the Choi representations X_2 = J(Ξ_2) and
X_1 = J(Ξ_1).

Finally, the probability that Bob's measurement produces a given outcome
is a linear function of the channel Ξ_3, and is therefore a linear function
of the Choi representation X_3 = J(Ξ_3).
Although this process is not relevant to the main result of this paper, we note
that it is possible to obtain an explicit description of this linear function
given a specification of Bob's actions, including his final measurement.
In somewhat vague terms, the linear function describing Bob's probability to
produce a particular measurement outcome is given by PX_3, where

    P∈(_1⊗_2⊗_3⊗_1⊗_2⊗_3)

is an operator that is obtained from Ψ_1, Ψ_2, Ψ_3, Ψ_4,
and the measurement operator corresponding to the outcome being considered
by a process very similar to the one through which X_3 is obtained from
Φ_1, Φ_2, and Φ_3.
The reader is again referred to
<cit.> for further details.

More generally, an arbitrary real-valued linear function of the operator
X_3 may be expressed as HX_3 for some choice of a Hermitian operator

    H∈(_1⊗_2⊗_3⊗_1⊗_2⊗_3),

which need not represent the probability with which a particular measurement
outcome is obtained for channels Ψ_1,…,Ψ_4 followed by a
measurement.
Such a function could, for instance, represent an expected payoff for Alice's
actions, under the assumption that a real-valued payoff is associated with each
of Bob's measurement outcomes.



 §.§ General semidefinite programming formulation


As mentioned previously, the six-message example just described generalizes to
any finite number of message exchanges.
If the number of message exchanges is equal to n, the input registers to
Alice (the player whose actions are being optimized) are
X_1,…,X_n, and the output registers of Alice are
Y_1,…,Y_n, then the possible strategies for Alice are
represented by channels of the form

    Ξ_n ∈(_1⊗⋯⊗_n,
      _1⊗⋯⊗_n)

that obey constraints that generalize (<ref>) and
(<ref>).
Specifically, there must exist channels

    Ξ_n-1∈(_1⊗⋯⊗_n-1,
        _1⊗⋯⊗_n-1)
    ⋮
    Ξ_1∈(_1,_1)

such that

    Tr__k∘Ξ_k = Ξ_k-1∘Tr__k

for all k∈{2,…,n}.
For the maximization of a real-valued linear function over all strategies for
Alice, represented by a Hermitian operator

    H∈(_1⊗⋯⊗_n⊗_1⊗⋯⊗_n),

one obtains the semidefinite program described in
Figure <ref>.
The primal problem corresponds to an optimization over all Choi
representations of the channels Ξ_1,…,Ξ_n.
This semidefinite programming formulation is implicit in <cit.>,
and first appeared explicitly in <cit.>.
It also appears in <cit.>, where it was used to define
a generalized notion of min-entropy for quantum networks.



It may be noted that the general problem just formulated concerns interactions
involving an even number of register exchanges, where Alice (the player whose
actions are being optimized) always receives the first transmission,
represented by X_1, and sends the last transmission, represented by
Y_n.
However, one is free to take either or both of the registers X_1 and
Y_n to be trivial registers, so that correspondingly _1 =
and/or _n =.
This is tantamount to allowing either an odd number of register exchanges or an
even number in the situation that Alice sends the first (nontrivial) register
and receives the last.




§ STATEMENT AND PROOF OF THE MAIN RESULT


The main result of the current paper concerns the optimization problem
described in the previous section, as represented by the semidefinite program
in Figure <ref>, in the case that H = u u^∗
is a rank one positive semidefinite operator.
The result to be described does not hold in general when H does not take this
form.

In order to explain the main result in precise terms, it will be helpful to
introduce some notation.
Suppose that a positive integer n along with spaces _1,…,_n and
_1,…,_n have been fixed.
For each k∈{1,…,n}, let

    _k(_1,…,_k; _1,…,_k)
      ⊂(_1⊗⋯⊗_k⊗_1⊗⋯⊗_k)

denote the primal-feasible choices for the operator X_k in the semidefinite
program specified in Figure <ref>.
That is, we define

    _1(_1;_1) = {X_1∈(_1⊗_1) : __1(X_1) = __1}

(which is the set of all Choi operators of channels of the form
Ξ_1 ∈(_1,_1)), and

    _k(_1,…,_k;_1,…,_k)
    
        = {
        X_k∈(_1⊗⋯⊗_k⊗_1⊗⋯⊗_k)
         : __k(X_k) = X_k-1⊗__k
    for some X_k-1∈_k-1(_1,…,
        _k-1;_1,…,_k-1)}

for k ∈{2,…,n}.
The primal form of the semidefinite program described in
Figure <ref> can therefore be expressed succinctly
as

    maximize:     HX
    subject to:      X∈_n(_1,…,_n;_1,…,_n).

We will refer to operators in the sets defined above as
strategy operators, as they represent n-turn strategies with respect
to the quantum strategy framework.

Let us also define an isometry

    W ∈(_1⊗⋯⊗_n⊗_1⊗⋯⊗_n,
      _n⊗⋯⊗_1⊗_n⊗⋯⊗_1)

by the action

    W (y_1⊗⋯⊗ y_n⊗ x_1⊗⋯⊗ x_n)
      = x_n⊗⋯⊗ x_1⊗ y_n⊗⋯⊗ y_1

for all vectors x_1∈_1,…,x_n∈_n and
y_1∈_1,…,y_n∈_n.
In words, W simply reverses the order of the tensor factors of the space
_1⊗⋯⊗_n⊗_1⊗⋯⊗_n, yielding a
vector in _n⊗⋯⊗_1⊗_n⊗⋯⊗_1
that, aside from this re-ordering of tensor factors, is the same as its input
vector.



 §.§ Statement of the main result


With the notation just introduced in hand, the main theorem may now be stated.


  
  Let _1,…,_n and _1,…,_n be complex Euclidean spaces,
  for n a positive integer, let
  
    u ∈_1⊗⋯⊗_n⊗_1⊗⋯⊗_n

  be a vector, and let
  
    X∈_n(_1,…,_n;_1,…,_n)

  be a strategy operator.
  There exists a strategy operator
  
    Y∈_n(_n,…,_1;_n,…,_1)

  such that
  
    W u u^∗ W^∗Y≥u u^∗X.

  If it is the case that
  (_1⊗⋯⊗_n)≤(_1⊗⋯⊗_n),
  then the operator Y may be chosen so that equality holds in
  (<ref>).



  
  Let _1,…,_n and _1,…,_n be complex Euclidean spaces,
  for n a positive integer, and let
  
    u ∈_1⊗⋯⊗_n⊗_1⊗⋯⊗_n

  be a vector.
  The semidefinite optimization problems
  
    maximize:     u u^∗X
    subject to:      X ∈_n(_1,…,_n;_1,…,_n)

  and
  
    maximize:     W u u^∗W^∗Y
    subject to:      Y ∈_n(_n,…,_1;_n,…,_1)

  have the same optimum value.



  Using the notation introduced in <cit.>, which defines a
  quantum network generalization of conditional min-entropy, the equivalence
  expressed by Corollary <ref> may alternatively be written
  
    H_min(Y_n|X_1,Y_1,…,
          X_n-1,Y_n-1,X_n)_u u^∗
    
          = H_min(X_1|Y_n,X_n,…,
          Y_2,X_2,Y_1)_u u^∗

  for every vector u ∈_1 ⊗_1⊗⋯⊗_n⊗_n.
  




 §.§ Interpretations of the main theorem


Theorem <ref> establishes a time-reversal property of
rank-one strategy functions.
Intuitively speaking, the linear function

    Y ↦W u u^∗ W^∗Y

defined on _n(_n,…,_1;_n,…,_1) represents the
time-reversal of the linear function

    X ↦u u^∗X

defined on _n(_1,…,_n;_1,…,_n), in the sense that the two
functions differ only in the reversal of the ordering of the register
exchanges:
X_1, Y_1, …, X_n, Y_n for the function
corresponding to u u^∗ and Y_n, X_n, …,
Y_1, X_1 for the function corresponding to
W u u^∗ W^∗. 

For a given choice of X∈_n(_1,…,_n;_1,…,_n), it is
generally not the case that
W^∗ X W∈_n(_n,…,_1;_n,…,_1).
It may not even be the case that W^∗ X W is the Choi representation of a
channel, and in the case that W^∗ X W is the Choi representation of a
channel, it will generally not be the case that this channel obeys the
constraints necessary for it to be a valid strategy operator.
When combined with the observation that
_n(_1,…,_n;_1,…,_n) and
_n(_n,…,_1;_n,…,_1) are compact and convex sets, this
fact implies that the main theorem cannot possibly hold for all Hermitian
operators H by the separating hyperplane theorem.
For small values of n and for spaces having small dimensions, simple
examples of operators H for which the main theorem fails may also easily be
obtained through random selections.

In Section <ref> we discuss another
interpretation of Theorem <ref>, which concerns multiple round
entanglement manipulation.



 §.§ Proof of Theorem <ref>


We will now prove Theorem <ref>.
The first step is to express the strategy represented by X as a sequence of
channels corresponding to invertible isometries (i.e., unitary operators for
which the input and output spaces have different names but necessarily the same
dimension), assuming an auxiliary input space initialized to a pure state
is made available.

Through the repeated application of the Stinespring dilation theorem, together
with the result of <cit.> establishing
that X=J(Ξ_n) is the Choi representation of a channel Ξ_n arising from
a valid n-turn strategy, one finds that there must exist complex Euclidean
spaces _0,…,_n satisfying
(_k-1⊗_k) = (_k⊗_k) for all
k∈{1,…,n}, a unit vector v ∈_0, and invertible isometries
U_1,…,U_n of the form

    U_k∈(_k-1⊗_k,_k⊗_k)

such that

    Ξ_n(Z) = __n(U (v v^∗⊗ Z) U^∗)

for all Z∈(_1⊗⋯⊗_n), where

    U = (__1⊗⋯⊗_n-1⊗ U_n)
        ⋯ (U_1 ⊗__2⊗⋯⊗_n)
    ∈(_0⊗_1⊗⋯⊗_n,
        _1⊗⋯⊗_n⊗_n).

In words, the strategy represented by the operator X is implemented by
first initializing a register Z_0 to the pure state v, then
applying the invertible isometric channels corresponding to U_1,…,U_n,
and finally discarding Z_n after the interaction has finished.
(The top picture in Figure <ref> illustrates this for the
case n=3.)




The vector u may be expressed as

    u = ∑_a_1,…,a_n
    b_1,…,b_n
      u(b_1,…,b_n,a_1,…,a_n)
      |b_1⟩⋯|b_n⟩|a_1⟩⋯|a_n⟩,

where the sum is over all standard basis states |a_1⟩,…,|a_n⟩ of
_1,…,_n and |b_1⟩,…,|b_n⟩ of _1,…,_n,
respectively.
Based on this expression, define an operator A∈(_0,_n) as

    A = ∑_a_1,…,a_n
    b_1,…,b_n
        u(b_1,…,b_n,a_1,…,a_n)
        (⟨b_n|⊗__n)U_n(__n-1⊗|a_n⟩)
        10mm0mm
    ⋯
        (⟨b_1|⊗__1)U_1(__0⊗|a_1⟩).

By considering the action of the strategy represented by v and
U_1,…,U_n, then performing the required operator-vector multiplications
required to evaluate the expression u u^∗X
when X = J(Ξ_n) for Ξ_n given by (<ref>), one concludes that

    u u^∗X = A v^2 = v v^∗A^∗ A.


Next we turn to the reversed interaction.
To obtain a strategy operator Y satisfying the requirements of the theorem,
we consider the strategy obtained by initializing the register Z_n to
a particular choice of a pure state w, which will be selected later,
then applying in sequence the invertible isometric channels corresponding to
the operators U_n^,…,U_1^.
(The bottom picture in Figure <ref> illustrates this for the
case n=3.)
That is, for 

    V = (__n⊗⋯⊗_2⊗ U_1^)
        ⋯ (U_n^⊗__n-1⊗⋯⊗_1)
    ∈(_n⊗_n⊗⋯⊗_1,
        _0⊗_n⊗⋯⊗_1),

we consider the channel Θ_n∈(_n⊗⋯⊗_1,
_n⊗⋯⊗_1) defined as

    Θ_n(Z) = __0( V (w w^∗⊗ Z) V^∗)

for all Z∈(_n⊗⋯⊗_1).
It is evident from the specification of this channel,
irrespective of the choice of the pure state w, that
Y = J(Θ_n)∈_n(_n,…,_1;_n,…,_1).
By considering the action of this strategy, a similar calculation to the one
above reveals that 

    Wu u^∗W^∗Y = A^ w^2 =
      w w^∗AA^.


The nonzero eigenvalues of A^∗ A and A A^ are equal,
and therefore by choosing w to be an eigenvector corresponding to the largest
eigenvalue of A A^ one obtains

    Wu u^∗W^∗Y =
      w w^∗AA^≥v v^∗A^∗ A = u u^∗X.

If it holds that (_1⊗⋯⊗_n)≤(_1⊗⋯⊗_n), then (_0)≤(_n), which
implies that the inequality in (<ref>) may be taken as an
equality for an appropriate choice of a pure state w.
This completes the proof.




§ APPLICATION TO MIN- AND MAX-ENTROPY


In this section we connect the main result proved in the previous section to
the conditional min- and max-entropy functions.
These function, which were first introduced in <cit.>, may be defined
as follows.
First, one defines the max- and min-relative entropy of P with respect to
Q, for positive semidefinite operators P and Q (acting on the same
space), as follows:

    D_max(P    Q)     = log(
      min{λ≥ 0 :  P ≤λ Q}),
    D_min(P    Q)     = -log((P,Q)^2).

Then, with respect to a given state ρ∈(⊗) of a pair of
registers (X,Y), one defines

    H_min(X | Y) = -inf_σ∈()D_max(ρ  _⊗σ),
    H_max(X | Y) = -inf_σ∈()D_min(ρ  _⊗σ).

It is known that these two quantities are related in the following way:
with respect to any pure state u u^∗ of a triple of registers
(X,Y,Z), one has that

    H_min(X | Y)
      = -H_max(X | Z).

(Indeed, in <cit.> the conditional max-relative entropy of a
state of (X,Z) is defined by the equation
(<ref>), which does not depend on which
purification of this state is chosen, and is then proved to agree with the
definition stated previously.)

Consider any unit vector u ∈⊗⊗, which defines a pure
state u u^∗ of a triple of registers (X,Y,Z).
We will consider two optimization problems defined by u, the first of which
is as follows:

    maximize:      u u^∗ X 
    subject to:      X ∈_2(,;,).

This optimization problem is illustrated in Figure <ref>.



In this case, the channel Φ_2 takes registers Z and W
as input and outputs nothing (which is equivalent to outputting the unique
state 1 ∈() of a one-dimensional system).
That is, Φ_2 must be the trace mapping.
One may therefore simplify this problem, obtaining the following semidefinite
program:


  [t].42
    Primal problem

    
    maximize:     _(u u^∗)X
    subject to:     _(X) = _,
        X ∈(⊗).

  
  [t].42
    Dual problem

    
    minimize:     (Y)
    subject to:     _⊗ Y ≥_(u u^∗),
        Y ∈().

  


By examining the dual problem, one sees that the optimal value of this
semidefinite program is

    2^-H_min(X|Y)

with respect to the state u u^∗ of (X,Y,Z).
König, Renner, and Schaffner <cit.> observed that the primal
problem coincides with the value represented by the expression
(<ref>), which is consistent with the observation that
strong duality always holds for this semidefinite program (which may be
verified through Slater's theorem, for instance).

The second optimization problem we consider is the time-reversal of the first,
and may be stated as follows:

    maximize:      W u u^∗ W^∗ Y 
    subject to:      Y ∈_2(,;,).

Figure <ref> illustrates the interaction corresponding to this
optimization problem.



The inclusion X∈_2(,;,), for a given operator
X∈(⊗⊗), is equivalent to the condition that
_(X) = σ⊗_ for some σ∈().
After re-ordering tensor factors, we obtain the following semidefinite program:


  [t].42
    Primal problem

    
    maximize:     u u^∗X
    subject to:     _(X) = _⊗σ,
        X ∈(⊗⊗),
       σ∈().

  
  [t].42
    Dual problem

    
    minimize:     λ
    subject to:      Y ⊗_≥ u u^∗,
       λ_≥_(Y),
        Y ∈(⊗),
       λ∈.

  


An examination of the primal problem reveals (through Uhlmann's theorem) that
the optimal value of this semidefinite program is

    2^H_max(X|Z).


By our main theorem, it follows that the two optimization problems have the
same optimal value, and therefore we obtain an alternative proof that with
respect to every pure state of a triple or registers
(X,Y,Z) one has

    H_min(X | Y)
      = -H_max(X | Z).


It is natural to ask if the connections among min-entropy, max-entropy, and
optimization problems involving three-message strategies have interesting
implications or generalizations for interactions involving four or more
messages.
As a partial answer to this question, we observe that when our main result is
applied to the four-message interaction depicted in
Figure <ref>, it reveals the identity

    max_Φ∈(,)(
      _(u u^∗), J(Φ) ⊗_)
      = max_Ψ∈(,)(
      _(u u^∗), _⊗ J(Ψ))

for all vectors u∈⊗⊗⊗.



This identity is appealing in its simplicity and symmetry, and by taking
= (or =) a statement equivalent to
(<ref>) for all pure states of
(X,Y,Z) is obtained.
We do not know, however, if the quantity represented by either side of the
identity has any direct operational significance.

Other identities may be obtained through a similar methodology, although they
become increasingly complex as the number of messages is increased.




§ ONLINE PURE STATE ENTANGLEMENT MANIPULATION



The following three statements are equivalent for a given operator
X∈(⊗):


  1.
  X∈_1(;).
  (Equivalently, X∈(⊗) and _(X) = _.)

  2. X = (Φ⊗_())((⃗_)(⃗_)^∗)
  for some channel Φ∈(,).

  3. X = (_()⊗Ψ)((⃗_)(⃗_)^∗)
  for some completely positive and unital map Ψ∈(,).

(Here and throughout this section, vec refers to the vectorization
mapping, which is the mapping obtained by extending the transformation
|a⟩⟨b|↦|a⟩|b⟩ for standard basis states to arbitrary
operators by linearity.
In particular, (⃗_) is a non-normalized vector proportional to the
canonical maximally entangled pure state corresponding to two identical copies
of a system whose state space is .)
The maps Φ and Ψ uniquely determine one another, and it is reasonable
to view these maps as being related by transposition (with respect to the
standard basis): Ψ = Φ^ and Φ = Ψ^.
To obtain a Kraus representation for Ψ, for instance, one may simply
take a Kraus representation of Φ and transpose each of the Kraus
operators.
(The transpose of an arbitrary map can be defined in a manner that is
consistent with these statements, but it is sufficient for our needs to focus
on channels and completely positive unital maps.)

A generalization of the equivalence mentioned above to the quantum strategy
framework may also be verified.
For an operator
X∈(_1⊗⋯⊗_n⊗_1⊗⋯⊗_n),
these three statements are equivalent:


  1. X∈_n(_1,…,_n;_1,…,_n).

  2. There exist complex Euclidean spaces _1,…,_n-1
  (and _0 = and _n =), along
  with channels Φ_1, …,Φ_n having the form
  
    Φ_k ∈(_k-1⊗_k,_k⊗_k),

  such that the channel
  Ξ_n∈(_1⊗⋯⊗_n,_1⊗⋯⊗_n)
  defined as
  
    Ξ_n = (_(_1⊗⋯⊗_n-1)⊗Φ_n)
        ⋯(Φ_1 ⊗_(_2⊗⋯⊗_n))

  satisfies
  
    X = (Ξ_n ⊗_(_1⊗⋯⊗_n))
        ((⃗__1⊗⋯⊗_n)
        (⃗__1⊗⋯⊗_n)^∗).


  3. There exist complex Euclidean spaces _1,…,_n-1
  (and _0 = and _n =), along
  with completely positive and unital maps Ψ_1, …,Ψ_n having the
  form
  
    Ψ_k ∈(_k⊗_k,_k-1⊗_k),

  such that the unital map
  Λ_n∈(_1⊗⋯⊗_n,_1⊗⋯⊗_n)
  defined as
  
    Λ_n =
        (Ψ_1 ⊗_(_2⊗⋯⊗_n))⋯(_(_1⊗⋯⊗_n-1)⊗Ψ_n)

  satisfies
  
    X = (_(_1⊗⋯⊗_n)⊗Λ_n)
        ((⃗__1⊗⋯⊗_n)
        (⃗__1⊗⋯⊗_n)^∗).



Through this equivalence, for a given state
ρ∈(_1⊗⋯⊗_n
⊗_1⊗⋯⊗_n),
one arrives at an alternative interpretation of the semidefinite program

    maximize:     ρX
    subject to:      X∈_n(_1,…,_n;_1,…,_n)

that concerns an online variant of entanglement manipulation, as is explained
shortly.
The term “online” in this context refers to a situation in which a quantum
state must be manipulated in multiple turns, where an output is required
immediately after each input system arrives and prior to the next input system
being made available, similar to an online process.

By the equivalence of the third statement above to the first, a maximization
over all X∈_n(_1,…,_n;_1,…,_n) is equivalent to a
maximization over all operators

    (_(_1⊗⋯⊗_n)⊗Λ_n)
      ((⃗__1⊗⋯⊗_n)
      (⃗__1⊗⋯⊗_n)^∗)

for 

    Λ_n =
        (Ψ_1 ⊗_(_2⊗⋯⊗_n))⋯(_(_1⊗⋯⊗_n-1)⊗Ψ_n)

and Ψ_1,…,Ψ_n being completely positive and unital maps of
the form

    Ψ_k ∈(_k⊗_k,_k-1⊗_k).

The value of the objective function ρX may therefore be expressed
as

    (_(_1⊗⋯⊗_n)⊗Λ_n^∗)(ρ)
      (⃗__1⊗⋯⊗_n)
        (⃗__1⊗⋯⊗_n)^∗,

which is (_1⊗⋯⊗_n) times the squared fidelity
between the maximally entangled state
τ∈(_1⊗⋯⊗_n⊗_1⊗⋯⊗_n) given by

    τ = (⃗__1⊗⋯⊗_n)
           (⃗__1⊗⋯⊗_n)^∗/(_1⊗⋯⊗_n)

and the state obtained by applying the channel Λ_n^∗ to the
portion of ρ corresponding to the spaces _1,…,_n.
In the case that n=1, König, Renner, and Schaffner <cit.>
refer to this quantity as the quantum correlation.
This situation is illustrated for the case n=3 in
Figure <ref>.





By Theorem <ref>, one finds that when ρ is pure, the same
optimal value is achieved when the ordering of the channels and the registers
on which they act is reversed, as illustrated in
Figure <ref> for the case n=3.
That is, when ρ is a pure state, the optimal value of the semidefinite
program (<ref>) represents the value

    (Ξ_n⊗_(_1⊗⋯⊗_n))(ρ)(⃗__1⊗⋯⊗_n)
        (⃗__1⊗⋯⊗_n)^∗,

maximized over all channels Ξ_n∈(_1⊗⋯⊗_n,
_1⊗⋯⊗_n) of the form

    Ξ_n = (Φ_1⊗_(_2⊗⋯⊗_n))
    
      ⋯(_(_1⊗⋯⊗_n-1)⊗Φ_n)

for channels Φ_1,…,Φ_n taking the form

    Φ_k ∈(_k⊗_k,_k-1⊗_k)

and for _2,…,_n-1 arbitrary complex Euclidean spaces
(along with _0 = and _n =).
 



§ CONCLUSION


We have identified a time-reversal property for rank-one quantum strategy
functions, explained its connection to conditional min- and max-entropy, and
described an alternative view of this property through an online variant of
pure state entanglement manipulation.
An obvious question arises: are there interesting applications or implications
of this property beyond those we have mentioned?




 §.§ Acknowledgments


Yuan Su was supported in part by the Army Research Office (MURI award
W911NF-16-1-0349) and the National Science Foundation (grant 1526380).
John Watrous acknowledges the support of Canada's NSERC.
We thank Frédéric Dupuis, James R. Garrison, Brian Swingle, Penghui
Yao, Ronald de Wolf, and Māris Ozols for helpful discussions, and we thank
the anonymous referees for their comments and suggestions.


plainnat



16


urlstyle

[Chiribella and Ebler(2016)]ChiribellaE16
G. Chiribella and D. Ebler.
Optimal quantum networks and one-shot entropies.
New Journal of Physics, 18:0 093053, 2016.
10.1088/1367-2630/18/9/093053.

[Chiribella et al.(2008a)Chiribella, D'Ariano, and
  Perinotti]ChiribellaDP08
G. Chiribella, G. D'Ariano, and P. Perinotti.
Quantum circuit architecture.
Physical Review Letters, 1010 (6):0 060401,
  2008a.
10.1103/PhysRevLett.101.060401.

[Chiribella et al.(2008b)Chiribella, D'Ariano, and
  Perinotti]ChiribellaDP08b
G. Chiribella, G. D'Ariano, and P. Perinotti.
Transforming quantum operations: quantum supermaps.
Europhysics Letters, 830 (3):0 30004,
  2008b.
10.1209/0295-5075/83/30004.

[Chiribella et al.(2009)Chiribella, D'Ariano, and
  Perinotti]ChiribellaDP09
G. Chiribella, G. D'Ariano, and P. Perinotti.
Theoretical framework for quantum networks.
Physical Review A, 800 (2):0 022339, 2009.
10.1103/PhysRevA.80.022339.

[Chiribella et al.(2013)Chiribella, D'Ariano, Perinotti, Schlingemann,
  and Werner]ChiribellaDPSW13
G. Chiribella, G. D'Ariano, P. Perinotti, D. Schlingemann, and R. Werner.
A short impossibility proof of quantum bit commitment.
Physics Letters A, 3770 (15), 2013.
10.1016/j.physleta.2013.02.045.

[Datta(2009)]Datta09
N. Datta.
Min- and max-relative entropies and a new entanglement monotone.
IEEE Transactions on Information Theory, 550
  (6):0 2816–2826, 2009.
10.1109/TIT.2009.2018325.

[Eggeling et al.(2002)Eggeling, Schlingemann, and Werner]EggelingSW02
T. Eggeling, D. Schlingemann, and R. Werner.
Semicausal operations are semilocalizable.
Europhysics Letters, 570 (6):0 782–788, 2002.
10.1209/epl/i2002-00579-4.

[Gutoski(2009)]Gutoski09
G. Gutoski.
Quantum Strategies and Local Operations.
PhD thesis, University of Waterloo, 2009.
http://hdl.handle.net/10012/4903URI: 10012/4903.

[Gutoski and Watrous(2007)]GutoskiW07
G. Gutoski and J. Watrous.
Toward a general theory of quantum games.
In Proceedings of the 39th Annual ACM Symposium on Theory of
  Computing, pages 565–574, 2007.
10.1145/1250790.1250873.

[Hardy(2012)]Hardy12
L. Hardy.
The operator tensor formulation of quantum theory.
Philosophical Transactions of the Royal Society A,
  3700 (1971):0 3385–3417, 2012.
10.1098/rsta.2011.0326.

[Kitaev et al.(2002)Kitaev, Shen, and Vyalyi]KitaevSV02
A. Kitaev, A. Shen, and M. Vyalyi.
Classical and Quantum Computation, volume 47 of Graduate
  Studies in Mathematics.
American Mathematical Society, 2002.
10.1090/gsm/047/08.

[König et al.(2009)König, Renner, and Schaffner]KoenigRS09
R. König, R. Renner, and C. Schaffner.
The operational meaning of min- and max-entropy.
IEEE Transactions on Information Theory, 550
  (9):0 4337–4347, 2009.
10.1109/TIT.2009.2025545.

[Nielsen and Chuang(2000)]NielsenC00
M. Nielsen and I. Chuang.
Quantum Computation and Quantum Information.
Cambridge University Press, 2000.
10.1017/CBO9780511976667.

[Watrous(2018)]Watrous18
J. Watrous.
The Theory of Quantum Information.
Cambridge University Press, 2018.
10.1017/9781316848142.

[Wilde(2013)]Wilde13
M. Wilde.
Quantum Information Theory.
Cambridge University Press, 2013.
10.1017/CBO9781139525343.

[Wolkowicz et al.(2000)Wolkowicz, Saigal, and
  Vandenberge]WolkowiczSV00
H. Wolkowicz, R. Saigal, and L. Vandenberge, editors.
Handbook of Semidefinite Programming: Theory, Algorithms, and
  Applications.
Kluwer Academic Publishers, 2000.
10.1007/978-1-4615-4381-7.




