Approximating orthogonal matrices by permutation matrices

الأصل · EN

Motivated in part by a problem of combinatorial optimization and in part by analogies with quantum computations, we consider approximations of orthogonal matrices U by ``non-commutative convex combinations'' A of permutation matrices of the type A=sum Aₛigma sigma, where sigma are permutation matrices and Aₛigma are positive semidefinite nxn matrices summing up to the identity matrix. We prove that for every nxn orthogonal matrix U there is a non-commutative convex combination A of permutation matrices which approximates U entry-wise within an error of c n⁻¹/²ln n and in the Frobenius norm within an error of c ln n. The proof uses a certain procedure of randomized rounding of an orthogonal matrix to a permutation matrix.