Operator scaling and applications
1"We study operator scaling, a quantum generalization of Sinkhorn's matrix scaling. The main contribution of the paper is a complexity analysis of an existing
algorithm due to Gurvits, who proved it was polynomial time for
certain classes of inputs.
We prove it always runs in polynomial time. The main component of our
analysis is a simple (given the necessary known tools) lower bound on
central notion of capacity of operators (introduced by Gurvits, not to be confused with capacity of quantum channels).
We extend the algorithm to actually approximate capacity to any accuracy
in polynomial time.
Operator scaling, and the related structural and algorithmic questions, have a remarkable number of diverse
origins and motivations. They arise independently in (commutative) invariant theory and representation theory, linear algebra, optimization,
linear system theory, quantum information theory, approximation of the permanent and naturally in non-commutative algebra. So our algorithm has implications in all of these fields of mathematics. In particular, we obtain the first deterministic polynomial algorithm for computing non-commutative rank of symbolic matrices (a problem whose commutative cousin is a major open problem in computational complexity theory). The operator scaling algorithm has also found applications in computing optimal constants in Brascamp-Lieb inequalities."