  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_sigma sigma, where sigma are permutation matrices and
A_sigma 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^{-1/2}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.
