Barrier relaxations of the classical and quantum optimal transport problems
Shmuel Friedland · 2025
Read Barrier relaxations of the classical and quantum optimal transport problems by Shmuel Friedland (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-10667.txt.
Introduction
Shmuel Friedland wrote a 2025 paper on relaxed forms of the optimal transport problem. That problem asks for the cheapest way to move mass between distributions, in both classic and quantum forms. A smoothed version has seen much progress in the past fifteen years.
Friedland shows that interior point methods for these problems can be seen as barrier relaxations. The dual form of the problem has far fewer variables, which is a clear gain. For the classic case, these methods are slower than a known fast scaling method. For the quantum case, though, the dual interior point method seems to work quite well in practice.
Catalog record
| CREATOR | Shmuel Friedland |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 101 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-10667
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Barrier relaxations of the classical and quantum optimal transport problems Shmuel Friedland Abstract . In the last fifteen years a significant progress was achieved by considering an entropic relaxation of the classical multi-partite optimal transport problem (MPOTP). The entropic relaxation gives rise to the rescaling problem of a given tensor. This rescaling can be achieved fast with the Sinkhorn type algorithms. Recently, it was shown that a similar approach works for the quantum MPOTP. However, the analog of the rescaling Sinkhorn algorithm is much more complicated than in the classical MPOTP. In this paper we show that the interior point method (IPM) for the primary and dual problems of classical and quantum MPOTP problems can be considered as barrier relaxations of the optimal transport problems (OTP). It is well known that the dual of the OTP are advantageous as it has much less variables than the primary problem. The IPM for the dual problem of the classical MPOTP are not as fast as the Sinkhorn type algorithm. However, IPM method for the dual of the quantum MPOTP seems to work quite efficiently. 2010 Mathematics Subject Classification 15A69, 52A41, 65K05, 0C22,90C25 1. Introduction 1.1. Discrete classical optimal transport problem The discrete classical bi-partite optimal transport problem (BPOTP) was introduced by Hitchcock and Kantorovich [ 20 , 21 ] . It is the following linear programming problem (LP). Let \Delta^{n}\subset\mathbb{R}^{n} the simplex of column probablity vectors, and [n]=\{1,\ldots,n\} . For \mathbf{x}=(x_{1},\ldots,x_{n})^{\top}\in\Delta^{n} denote by E_{S}(\mathbf{x})=-\sum_{i=1}^{n}x_{i}\log x_{i} the Shannon entropy of \mathbf{x} . Assume that \mathbf{p}_{i}\in\Delta^{n_{i}} for i=1,2 . Let P=(\mathbf{p}_{1},\mathbf{p}_{2}) and \mathrm{V}(P) be the convex set of all (coupling) probability matrices with marginals \mathbf{p}_{1},\mathbf{p}_{2} : (1.1) \mathrm{V}(P)=\{V=[v_{j_{1},j_{2}}]\in\mathbb{R}_{+}^{n_{1}\times n_{2}},\sum_{j_{2}=1}^{n_{2}}v_{j_{1},j_{2}}=p_{j_{1},1},\sum_{j_{1}=1}^{n_{1}}v_{j_{1},j_{2}}=p_{j_{2},2}\}. Here \mathbb{R}_{+}^{n}\supset\mathbb{R}_{++}^{n} stands for the cone of nonnegative vectors and its interior of positive vectors in \mathbb{R}^{n} . Let C=[c_{j_{1},j_{2}}]\in\mathbb{R}^{n_{1}\times n_{2}} be the cost matrix of transporting a unit j_{1}\in[n_{1}] to j_{2}\in[n_{2}] . The BPOTP is (1.2) \tau(C,P)=\min_{V\in\mathrm{V}(P)}\tr C^{\top}V. This problem can be stated in terms of maximum flow [ 30 ] . Hence, for n_{1}=n_{2}=n the complexity of finding \tau(C,P) is O(n^{3}\log n) . It turns out that \tau(C,P) has many recent applications in machine learning [ 1 , 2 , 23 , 26 , 36 ] , statistics [ 4 , 29 , 38 ] and computer vision [ 5 , 35 ] . For n>10^{3} the cost of computing \tau(C,P) becomes prohibitively high if one uses the maximal flow algorithm. In a breakthrough paper Cuturi [ 11 ] suggested an entropic relaxation of the BPOTP: (1.3) \displaystyle\tau(C,P,\varepsilon)=\min_{V\in\mathrm{V}(P)}\tr C^{\top}V-\varepsilon\mathrm{E}_{S}(V). Recall that (1.4) \tau(C,P,\varepsilon)\leq\tau(C,P)\leq\tau(C,P,\varepsilon)+\varepsilon\log(n_{1}n_{2}). (See part (a) of Lemma 2.1 .) As -\mathrm{E}_{S} is strictly convex, the minimal solution to ( 1.3 ) is unique. For a matrix A=[a_{j_{1},j_{2}}]\in\mathbb{R}^{n_{1}\times n_{2}} denote by \exp(\circ A)\in\mathbb{R}_{++}^{n_{1}\times n_{2}} the entry-wise exponential matrix [\exp(a_{j_{1},j_{2}})] . Then the minimal solution to the entropic relaxation of OTP is given by (1.5) \displaystyle U=\exp\left(\circ(\hat{U}_{1}+\hat{U}_{2}-\frac{1}{\varepsilon}C)\right)\in\mathrm{V}(P), \displaystyle\hat{U}_{1}=\mathbf{u}_{1}\mathbf{1}_{n_{2}}^{\top},\hat{U}_{2}=\mathbf{1}_{n_{1}}\mathbf{u}_{2}^{\top},\mathbf{u}_{1}\in\mathbb{R}^{n_{1}},\mathbf{u}_{2}\in\mathbb{R}^{n_{2}},\mathbf{1}_{n_{1}}^{\top}\mathbf{u}_{1}-\mathbf{1}_{n_{2}}^{\top}\mathbf{u}_{2}=0, \displaystyle\mathbf{1}_{n}=(1,\ldots,1)^{\top}\in\mathbb{R}^{n}. That is, the minimal solution is a rescaling of \exp\left(\circ(-\frac{1}{\varepsilon}C)\right) . This solution can be obtained by Sinkhorn’s algorithm [ 37 ] by alternatively rescaling the rows and columns of U_{k}=\exp\left(\circ(\hat{U}_{1,k}+\hat{U}_{2,k}-\frac{1}{\varepsilon}C)\right) . It turns out that fixing the error \delta and n_{1}=n_{2}=n , the complexity of modified Sinkhorn’s algorithm is O(n^{2}) ignoring logarithmic factors [ 1 ] . In this paper by arithmetic complexity of an algorithm we mean an estimate of number of flops to carry out this algorithm, see Appendix B . Similar results were obtained for entropic relaxation of multi-partite optimal transport problems that will be discussed later [ 3 , 39 , 19 , 22 , 14 ] . 1.2. Finite dimensional quantum optimal transport Let \mathcal{H} be an n -dimensional vector space with the inner product \langle\mathbf{x},\mathbf{y}\rangle . Let \mathrm{B}(\mathcal{H})\supset\mathrm{S}(\mathcal{H})\supset\mathrm{S}_{+}(\mathcal{H})\supset\mathrm{S}_{++}(\mathcal{H}) be the space of linear operators, the real subspace of self-adjoint operators, the cone of positive semidefinite operators, and the open set of positive definite operators respectively. By choosing a fixed orthonormal basis |0\rangle,\ldots,|n-1\rangle we identify \mathcal{H} with \mathbb{C}^{n} , where \langle\mathbf{x},\mathbf{y}\rangle=\mathbf{x}^{*}\mathbf{y} . Then the above linear operators on \mathcal{H} correspond to \mathbb{C}^{n\times n}\supset\mathrm{H}_{n}\supset\mathrm{H}_{n,+}\supset\mathrm{H}_{n,++} : the algebra of n\times n complex valued matrices, the Hermitian matrices, the positive semidefinite matrices, and the positive definite matrices respectively. Denote by \mathrm{H}_{n,+,1}\supset\mathrm{H}_{n,++,1} the convex set of density matrices (having trace one) and its interior respectively. For A\in\mathrm{H}_{n} denote by \lambda_{\max}=\lambda_{1}(A)\geq\cdots\geq\lambda_{n}(A)=\lambda_{\min}(A),\lambda(A)=(\lambda_{1}(A),\ldots,\lambda_{n}(A))^{\top}. the n eigenvalues of A . Recall that the spectral norm of A is \|A\|_{2}=\max(\lambda_{\max}(A),-\lambda_{\min}(A)) , and the Frobenius norm \|A\|_{F}=\sqrt{\sum_{j=1}^{n}\lambda_{j}^{2}(A)} . Assume that \mathcal{H}_{i} is a Hilbert space of dimension n_{i} for i\in[d] . Let \mathcal{H}=\otimes_{i=1}^{d}\mathcal{H}_{i} . Then \mathbb{C}^{\mathbf{n}}=\otimes_{i=1}^{d}\mathbb{C}^{n_{i}} is a representation of \mathcal{H} , and \mathrm{B}(\mathcal{H})\supset\mathrm{S}(\mathcal{H}) are represented by \mathbb{C}^{\mathbf{n}\times\mathbf{n}}\supset\mathrm{H}_{\mathbf{n}} respectively. (Here we identify \H_{n_{1}\cdots n_{d}} with 2d -mode Hermitian tensors \mathrm{H}_{\mathbf{n}} .) Let \rho_{i}\in\mathrm{H}_{n_{i},+,1} for i\in[d] , for d>1 . The coupling set of R=(\rho_{1},\ldots,\rho_{d}) is the closed convex set of all d -partite states whose partial traces are \rho_{i} for i\in[d] respectively: (1.6) \Gamma(R)=\{\rho\in\mathrm{H}_{\mathbf{n},+},\tr_{\hat{i}}\rho=\rho_{i},i\in[d]\},R=(\rho_{1},\ldots,\rho_{d})\}. Here, \tr_{\hat{i}}\rho is the sum of all partial traces of \rho except on the index i . (Observe that if \rho\in\Gamma(R) then \tr\rho=1 .) The quantum multi-partite optimal transport optimal transport problem for a given C\in\mathrm{H}_{\mathbf{n}} is [ 6 , 8 , 16 , 9 ] : (1.7) \kappa(C,R)=\min_{\rho\in\Gamma(R)}\tr C\rho. It is a semidefinite programming problem (SDP) [ 40 ] that can be solved efficiently using the interior point programming (IPM) [ 9 ] . For \rho\in\mathrm{H}_{n,+,1} denote by E_{N}(\rho)=-\sum_{i=1}^{n}\lambda_{i}(\rho)\log\lambda_{i}(\rho) the von Neumann entropy of \rho . The entropic relaxation of the quantum d -partite problem is (1.8) \kappa(C,R,\varepsilon)=\min_{\rho\in\Gamma(R)}\tr C\rho-\varepsilon\mathrm{E}_{N}(\rho). The analog of the inequality ( 1.4 ) is (1.9) \kappa(C,R,\varepsilon)\leq\kappa(C,R)\leq\kappa(C,R,\varepsilon)+\varepsilon\log(n_{1}n_{2}). It is shown in [ 12 , equation (1.2)] that the unique solution of ( 1.8 ) is of the form (1.10) \displaystyle\rho=\exp\left(\sum_{i=1}^{d}\hat{U}_{i}-\frac{1}{\varepsilon}C\right)\in\Gamma(R), \displaystyle\hat{U}_{i}=(\otimes_{j=1}^{i-1}I_{n_{j}})\otimes U_{i}\otimes(\otimes_{k=i+1}^{d}I_{n_{k}}),\quad U_{i}\in\mathrm{H}_{n_{i}},i\in[d]. The choice of U_{1},\ldots,U_{d} is not unique, and some normalizations on U_{1},\ldots,U_{d} can be imposed [ 12 ] . The step k of the Sinkhorn algorithm consists of choosing a mode j_{k}\in[d] and updating U_{j_{k}} such that the corresponding \rho_{k+1} in the above equation satisfies \tr_{\widehat{j_{k}}}\rho_{k+1}=\tr\rho_{j_{k}} . While this condition for the classical Sinkhorn algorithm is very simple, in the quantum case it is computationally complex [ 7 , 33 ] . 1.3. Our contribution In this paper we use a relaxation to the classical and quantum MPOTP and their duals using a barrier function, which is the corner stone of the interior point method (IPM). For the minimum problems the barrier function has to be a smooth convex functions that blow up on the boundary of a given convex domain, and satisfy a few other technical conditions [ 27 , 34 ] . Observe that the Shannon and von Neumann entropies are not barriers as they don’t blow up at the boundary. In [ 15 ] we showed how to apply the IPM method for the classical MPOTP. We briefly explain our approach for the BPOTP. The barrier functions on \mathbb{R}_{++}^{n} and \mathbb{R}_{++}^{n_{1}\times n_{2}} are (1.11) \displaystyle\beta(\mathbf{x})=-\sum_{i=1}^{n}\log x_{i},\quad\mathbf{x}\in R_{++}^{n}, \displaystyle\beta(V)=-\sum_{j_{1}=j_{2}=1}^{n_{1},n_{2}}\log v_{j_{1},j_{2}},\quad V=[v_{j_{1},j_{2}}]\in\mathbb{R}_{++}^{n_{1}\times n_{2}}. In what follows we denote (1.12) (R^{n_{1}}\times\mathbb{R}^{n_{2}})_{++,b}=\{(\mathbf{x},\mathbf{y})\in\mathbb{R}_{++}^{n_{1}}\times\mathbb{R}^{n_{2}}_{++},\mathbf{1}_{n_{1}}^{\top}\mathbf{x}=\mathbf{1}_{n_{2}}^{\top}\}. For (\mathbf{p}_{1},\mathbf{p}_{2})\in(R^{n_{1}}\times\mathbb{R}^{n_{2}})_{++,b} we define V(P) as in ( 1.1 ). We call \tau(C,P) given by ( 1.2 ) the (generalized) classical BPOTP. Let \mathrm{V}_{o}(P) be the interior of \mathrm{V}(P) , which consists of all positive matrices in \mathrm{V}(P) . The relaxed BPOTP is (1.13) \tau_{\beta}(C,P,\varepsilon)=\min_{V\in\mathrm{V}_{o}(P)}\tr C^{T}V+\varepsilon\beta(V). We