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.
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.
This article introduces a new notion of optimal transport (OT) between tensor fields, which are measures whose values are positive semidefinite (PSD) matrices. This “quantum” formulation of optimal transport (Q-OT) corresponds to a relaxed version of the classical Kantorovich transport problem, where the fidelity between the input PSD-valued measures is captured using the geometry of the Von-Neumann quantum entropy. We propose a quantum-entropic regularization of the resulting convex optimization problem, which can be solved efficiently using an iterative scaling algorithm. This method is a generalization of the celebrated Sinkhorn algorithm to the quantum setting of PSD matrices. We extend this formulation and the quantum Sinkhorn algorithm to compute barycentres within a collection of input tensor fields. We illustrate the usefulness of the proposed approach on applications to procedural noise generation, anisotropic meshing, diffusion tensor imaging and spectral texture synthesis.
The growing demand for solving large-scale, data-intensive linear and conic optimization problems, particularly in applications such as artificial intelligence and machine learning, has highlighted the limitations of classical interior point methods (IPMs). Despite their favorable polynomial-time convergence, conventional IPMs often suffer from high per-iteration computational costs, especially for dense problem instances. Recent advances in quantum computing, particularly quantum linear system solvers, offer promising avenues to accelerate the most computationally intensive steps of IPMs. However, practical challenges such as quantum error, hardware noise, and sensitivity to poorly conditioned systems remain significant obstacles. In response, a series of Quantum IPMs (QIPMs) has been developed to address these challenges, incorporating techniques such as feasibility maintenance, iterative refinement, and preconditioning. In this work, we review this line of research with a focus on our recent contributions, including an almost-exact QIPM framework. This hybrid quantum-classical approach constructs and solves the Newton system entirely on a quantum computer, while performing solution updates classically. Crucially, all matrix-vector operations are executed on quantum hardware, enabling the method to achieve an optimal worst-case scalability w.r.t dimension, surpassing the scalability of existing classical and quantum IPMs.
In this manuscript, we study the (finite-dimensional) static formulation of quantum optimal transport problems with general convex regularization and its unbalanced relaxation. In both cases, we show a duality result, characterizations of minimizers (for the primal) and maximizers (for the dual). An important tool we define is a non-commutative version of the classical ( c , ψ , ε ) -transforms associated with a general convex regularization, which we employ to prove the convergence of the associated Sinkhorn iterations. Finally, we show the convergence of the unbalanced transport problems towards the constrained one, as well as the convergence of transforms, as the marginal penalization parameters go to +∞.
The emergence of huge-scale, data-intensive linear optimization (LO) problems in applications such as machine learning has driven the need for more computationally efficient interior point methods (IPMs). While conventional IPMs are polynomial-time algorithms with rapid convergence, their per-iteration cost can be prohibitively high for dense large-scale LO problems. Quantum linear system solvers have shown potential in accelerating the solution of linear systems arising in IPMs. In this work, we introduce a novel almost-exact quantum IPM, where the Newton system is constructed and solved on a quantum computer, while solution updates occur on a classical machine. Additionally, all matrix-vector products are performed on the quantum hardware. This hybrid quantum-classical framework achieves an optimal worst-case scaling of O(n2) for fully dense LO problems. To ensure high precision, despite the limited accuracy of quantum operations, we incorporate iterative refinement techniques both within and outside the proposed IPM iterations. The proposed algorithm has a quantum complexity of O(n1.5κAlog(ε1)) queries to QRAM and O(n2log(ε1)) classical arithmetic operations. Our method outperforms the worst-case complexity of prior classical and quantum IPMs, offering a significant improvement in scalability and computational efficiency.
The growing demand for solving large-scale, data-intensive linear and conic optimization problems, particularly in applications such as arti?cial intelligence and machine learning, has highlighted the limitations of classical interior point methods (IPMs). Despite their favorable polynomial-time convergence, conventional IPMs often su!er from high per-iteration computational costs, especially for dense problem instances. Recent advances in quantum computing, particularly quantum linear system solvers, o!er promising avenues to accelerate the most computationally intensive steps of IPMs. However, practical challenges such as quantum error, hardware noise, and sensitivity to poorly conditioned systems remain signi?cant obstacles. In response, a series of Quantum IPMs (QIPMs) has been developed to address these challenges, incorporating techniques such as feasibility maintenance, iterative re?nement, and preconditioning. In this work, we review this line of research with a focus on our recent contributions, including an almost-exact QIPM framework. This hybrid quantum-classical approach constructs and solves the Newton system entirely on a quantum computer, while performing solution updates classically. Crucially, all matrix-vector operations are executed on quantum hardware, enabling the method to achieve an optimal worstcase scalability w.r.t dimension, surpassing the scalability of existing classical and quantum IPMs.
We study constructive discrete multimarginal optimal transport (MOT) among m distributions on n points, where the cost tensor C has N=nm entries. For additive accuracy ε, let κ=max{1,(maxC−minC)/ε}. Classically, we give two algorithms that return exactly feasible additive-ε couplings. A deterministic box--simplex method with rounding runs in O(m2NκlogN)=O(m3Nκ) time, while an exact reduction to positive packing followed by rank-one completion runs in randomized time O(m2Nκ). At fixed κ, both match the Ω(N) cost of writing a dense coupling, up to factors in m and logarithms. Quantumly, in the general entry-access model, tensor Sinkhorn followed by sparse recovery returns an exactly feasible additive-ε coupling as a classical list of O(m2nκ2) atoms, using O(m4Nnκ3) coherent cost queries without materializing the tensor. Finally, for fixed m and constant normalized accuracy, we prove sparse-output lower bounds of Ω(N) randomized classical queries, even with unrestricted output size, and Ω(Nn) quantum queries for outputs with at most npolylog(n) atoms. Hence, for fixed m and normalized accuracy between (logn)−O(1) and a sufficiently small constant, explicit sparse MOT construction has query complexity Θ(N) classically and Θ(Nn) quantumly.