Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2005.01453 · Linear Algebra and its Applications

Information geometry of operator scaling

Takeru Matsuda, Tasuku Soma

Published May 16, 2022• 3 citations
arXivHTMLPDF

Abstract

Matrix scaling is a classical problem with a wide range of applications. It is known that the Sinkhorn algorithm for matrix scaling is interpreted as alternating e-projections from the viewpoint of classical information geometry. Recently, a generalization of matrix scaling to completely positive maps called operator scaling has been found to appear in various fields of mathematics and computer science, and the Sinkhorn algorithm has been extended to operator scaling. In this study, the operator Sinkhorn algorithm is studied from the viewpoint of quantum information geometry through the Choi representation of completely positive maps. The operator Sinkhorn algorithm is shown to coincide with alternating e-projections with respect to the symmetric logarithmic derivative metric, which is a Riemannian metric on the space of quantum states relevant to quantum estimation theory.

DOI
10.1016/j.laa.2022.04.022

Related papers

Quantum Algorithms for Matrix Scaling and Matrix Balancing

Joran van Apeldoorn, Sander Gribling, Yinan Li +3 more

Matrix scaling and matrix balancing are two basic linear-algebraic problems with a wide variety of applications, such as approximating the permanent, and pre-conditioning linear systems to make them more numerically stable. We study the power and limitations of quantum algorithms for these problems. We provide quantum implementations of two classical (in both senses of the word) methods: Sinkhorn’s algorithm for matrix scaling and Osborne’s algorithm for matrix balancing. Using amplitude estimation as our main tool, our quantum implementations both run in time Õ(√{mn}/ε⁴) for scaling or balancing an n × n matrix (given by an oracle) with m non-zero entries to within 𝓁₁-error ε. Their classical analogs use time Õ(m/ε²), and every classical algorithm for scaling or balancing with small constant ε requires Ω(m) queries to the entries of the input matrix. We thus achieve a polynomial speed-up in terms of n, at the expense of a worse polynomial dependence on the obtained 𝓁₁-error ε. Even for constant ε these problems are already non-trivial (and relevant in applications). Along the way, we extend the classical analysis of Sinkhorn’s and Osborne’s algorithm to allow for errors in the computation of marginals. We also adapt an improved analysis of Sinkhorn’s algorithm for entrywise-positive matrices to the 𝓁₁-setting, obtaining an Õ(n^{1.5}/ε³)-time quantum algorithm for ε-𝓁₁-scaling. We also prove a lower bound, showing our quantum algorithm for matrix scaling is essentially optimal for constant ε: every quantum algorithm for matrix scaling that achieves a constant 𝓁₁-error w.r.t. uniform marginals needs Ω(√{mn}) queries.

arXiv:2011.12823•Leibniz international proceedings in informatics•Nov 25, 2020•6 citations

Quantum entropic regularization of matrix-valued optimal transport

Gabriel Peyré A, Lénaïc Chizat, François‐Xavier Vialard +1 more

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.

arXiv:1612.08731•European Journal of Applied Mathematics•Sep 28, 2017•35 citations

Autoparallelity of quantum statistical manifolds in light of quantum estimation theory

Hiroshi Nagaoka, Akio Fujiwara

In this paper we study the autoparallelity w.r.t. the e-connection for an information-geometric structure called the SLD structure, which consists of a Riemannian metric and mutually dual e- and m-connections, induced on the manifold of strictly positive density operators. Unlike the classical information geometry, the e-connection has non-vanishing torsion, which brings various mathematical difficulties. The notion of e-autoparallel submanifolds is regarded as a quantum version of exponential families in classical statistics, which is known to be characterized as statistical models having efficient estimators (unbiased estimators uniformly achieving the equality in the Cramér-Rao inequality). As quantum extensions of this classical result, we present two different forms of estimation-theoretical characterizations of the e-autoparallel submanifolds. We also give several results on the e-autoparallelity, some of which are valid for the autoparallelity w.r.t. an affine connection in a more general geometric situation.

arXiv:2307.03431•Information Geometry•Sep 5, 2026•0 citations

Information geometry of density matrices and state estimation

Dorje C. Brody

Given a pure state vector | x ⟩ and a density matrix , the function defines a probability density on the space of pure states parameterised by density matrices. The associated Fisher–Rao information measure is used to define a unitary invariant Riemannian metric on the space of density matrices. An alternative derivation of the metric, based on square-root density matrices and trace norms, is provided. This is applied to the problem of quantum-state estimation. In the simplest case of unitary parameter estimation, new higher-order corrections to the uncertainty relations, applicable to general mixed states, are derived.

arXiv:1009.1115•Journal of Physics A Mathematical and Theoretical•May 19, 2011•32 citations

Role Of Partial Transpose And Generalized Choi Maps In Quantum Dynamical Semigroups Involving Separable And Entangled States

Ajit Singh

Power symmetric stochastic matrices introduced by R. Sinkhorn (1981) and their generalization by R.B. Bapat, S.K. Jain and K. Manjunatha Prasad (1999) have been utilized to give positive block matrices with trace one possessing positive partial transpose, the so-called PPT states. Another method to construct such PPT states is given, it uses the form of a matrix unitarily equivalent to to its transpose obtained by S.R. Garcia and J.E. Tener (2012). Evolvement or suppression of separability or entanglement of various levels for a quantum dynamical semigroup of completely positive maps has been studied using Choi-Jamiolkowsky matrix of such maps and the famous Hordeckis criteria (1996). A Trichotomy Theorem has been proved, and examples have been given that depend mainly on generalized Choi maps and clearly distinguish the levels of entanglement breaking.

arXiv:1201.0250•Electronic Journal of Linear Algebra•Sep 20, 2015•2 citations

Role Of Partial Transpose And Generalized Choi Maps In Quantum Dynamical Semigroups Involving Separable And Entangled States

Ajit Iqbal Singh

Power symmetric stochastic matrices introduced by R. Sinkhorn (1981) and their generalization by R.B. Bapat, S.K. Jain and K. Manjunatha Prasad (1999) have been utilized to give positive block matrices with trace one possessing positive partial transpose, the so-called PPT states. Another method to construct such PPT states is given, it uses the form of a matrix unitarily equivalent to to its transpose obtained by S.R. Garcia and J.E. Tener (2012). Evolvement or suppression of separability or entanglement of various levels for a quantum dynamical semigroup of completely positive maps has been studied using Choi-Jamiolkowsky matrix of such maps and the famous Hordeckis criteria (1996). A Trichotomy Theorem has been proved, and examples have been given that depend mainly on generalized Choi maps and clearly distinguish the levels of entanglement breaking.

•Dec 21, 2015•1 citation
Matrix scaling is a classical problem with a wide range of applications. It is known that the Sinkhorn algorithm for matrix scaling is interpreted as alternating e-projections from the viewpoint of classical information geometry. Recently, a generalization of matrix scaling to completely positive maps called operator scaling has been found to appear in various fields of mathematics and computer science, and the Sinkhorn algorithm has been extended to operator scaling. In this study, the operator Sinkhorn algorithm is studied from the viewpoint of quantum information geometry through the Choi representation of completely positive maps. The operator Sinkhorn algorithm is shown to coincide with alternating e-projections with respect to the symmetric logarithmic derivative metric, which is a Riemannian metric on the space of quantum states relevant to quantum estimation theory.
Matrix scaling and matrix balancing are two basic linear-algebraic problems with a wide variety of applications, such as approximating the permanent, and pre-conditioning linear systems to make them more numerically stable. We study the power and limitations of quantum algorithms for these problems. We provide quantum implementations of two classical (in both senses of the word) methods: Sinkhorn’s algorithm for matrix scaling and Osborne’s algorithm for matrix balancing. Using amplitude estimation as our main tool, our quantum implementations both run in time Õ(√{mn}/ε⁴) for scaling or balancing an n × n matrix (given by an oracle) with m non-zero entries to within 𝓁₁-error ε. Their classical analogs use time Õ(m/ε²), and every classical algorithm for scaling or balancing with small constant ε requires Ω(m) queries to the entries of the input matrix. We thus achieve a polynomial speed-up in terms of n, at the expense of a worse polynomial dependence on the obtained 𝓁₁-error ε. Even for constant ε these problems are already non-trivial (and relevant in applications). Along the way, we extend the classical analysis of Sinkhorn’s and Osborne’s algorithm to allow for errors in the computation of marginals. We also adapt an improved analysis of Sinkhorn’s algorithm for entrywise-positive matrices to the 𝓁₁-setting, obtaining an Õ(n^{1.5}/ε³)-time quantum algorithm for ε-𝓁₁-scaling. We also prove a lower bound, showing our quantum algorithm for matrix scaling is essentially optimal for constant ε: every quantum algorithm for matrix scaling that achieves a constant 𝓁₁-error w.r.t. uniform marginals needs Ω(√{mn}) queries.
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.
In this paper we study the autoparallelity w.r.t. the e-connection for an information-geometric structure called the SLD structure, which consists of a Riemannian metric and mutually dual e- and m-connections, induced on the manifold of strictly positive density operators. Unlike the classical information geometry, the e-connection has non-vanishing torsion, which brings various mathematical difficulties. The notion of e-autoparallel submanifolds is regarded as a quantum version of exponential families in classical statistics, which is known to be characterized as statistical models having efficient estimators (unbiased estimators uniformly achieving the equality in the Cramér-Rao inequality). As quantum extensions of this classical result, we present two different forms of estimation-theoretical characterizations of the e-autoparallel submanifolds. We also give several results on the e-autoparallelity, some of which are valid for the autoparallelity w.r.t. an affine connection in a more general geometric situation.
Given a pure state vector | x ⟩ and a density matrix , the function defines a probability density on the space of pure states parameterised by density matrices. The associated Fisher–Rao information measure is used to define a unitary invariant Riemannian metric on the space of density matrices. An alternative derivation of the metric, based on square-root density matrices and trace norms, is provided. This is applied to the problem of quantum-state estimation. In the simplest case of unitary parameter estimation, new higher-order corrections to the uncertainty relations, applicable to general mixed states, are derived.
Power symmetric stochastic matrices introduced by R. Sinkhorn (1981) and their generalization by R.B. Bapat, S.K. Jain and K. Manjunatha Prasad (1999) have been utilized to give positive block matrices with trace one possessing positive partial transpose, the so-called PPT states. Another method to construct such PPT states is given, it uses the form of a matrix unitarily equivalent to to its transpose obtained by S.R. Garcia and J.E. Tener (2012). Evolvement or suppression of separability or entanglement of various levels for a quantum dynamical semigroup of completely positive maps has been studied using Choi-Jamiolkowsky matrix of such maps and the famous Hordeckis criteria (1996). A Trichotomy Theorem has been proved, and examples have been given that depend mainly on generalized Choi maps and clearly distinguish the levels of entanglement breaking.
Power symmetric stochastic matrices introduced by R. Sinkhorn (1981) and their generalization by R.B. Bapat, S.K. Jain and K. Manjunatha Prasad (1999) have been utilized to give positive block matrices with trace one possessing positive partial transpose, the so-called PPT states. Another method to construct such PPT states is given, it uses the form of a matrix unitarily equivalent to to its transpose obtained by S.R. Garcia and J.E. Tener (2012). Evolvement or suppression of separability or entanglement of various levels for a quantum dynamical semigroup of completely positive maps has been studied using Choi-Jamiolkowsky matrix of such maps and the famous Hordeckis criteria (1996). A Trichotomy Theorem has been proved, and examples have been given that depend mainly on generalized Choi maps and clearly distinguish the levels of entanglement breaking.