Circuit partitions and #P-complete products of inner products

الأصل · EN

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 xᵥ. We take the product, over all edges (u,v), of the inner product <xᵤ,xᵥ>. Finally, q(G;k) is the expectation of this product, where the xᵥ 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.