Circuit Partitions and #P-complete Products of Inner Products

We present a simple, natural #P-complete problem. Let G be a directed graph, and let k be a positive integer. We define q(G; k) as follows. At each vertex v, we place a k-dimensional complex vector xv . We take the product, over all edges (u, v), of the inner product 〈xu , xv 〉. Finally, q(G; k) is the expectation of this product, where the xv are chosen uniformly and independently from all vectors of norm 1 (or, alternately, from the Gaussian distribution). We show that q(G; k) is proportional to G’s cycle partition polynomial, and therefore that it is #P-complete for any k > 1.