Clifford algebras and approximating the permanent (Q5917579)

Computing permanents is a hard problem compared with computing the determinant. Randomized algorithms can yield estimates of predictable precision computable in a faster way. The present paper studies permanents of \((0,1)\)-matrices utilizing the fact that \(\text{ perm}(A)=E[|\text{ det}(A)^2|]\) is an unbiased estimate, where the positive entries of \(\text{ det}(A)\) are chosen with random signs. The quality of the estimate is given by the second moment, or equivalently \(E[X_A^2]/E[X_A]^2\), called critical ratio. The quality of the estimate can be improved if the randomization is not restricted to the sign, but if for the positive elements in \(A\) one inserts basis elements of Clifford algebras. Examples with complex numbers and quaternions appear in the literature. The main result is that the estimator is bounded from above by the critical ratio \((1+1/2^{2q})^{n/2}\) in \(CL_m\) with \(m = 4q+2\) for \(n\times n\)-matrices. The authors implemented such algorithms showing the improvement. If determinants of Clifford valued matrices can be computed as easily as ordinary determinants, such an algorithm could come up with a polynomial time estimate for permanents.