I've found a couple of other Permanent formulas, which are probably well known (to those who know them). Our 19th century colleagues were especially good at this stuff. In the complex number construction, instead of selecting the elements of the random vector from the unit circle, one can select 50:50 from +-1, and the construction still works. This leads to a non-random formula, simply by going through all combinations of +-1 in the "random" vector. The first element can be forced to +1 without harm. This gives an (N-1) * 2^(N-1) multiplications method; the +-1 combinations can be traversed in gray-code to limit the amount of addition work required for computing the column-sums. This could also be the basis for a more standard QCmp approach using random bits: The +-1s could be fabulated in the usual 50:50 fashion, and the product computed using "ordinary quantum gates". The difficult part is estimating the expected value of the product. Another easy algorithm uses 0,1 in the random vector instead of +-1, but the product terms are signed +-1, depending on an even/odd number of 0s in the "random" vector. In this case the terms are simply added (or subtracted) to get the permanent. Example: Perm [ A B ] [ C D ] = (A+C)(B+D) - AB - CD + 0*0 = AD + BC Another way to look at the permanent: If the random vector is symbolic, (x y z ...), then the coefficient of the all-linear term in the product, xyz..., is the permanent. In the N=2 example, (Ax+Cy) (Bx + Dy) = AB x^2 + (AD+BC) xy + CD y^2. Of course it works the same with rows instead of columns. The minimum necessary for using permanents to solve NP problems is to distinguish (with accuracy > 50%) between a permanent value of 0 and a specific known non-zero value (something like 4^N * N!). If the matrix entries are non-negative numbers this is an easy problem. Unfortunately the insteresting problems involve (small) negative numbers. Dan will note that +-1 is just the 0-dim case of the unit circle, and wonder what happens if we step out to quaternions etc. Beyond noting that commutativity needs to be addressed, deponent sayeth not. Rich rcs@cs.arizona.edu