{'fraction_non_alphanumeric': 0.04378554469659323, 'fraction_numerical': 0.016343658550052455, 'mean_word_length': 4.395293416741138, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 2, 'https://': 1, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Efficient optimization of the quantum relative entropy

Many quantum information measures can be written as an optimization of the quantum relative entropy between sets of states. For example, the relative entropy of entanglement of a state is the minimum relative entropy to the set of separable states. The various capacities of quantum channels can also be written in this way. We propose a unified framework to numerically compute these quantities using off-the-shelf semidefinite programming solvers, exploiting the approximation method proposed in [Fawzi, Saunderson, Parrilo, Semidefinite approximations of the matrix logarithm, arXiv:1705.00812]. As a notable application, this method allows us to provide numerical counterexamples for a proposed lower bound on the quantum conditional mutual information in terms of the relative entropy of recovery.


Introduction
Many quantities in quantum information theory can be formulated as optimization problems involving the quantum relative entropy function: Examples of such problems include various notions of channel capacities, and relative entropy measures such as the relative entropy of entanglement [VPRK97] or the relative entropy of recovery [LW14]. Despite being a convex function, the relative entropy function D is not natively supported by standard conic optimization solvers. To address this issue, the recent paper [FSP17] proposed a new way to accurately approximate the relative entropy function via semidefinite programming. This allows us to use off-the-shelf semidefinite programming solvers to solve convex optimization problems involving relative entropy.
The purpose of this paper is to survey some optimization problems in quantum information theory where the proposed method can be used. In particular we show how various quantum information theoretic quantities can be computed using semidefinite programming. The problems we consider in this paper include: • Capacity of classical-quantum channel • Entanglement-assisted classical capacity of quantum channel • Quantum capacity of degradable channels • Relative entropy of entanglement • Relative entropy of recovery Some tailored algorithms have previously been developed for some of these quantities [ZFG10,SSMER16] and we show that the SDP-based approximations of [FSP17] are in general much faster in addition to being more flexible. As an application, we provide a numerical counterexample for an inequality that was recently proposed in [LW14,BHOS15] concerning the relative entropy of recovery. Other applications of relative entropy optimization are discussed in [CS15].
The approximations of [FSP17] were implemented in the Matlab package for CVX called CvxQuad and is available at the URL: https://www.github.com/hfawzi/cvxquad/ Table 1 shows the functions implemented in CvxQuad. For each problem we consider in this paper we provide the Matlab code using CvxQuad that is needed to do the computation. Some of the code also requires the quantinf package [Cub] for density matrix manipulations.
a For each function, the constructed SDP consists of several blocks, each of size indicated in the column (n is the dimension of the input ρ, and σ if applicable). The number of such blocks is equal to k + m where k and m are two parameters that control the accuracy of the approximations. The default setting in CvxQuad is k = m = 3 which we observed gives a good accuracy for most practical situations. We refer to [FSP17] for more details on the role of k and m.
b For the function quantum rel entr, the SDP consists more precisely of m blocks of size (n 2 + 1) × (n 2 + 1) and k blocks of size 2n 2 × 2n 2 . Also if either ρ or σ are constant, the SDP blocks have size 2n × 2n instead. The main technical idea underlying [FSP17] and CvxQuad is a rational function approximation of the logarithm function which preserves operator concavity. Such a rational approximation is obtained by using quadrature on an integral representation of log (hence the name CvxQuad). We refer the reader to [FSP17] for more information on how the approximation works. Internally all the functions given in Table 1 are represented as semidefinite constraints and can thus be used with any off-the-shelf semidefinite solver.
The paper is organized as follows. In Section 2 we introduce the notations that will be used in this paper. In Section 3 we consider the problem of computing various channel capacities. In Section 4 we consider the computation of the relative entropy of entanglement. Finally, Section 5 is concerned with the relative entropy of recovery where we show via numerical counterexamples that the relative entropy of recovery is not in general a lower bound on the quantum conditional mutual information, answering a question of [LW14,BHOS15].

Notations
Given a finite-dimensional Hilbert space A we denote by D(A) the set of density operators on A, i.e., the set of Hermitian positive semidefinite matrices of size dim(A) with unit trace. Given ρ ∈ D(A) we denote by H(ρ) = − Tr[ρ log ρ] the von Neumann entropy of ρ. If σ ∈ D(A) is another density operator on A we let D(ρ σ) = Tr[ρ(log ρ − log σ)] be the quantum relative entropy between ρ and σ. If ρ is a bipartite state on A ⊗ B, the conditional entropy H(A|B) ρ is defined by We denote by L(A) the set of linear operators on A. If A has dimension n then L(A) ∼ = C n×n . A quantum channel Φ with input space A and output space B is a linear map Φ : L(A) → L(B) that is completely positive and trace-preserving.
3 Capacities of quantum channels 3.1 Classical to quantum channel Given a (finite) input alphabet X and a finite-dimensional Hilbert space A, a classical-quantum channel is a map Φ : X → D(A) which maps symbols x ∈ X to density operators Φ(x). The capacity of such a channel is given by the solution of the following optimization problem [HG12]: where H is the von Neumann entropy. The variable in (1) is a probability distribution p on X . One can formulate this optimization problem using the following CVX code, which uses the quantum entr function of CvxQuad (for simplicity the code shown here is when X consists of two elements): % Input alphabet X ={1 ,2}. % Generate rho1 and rho2 at random using quantinf ' s randRho function rho1 = randRho (2); rho2 = randRho (2); cvx_begin variables p1 p2 ; maximize (( quantum_entr ( p1 * rho1 + p2 * rho2 ) ... -p1 * quantum_entr ( rho1 ) -p2 * quantum_entr ( rho2 ))/ log (2)) p1 + p2 == 1; p1 >= 0; p2 >= 0; cvx_end Listing 1: Capacity of cq-channel Accuracy Since CvxQuad is based on an approximation of the entropy function, we first check the accuracy of the method on a simple channel for which the capacity is known. Consider a channel on binary input alphabet X = {0, 1} where Φ(0) and Φ(1) are pure states (2) In this this case it known that the capacity of the channel is h 2 ((1 + )/2) where h 2 is the binary entropy function and = | ψ 0 |ψ 1 | (see [HG12, Example 1]). We generate random channels by generating random states ψ 0 and ψ 1 . Table 2 shows the value of the capacity computed by solving (1) via CvxQuad, vs. the true value of the capacity. We see that the absolute error between the true value of capacity and the value obtained by running Listing 1 is of the order of 10 −6 .  Table 2: Classical-to-quantum channel capacity of random channels of the form (2). We see that the absolute error between the true value of capacity and the value obtained by running Listing 1 is of the order of 10 −6 .
Computation time The paper [SSMER16] developed a tailored first-order optimization method to compute the solution of (1). In Table 3 we compare the running times of the approach of [SSMER16] and the SDP-based approach of CvxQuad. We see that the SDP-based approach scales better for channels with large output dimension.  Table 3: Comparison of computation time for the first-order method of [SSMER16] and the SDPbased method of CvxQuad for the capacity of classical-quantum channels. The number of iterations of [SSMER16] was set to achieve an a priori accuracy of 10 −2 . The a posteriori error ended up being around 10 −4 for the different instances. The channel output dimension seems to have a strong effect on the method of [SSMER16].

Entanglement-assisted classical capacity
Consider a quantum channel Φ with input system A and output system B. The entanglementassisted classical capacity denoted C ea quantifies the amount of classical bits one can transmit reliably through the channel, if the transmitter and receiver are allowed to share an arbitrary entangled state. The entanglement-assisted classical capacity of a quantum channel was shown in [BSST02] to have a simple maximization expression: where I(ρ, Φ) is the so-called mutual information of the channel Φ for the input ρ. This formula plays the same role as the well-known formula for the Shannon capacity of a classical channel. To define the mutual information I(ρ, Φ) let U : A → B ⊗ E be a Stinespring isometry for Φ with environment E, i.e., such that Φ(X) = Tr E [U XU * ] for any operator X on A. Then I(ρ, Φ) is defined as: where H(B|E) denotes the conditional entropy. An important property of the mutual information defined in (4) is that it is concave in ρ. This follows from concavity of conditional entropy which follows from convexity of relative entropy: indeed if σ is a bipartite state on BE then one can verify that Since Chapter 7] for more properties of I(ρ, Φ).
Illustration Consider the so-called amplitude-damping channel defined by (see [Wil16, Section 21.6.2]): where The following Matlab/CVX script uses the quantum cond entr function of CvxQuad to compute the entanglement-assisted capacity of the amplitude damping channel for the parameter γ = 0.2: Remark 1 (Size of the semidefinite program to compute (3)). As explained before, the function quantum cond entr will internally use a semidefinite programming approximation of the quantum conditional entropy function. The size of the SDP that is generated to express I(ρ, Φ) for a given channel Φ can be quite large. More precisely if we let dim(A), dim(B), dim(E) be respectively the dimensions of the input, output and environment spaces of the channel, then the SDP representation of the quantum cond entr term in Listing 2 (for the default approximation parameters) has a total of 6 positive semidefinite constraints, each of size 2(dim(B) dim(E)) 2 (more generally there are k + m such constraints where k and m are the two parameters that control the accuracy of the approximation, see Table 1, and [FSP17] for details).
In the example of amplitude-damping channel, the environment has dimension dim(E) = 2 and so the size of the each block is 2 × 4 2 = 32. Some channels though have larger environment spaces, say dim(E) = 3 (phase-damping channel) or dim(E) = 4 (depolarizing channel) which may result in much larger SDPs. Many of the channels however have a lot of symmetry and this symmetry could be exploited to reduce the size of the resulting SDPs.

Quantum capacity of degradable channels
The (unassisted) quantum capacity Q(Φ) of a quantum channel Φ is the number of quantum bits (qubits) one can reliably transmit over Φ. The quantum capacity of Φ admits the following expression [HG12] where I c is the so-called coherent information of a channel Φ for the input ρ: In the expression above, Φ c denotes a complementary channel of Φ defined as follows: if Φ is a channel from A to B with environment E and isometry representation U : A → B ⊗ E, then a complementary channel Φ c : L(A) → L(E) is given by: In general, evaluating the quantum capacity (7) is difficult. However there is a class of socalled degradable channels where the expression for Q(Φ) can be simplified [DS05]. A channel Φ is degradable if there exists a channel Ξ : L(B) → L(E ) with E ∼ = E such that Φ c = Ξ • Φ. If a channel Φ is degradable one can show that the limit in (7) is not needed (i.e., one can fix n = 1) and that I c (ρ, Φ) is concave in ρ. The latter follows from concavity of quantum conditional entropy as we show now: assume Φ c = Ξ • Φ and let W : B → E ⊗ F be an isometry representation of Ξ. Then note that Φ c (ρ) = Ξ(Φ(ρ)) = Tr F [W Φ(ρ)W * ]. Thus we get that where in (a) we used the fact that H(σ) = H(W σW * ) since W is an isometry and in (b) we simply used the definition of conditional entropy. Since the conditional entropy is concave and The previous derivation shows that for degradable channels, I c (ρ, Φ) can be expressed in terms of conditional entropy and thus can be formulated using the functions in CvxQuad.
Remark 2. For general (non-degradable) channels, one can use the "approximately degradable" approach proposed in [SSWR14] to get an upper bound on the quantum capacity by solving a convex optimization problem similar to the one described above.
Illustration As an illustration, we consider the amplitude-damping channel we saw in the previous section (see Equation (6)). This channel is known to be degradable when γ ≤ 1/2 and the degrading map in this case is an amplitude damping channel of parameter (1 − 2γ)/(1 − γ). Listing 3 shows the Matlab/CVX script using the function quantum_cond_entr of CvxQuad to compute the quantum capacity of the amplitude-damping channel. Figure 2 shows a plot of the quantum capacity of amplitude damping channels for γ ∈ [0, 1/2]. Given a bipartite state ρ in D(A ⊗ B) the relative entropy of entanglement is defined as the distance from ρ to Sep, in the relative entropy sense [VPRK97]: Since the set Sep is difficult to describe in general [Gur03] we can get instead a lower bound on REE(ρ) by replacing the constraint that τ ∈ Sep, by the constraint that τ has a positive partial transpose: Similarly one can also define the quantity REE (k) (ρ) where the separability constraint is replaced by the k'th level of the SDP hierarchy [DPS04]. The value REE (1) (ρ) can be computed using the CVX code shown in Listing 4, which uses the function quantum_rel_entr of the CvxQuad package. The paper [ZFG10] (see also [GZFG15]) provides a numerical method to estimate REE (1) (ρ) using a tailored cutting-plane method which constructs a polyhedral approximation of the function τ → Tr[ρ log τ ] by evaluating its derivatives at different points. Table 4 shows the result of computing REE (1) (ρ) using the script above, for randomly generated ρ of different sizes, as well as with the cutting-plane method of [ZFG10,GZFG15]. We see that the method based on CvxQuad is much faster and scales better for states of large size.  Table 4: Running times to compute the value REE (1) (ρ) (9) for random choices of bipartite states ρ of size n = n A × n B . We see that on all the matrices tested, the CvxQuad approach is much faster than the cutting-plane approach of [ZFG10,GZFG15]. Note that the algorithm [ZFG10,GZFG15] returns an interval of length guaranteed to contain the optimal value of (9) (we set = 10 −3 in the experiments). In all cases tested the value returned by the CvxQuad code lied in that interval.

Relative entropy of recovery and conditional mutual information
Consider a tripartite state ρ ABC defined on the Hilbert space A ⊗ B ⊗ C. The conditional mutual information of A and C given B is defined by A state for which the conditional mutual information is zero is called a Markov chain A − B − C.
In the case of a probability distribution, this corresponds to the random variables A and C being conditionally independent given B. In the general quantum case, the word Markov chain is justified by the fact that such a state ρ has the following property: starting with the marginal on A ⊗ B, one can generate the system C by only acting on the system B [Pet88]. In other words, it is possible to perfectly recover the C system by acting only on B.
In order to interpret the conditional mutual information operationally, it would be desirable to relate it to how well a state is recoverable [LW14]. This leads us to consider states of the form where Λ is a quantum channel. These correspond to tripartite states that are obtained by acting only on B. In [FR15], it was shown that whereD 1/2 is a relative entropy measure of order 1/2 that is smaller than the quantum relative entropy, but its exact definition is not important for this paper. Inequality (11) was then improved by [BHOS15], who replaced the relative entropy measureD 1/2 of order 1/2 with the larger measured relative entropy D M . The authors of [LW14] and [BHOS15] naturally ask whether the inequality (11) may be further improved to Since the right-hand side of (12) -which we can call the relative entropy of recovery of ρ ABCis a quantum relative entropy optimization problem, we can test the inequality (12) numerically on any given state ρ ABC . Listing 5 shows the code to compute this quantity using the functions in CvxQuad. The following numerical examples show that the inequality (12) can be violated.
Random pure states We first tested (12) on random pure states where dim(A) = dim(B) = dim(C) = 2. Figure 3 shows a plot of the relative entropy of recovery vs. conditional mutual information for 2000 randomly generated states. We see that for some states the inequality (12) Relative entropy of recovery vs. conditional mutual information Figure 3: Plot of right-hand side of (12) vs. left-hand side for 2000 randomly generated rank-one (pure) states ρ ABC . We see that some of the points violate the inequality.
Explicit counter-example We can also give an explicit state ρ ABC that violates (12). Consider the following pure tripartite state: where |ψ ABC = 1 √ 2 |0 B |00 AC + 1 √ 2 |1 B (cos(θ)|01 AC + sin(θ)|10 AC ) (14) Figure 4 shows I(A : C|B) and the relative entropy of recovery for the range θ ∈ [0, π/2]. We have also included the quantum Rényi divergence (for α = 7/8) defined bȳ D α (ρ σ) = 1 α − 1 log Tr ρ α σ 1−α which is a lower bound on the relative entropy D and which can be optimized exactly using semidefinite programming for rational α [FS17,Sag13]. We see that there is a range of values of θ where the relative entropy of recovery is greater than or equal the conditional mutual information.